题目地址
https://pta.patest.cn/pta/test/15/exam/4/question/722
5-14 电话聊天狂人 (25分)
给定大量手机用户通话记录，找出其中通话次数最多的聊天狂人。
输入格式:
输入首先给出正整数NN（\le 10^5≤105），为通话记录条数。随后NN行，每行给出一条通话记录。简单起见，这里只列出拨出方和接收方的11位数字构成的手机号码，其中以空格分隔。
输出格式:
在一行中给出聊天狂人的手机号码及其通话次数，其间以空格分隔。如果这样的人不唯一，则输出狂人中最小的号码及其通话次数，并且附加给出并列狂人的人数。
输入样例:
4
13005711862 13588625832
13505711862 13088625832
13588625832 18087925832
15005713862 13588625832
输出样例:
13588625832 3
链地址实现/*
评测结果
时间 结果 得分 题目 编译器 用时（ms） 内存（MB） 用户
2017-07-07 14:54 正在评测 0 5-14 gcc 无 无
测试点结果
测试点 结果 得分/满分 用时（ms） 内存（MB）
测试点1 答案正确 12/12 2 2
测试点2 答案正确 3/3 2 2
测试点3 答案正确 10/10 105 11 电话号码有11位，故用hash表解决
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXN 110000
#define ERROR -1
typedef struct UserNode * ptrUser; struct UserHashTable
{
ptrUser Head;
} gHashTable[MAXN]; struct UserNode
{
char phonenumber[20];
int count;
ptrUser next; //冲突的值用链表串起来
}; void InitHashTable()
{
int i;
for (i=0;i<MAXN;i++)
{
gHashTable[i].Head=NULL;
}
} int Hash(char *num) //取后末尾四位，以及正数第三位电话号码做hash值
{
int i=0,result;
result=(num[10]-'0')+(num[9]-'0')*10+(num[8]-'0')*100+(num[7]-'0')*1000+(num[2]-'0')*10000;
return result;
} ptrUser CreateUserNode(char *a)
{
ptrUser P;
P=malloc(sizeof(struct UserNode));
P->count=1;
P->next=NULL;
strcpy(P->phonenumber,a);
} void InsertUserToTable(ptrUser T)
{
int idx;
idx=Hash(T->phonenumber);
T->next=gHashTable[idx].Head;
gHashTable[idx].Head=T;
} ptrUser FindUser(char *num)
{
int idx;
ptrUser T;
idx=Hash(num);
T=gHashTable[idx].Head;
while(T!=NULL)
{
if(strcmp(T->phonenumber,num)==0)
return T;
T=T->next;
}
return NULL;
} void Count()
{
char maxnumber[20];
int i,maxcount=0,samecount=1;
ptrUser P;
for(i=0;i<MAXN;i++)
{
P=gHashTable[i].Head;
while(P!=NULL)
{
if(P->count > maxcount)
{
maxcount=P->count;
strcpy(maxnumber,P->phonenumber);
samecount=1;
}
else
{
if(P->count==maxcount)
samecount++;
if(P->count==maxcount && strcmp(maxnumber,P->phonenumber)>0)
{
strcpy(maxnumber,P->phonenumber);
}
} P=P->next;
} } printf("%s %d",maxnumber,maxcount);
if(samecount>1)
{
printf(" %d",samecount);
} } int main()
{
int i,N,temp;
char a[20],b[20];
ptrUser P;
scanf("%d",&N);
InitHashTable();
for(i=0;i<N;i++)
{
scanf("%s %s",a,b);
P=FindUser(a);
if(P==NULL)
{
P=CreateUserNode(a);
InsertUserToTable(P);
}
else
P->count++; P=FindUser(b);
if(P==NULL)
{
P=CreateUserNode(b);
InsertUserToTable(P);
}
else
P->count++;
}
Count(); }