11-散列1 电话聊天狂人 (25 分)
给定大量手机用户通话记录，找出其中通话次数最多的聊天狂人。
输入格式:
输入首先给出正整数N（≤105），为通话记录条数。随后N行，每行给出一条通话记录。简单起见，这里只列出拨出方和接收方的11位数字构成的手机号码，其中以空格分隔。
输出格式:
在一行中给出聊天狂人的手机号码及其通话次数，其间以空格分隔。如果这样的人不唯一，则输出狂人中最小的号码及其通话次数，并且附加给出并列狂人的人数。
输入样例:
1
2
3
4
5
6
| 4
13005711862 13588625832
13505711862 13088625832
13588625832 18087925832
15005713862 13588625832
//结尾无空行
|
输出样例:
代码
本篇文章主要代码源自于陈越姥姥的课程里的小白专场
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
|
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<math.h>
#define KEYLENGTH 11
#define MAXTABLESIZE 100000
#define MAXD 5
typedef char ElementType[KEYLENGTH+1];
typedef int Index;
typedef struct LNode *PtrToLNode;
struct LNode {
ElementType Data;
PtrToLNode Next;
int Count;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;
typedef struct TblNode *HashTable;
struct TblNode {
int TableSize;
List Heads;
};
int NextPrime(int N)
{
int i,p=(N%2)?N+2:N+1;
while(p<=MAXTABLESIZE) {
for(i=(int)sqrt(p);i>2;i--)
if(!(p%i)) break;
if(i==2) break;
else p+=2;
}
return p;
}
int Hash(int Key,int TableSize) {
return Key%TableSize;
}
HashTable CreateTable(int TableSize)
{
HashTable H;
int i;
H = (HashTable)malloc(sizeof(struct TblNode));
H->TableSize = NextPrime(TableSize);
H->Heads = (List)malloc(H->TableSize * sizeof(struct LNode));
for(i=0;i<H->TableSize;i++)
{
H->Heads[i].Data[0]='\0';
H->Heads[i].Next = NULL;
H->Heads[i].Count = 0;
}
return H;
}
Position Find(HashTable H,ElementType Key)
{
Position P;
Index Pos;
Pos = Hash(atoi(Key+KEYLENGTH-MAXD),H->TableSize);
P = H->Heads[Pos].Next;
while(P && strcmp(P->Data,Key))
P = P->Next;
return P;
}
bool Insert(HashTable H,ElementType Key)
{
Position P,NewCell;
Index Pos;
P = Find(H,Key);
if(! P) {
NewCell = (Position)malloc(sizeof(struct LNode));
strcpy(NewCell->Data,Key);
NewCell->Count = 1;
Pos = Hash(atoi(Key+KEYLENGTH-MAXD),H->TableSize);
NewCell->Next = H->Heads[Pos].Next;
H->Heads[Pos].Next = NewCell;
}else {
P->Count ++;
return false;
}
}
void DestroyTable(HashTable H) {
int i;
Position P,Tmp;
for(i=0;i<H->TableSize;i++) {
P = H->Heads[i].Next;
while(P) {
Tmp = P->Next;
free(P);
P = Tmp;
}
}
free(H->Heads);
free(H);
}
void ScanAndOutput(HashTable H)
{
int i;
int MaxCnt = 0;
int PCnt = 0;
ElementType MinPhone;
List Ptr;
MinPhone[0] = '\0';
for(i=0;i<H->TableSize;i++) {
Ptr = H->Heads[i].Next;
while(Ptr) {
if(Ptr->Count > MaxCnt) {
MaxCnt = Ptr->Count;
strcpy(MinPhone,Ptr->Data);
PCnt = 1;
}else if (Ptr->Count == MaxCnt) {
PCnt ++;
if(strcmp(MinPhone,Ptr->Data)>0)
strcpy(MinPhone,Ptr->Data);
}
Ptr = Ptr->Next;
}
}
printf("%s %d",MinPhone,MaxCnt);
if(PCnt > 1) printf(" %d",PCnt);
printf("\n");
}
int main()
{
int N,i;
ElementType Key;
HashTable H;
scanf("%d",&N);
H = CreateTable(N*2);
for(i=0;i<N;i++) {
scanf("%s",Key); Insert(H,Key);
scanf("%s",Key);Insert(H,Key);
}
ScanAndOutput(H);
DestroyTable(H);
return 0;
}
|
