PTA 哈希查找 除留取余法

  1 //本题采用除留取余法构造哈希函数，使用分离链表法解决冲突
  2 
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <cstdlib>
  6 #include <iostream>
  7 
  8 using namespace std;
  9 #define KEYLENGTH 11                   /* 关键词字符串的最大长度 */
 10 typedef char ElementType[KEYLENGTH+1]; /* 关键词类型用字符串 */
 11 typedef int Index;                     /* 散列地址类型 */
 12 
 13 #define MAXTABLESIZE 1000000
 14 
 15 typedef struct LNode *PtrToLNode;
 16 struct LNode
 17 {
 18     ElementType Data;
 19     PtrToLNode Next;
 20     int cnt;
 21 };
 22 typedef PtrToLNode Position;
 23 typedef PtrToLNode List;
 24 
 25 typedef struct TblNode *HashTable; /* 散列表类型 */
 26 struct TblNode     /* 散列表结点定义 */
 27 {
 28     int TableSize; /* 表的最大长度 */
 29     List Heads;    /* 指向链表头结点的数组 */
 30 };
 31 
 32 Index Hash(int k, int TableSize )  //哈希函数
 33 {
 34     return k%TableSize; //除留取余法
 35 }
 36 
 37 int nextPrime(int n)  //选取一个产生冲突较少的素数，作为表长
 38 {
 39     int j=n%2?n+2:n+1;
 40     while(j<=MAXTABLESIZE)
 41     {
 42         int i=0;
 43         for(i=2; i*i<=j; i++)
 44         {
 45             if(!(j%i))
 46                 break;
 47         }
 48         if(i*i>j)
 49             return j;
 50         else
 51             j+=2;   //素数每次加2，减少循环次数
 52     }
 53 }
 54 Position Find(HashTable h,ElementType key,Index k)
 55 {
 56     Position p=h->Heads[k].Next;
 57     while(p&&strcmp(key,p->Data))
 58     {
 59         p=p->Next;
 60     }
 61     return p;
 62 }
 63 void insert(HashTable h,ElementType key)
 64 {
 65     int sum=0;
 66     for(int i=6; i<11; i++)
 67     {
 68         sum=sum*10+(key[i]-'0');   //以第七位到第11位的元素进行哈希
 69     }
 70     Index k=Hash(sum,h->TableSize);
 71     Position p=Find(h,key,k);
 72     if(!p)
 73     {
 74         //使用头插法，提高算法效率
 75         Position newPtr=(Position)malloc(sizeof(LNode));
 76         strcpy(newPtr->Data,key);
 77         newPtr->Next=NULL;
 78         newPtr->cnt=1;
 79         newPtr->Next=h->Heads[k].Next;
 80         h->Heads[k].Next=newPtr;
 81 
 82     }
 83     else
 84         p->cnt++;
 85 }
 86 HashTable BuildTable(int m)
 87 {
 88 
 89     HashTable h;
 90     h=(HashTable)malloc(sizeof(TblNode));
 91     //cout<<"111111111111"<<endl;
 92     h->TableSize=nextPrime(m);
 93     h->Heads=(List)malloc(sizeof(LNode)*h->TableSize);
 94 
 95     for(int i=0; i<h->TableSize; i++)
 96     {
 97         h->Heads[i].Next=NULL;
 98         h->Heads[i].cnt=0;
 99     }
100     return h;
101 }
102 
103 int main()
104 {
105     int n,m;
106     scanf("%d",&n);
107     m=2*n;
108     ElementType key;
109     HashTable h=BuildTable(m);
110     while(m--)
111     {
112         scanf("%s",key);
113         insert(h,key);
114     }
115     //cout<<"111111111111"<<endl;
116     int maxnum=0;
117     int ans=0;
118     for(int i=0; i<h->TableSize; i++)
119     {
120         Position p=h->Heads[i].Next;
121         while(p)
122         {
123             if(p->cnt>maxnum)
124             {
125                 maxnum=p->cnt;
126                 strcpy(key,p->Data);
127                 ans=1;
128             }
129             else if(p->cnt==maxnum)
130             {
131                 ans++;
132                 if(strcmp(key,p->Data)>0)
133                     strcpy(key,p->Data);
134             }
135             p=p->Next;
136         }
137         //cout<<"111111111111"<<endl;
138     }
139     //cout<<"111111111111"<<endl;
140     printf("%s %d",key,maxnum);
141     if(ans>1)
142         printf(" %d",ans);
143     printf("\n");
144     return 0;
145 }
146 
147 /*
148 4
149 13005711862 13588625832
150 13005711862 13088625832
151 13588625832 18087925832
152 13005711862 13588625832
153 
154 */