编辑代码

#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

//关键词字符串的最大长度
#define KEYLENGTH 11
#define MAXTABLESIZE 1000
#define MinTableSize 5
//参与散列映射计算的字符个数
#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 Hash(int Key,int P);
int NextPrime(int N);
int sqrtBinary(int p);
HashTable CreateTable(int TableSize);
Position Find(HashTable H,ElementType Key);
bool Insert(HashTable H,ElementType Key);
void ScanfAndOutput(HashTable H);

void ScanfAndOutput(HashTable H){
    int i,MaxCount = 0;
    int PCount = 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 > MaxCount){
               MaxCount = Ptr->Count;
               strcpy(MinPhone,Ptr->Data);
               PCount = 1;
            }else if(Ptr->Count == MaxCount){
                //狂人计数
                PCount++;
                if(strcmp(MinPhone,Ptr->Data) > 0){
                    //更新狂人的最小手机号码
                    strcpy(MinPhone,Ptr->Data);
                }
            }
            Ptr = Ptr->Next;
        }
    }

    printf("%s %d",MinPhone,MaxCount);
    if(PCount > 1){
        printf(" %d",PCount);
    }
    printf("\n");
}

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插入为H->Heads[Pos]链表的第一个结点
        NewCell->Next = H->Heads[Pos].Next;
        H->Heads[Pos].Next = NewCell;
        return true;
    }
    //关键词已存在
    else{
        P->Count++;
        return true;
    }
}

Position Find(HashTable H,ElementType Key){
    Position P;
    Index Pos;
    //初始散列位置
    Pos = Hash(atoi(Key+KEYLENGTH-MAXD),H->TableSize);
    //从该链表的第一个结点开始
    P = H->Heads[Pos].Next;
    //当未到表尾，并且Key未找到时，继续往后找
    while(P && strcmp(P->Data,Key)){
        P = P->Next;
    }
    //此时P或者指向找到的结点，或者为NULL
    return P;
}

//哈希表的建立
HashTable CreateTable(int TableSize){
    HashTable H;
    int i;
    if(TableSize < MinTableSize){
        printf("散列表太小");
        return NULL;
    }
    //分配散列表
    H = (HashTable)malloc(sizeof(struct TblNode));
    if(H == NULL){
        printf("空间溢出");
    }
    //H->TableSize = NextPrime(TableSize);
    H->TableSize = TableSize;
    H->Heads = (List)malloc(sizeof(struct LNode)*H->TableSize);
    if(H->Heads == NULL){
        printf("空间溢出");
    }
    for(int i = 0;i < H->TableSize;i++){
        H->Heads[i].Data[0] = '\0';
        H->Heads[i].Next = NULL;
        H->Heads[i].Count = 0;
    }
    return H;
}

//返回大于N且不超过MAXTABLESIZE的最小素数
// int NextPrime(int N){
//     int i;
//     //从大于N的下一个奇数开始
//     //int p = (N%2)? N+2 : N+1;
//     int p = 11;
//     while(p <= MAXTABLESIZE){
//         for(i = sqrt(p);i > 2;i--){
//             //p不是素数
//             if( !(p%i) ){
//                 break;
//             }
//             //for正常结束，说明p是素数
//             if(i ==2){
//                 break;
//             }
//             //否则试探下一个奇数
//             else{
//                 p += 2;
//             }
//         }
//     }
//     return p;
// }

// int sqrtBinary(int p){
//     if(p < 0){
//         printf("数据错误\n");
//     }
//     int mid,last; 
//     int low,up; 
//     low=0,up=p; 
//     mid=(low+up)/2; 
//     do
//     {
//         if(mid*mid>p){
//             up=mid; 
//         }
//         else{ 
//             low=mid;
//         }
//         last=mid;
//         mid=(up+low)/2; 
//     }while(mid*mid > p);

//     return mid; 
// }

//散列函数
int Hash(int Key,int P){
    //除留余数法散列函数
    return Key%P;
}

int main () {
    int N,i,HashTableSize;
    ElementType Key;
    HashTable H;

    // printf("输入电话对数：\n");
    // scanf("%d",&N);

    //创建一个散列表
    //H = CreateTable(N);
    H = CreateTable(5);
    for(i = 0;i < 4;i++){
        printf("输入第%d对的第一个号码：\n",i);
        scanf("%s",Key);
        Insert(H,Key);
        printf("输入第%d对的第二个号码：\n",i);
        scanf("%s",Key);
        Insert(H,Key);
    }
    ScanfAndOutput(H);
    //DestroyTable(H);
    return 0;
}