PTA数据结构与算法题目集(中文)  7-14

7-14 电话聊天狂人 (25 分)  

给定大量手机用户通话记录，找出其中通话次数最多的聊天狂人。

输入格式:

输入首先给出正整数N（≤），为通话记录条数。随后N行，每行给出一条通话记录。简单起见，这里只列出拨出方和接收方的11位数字构成的手机号码，其中以空格分隔。

输出格式:

在一行中给出聊天狂人的手机号码及其通话次数，其间以空格分隔。如果这样的人不唯一，则输出狂人中最小的号码及其通话次数，并且附加给出并列狂人的人数。

输入样例:

4
13005711862 13588625832
13505711862 13088625832
13588625832 18087925832
15005713862 13588625832

输出样例:

13588625832 3

（7-12 是简单的桶排序应用 7-13是排序的应用 至于排序在另一篇博客里写到了）
题目分析:一道利用散列表(哈希表)的基础题 将数据读入后进行判断就可以了 需要注意要记录所有狂人的人数 那么在找到最新的那个狂人时候 将人数设为1 之后找到与他次数相同的认识 将人数加1

  1 #define _CRT_SECURE_NO_WARNINGS   
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4 #include<malloc.h>
  5 #include<math.h>
  6 #include<string.h>
  7 #define KEYLENGTH 11
  8 #define MAXTABLESIZE 10000
  9 
 10 typedef char ElementType[KEYLENGTH + 1];
 11 typedef struct LNode* PtrToLNode;
 12 typedef PtrToLNode List;
 13 struct  LNode
 14 {
 15     ElementType Data;
 16     PtrToLNode Next;
 17     int TelTimes;
 18 };
 19 
 20 typedef struct HblNode* HashTable;
 21 struct HblNode
 22 {
 23     int TableSize;
 24     List Heads;
 25 };
 26 
 27 long Atoi(ElementType Tel)
 28 {
 29     long num = 0;
 30     int length = strlen(Tel);
 31     for (int i = 0; i < length; i++)
 32         num += num * 10 + Tel[i] - '0';
 33     return num;
 34 }
 35 
 36 int NextPrime(int num)
 37 {
 38     int p = (num % 2) ? num + 2 : num + 1;
 39     int i;
 40     while (p<MAXTABLESIZE)
 41     {
 42         for (i = (int)sqrt(p); i > 2; i--)
 43             if (p % i == 0)
 44                 break;
 45         if (i == 2)
 46             break;
 47         else
 48             p += 2;
 49     }
 50     return p;
 51 }
 52 
 53 int Hash(ElementType Tel,int TabelSize)
 54 {
 55     return atoi(Tel+5) % TabelSize;
 56 }
 57 
 58 HashTable BuildHashTable(int TabelSize)
 59 {
 60     HashTable H = (HashTable)malloc(sizeof(struct HblNode));
 61     H->TableSize = NextPrime(TabelSize);
 62     H->Heads = (List)malloc(H->TableSize * sizeof(struct LNode));
 63     for (int i = 0; i < H->TableSize; i++)
 64     {
 65         H->Heads[i].Data[0] = '\0';
 66         H->Heads[i].Next = NULL;
 67     }
 68     return H;
 69 }
 70 
 71 PtrToLNode Find(ElementType Tel, HashTable H)
 72 {
 73     int i = Hash(Tel,H->TableSize);
 74     PtrToLNode P = H->Heads[i].Next;
 75     while (P && strcmp(P->Data, Tel))
 76         P = P->Next;
 77     return P;
 78 }
 79 
 80 void Insert(ElementType Tel, HashTable H)
 81 {
 82     PtrToLNode P, NewCell;
 83     P = Find(Tel, H);
 84     if (!P)
 85     {
 86         int i = Hash(Tel, H->TableSize);
 87         NewCell = (PtrToLNode)malloc(sizeof(struct LNode));
 88         strcpy(NewCell->Data, Tel);
 89         NewCell->TelTimes = 1;
 90         NewCell->Next = H->Heads[i].Next;
 91         H->Heads[i].Next = NewCell;
 92     }
 93     else
 94         P->TelTimes++;
 95 }
 96 
 97 HashTable CreateHashTable()
 98 {
 99     int N;
100     scanf("%d", &N);
101     HashTable H = BuildHashTable(N);
102     N *= 2;
103     while (N--)
104     {
105         ElementType Tel;
106         scanf("%s", Tel);
107         Insert(Tel, H);
108     }
109     return H;
110 }
111 void Judge(HashTable H)
112 {
113     int TelTimes = -1;
114     PtrToLNode MinP=NULL;
115     PtrToLNode P=NULL;
116     int Persons = 0;
117     for (int i = 0; i < H->TableSize; i++)
118     {
119         P = H->Heads[i].Next;
120         while (P)
121         {
122             if (P->TelTimes > TelTimes)
123             {
124                 Persons = 1;
125                 MinP = P;
126                 TelTimes = P->TelTimes;
127             }
128             else if (P->TelTimes == TelTimes)
129                 Persons++;
130             P = P->Next;
131         }
132     }
133     if(Persons==1)
134         printf("%s %d", MinP->Data,MinP->TelTimes);
135     else
136         printf("%s %d %d", MinP->Data, MinP->TelTimes,Persons);
137 }
138 
139 int main()
140 {
141     HashTable H = CreateHashTable();
142     Judge(H);
143     return 0;
144 }

View Code