课程设计报告--散列法的实验研究.doc

课程设计报告 问题描述： (1) 散列法中，散列函数构造方法多种多样，同时对于同一散列函数解决冲突的方法也可以不同。两者是影响查询算法性能的关键因素。几种典型的散列函数构造方法，不同的解决冲突方法对查询性能的影响。typedef struct { int key; int si; }HashTable1; void CreateHashTable1(HashTable1 *H,int *a,int num)//哈希表线性探测在散列； { int i,d,cnt; for(i=0;iHashSize;i++) { H[i].key=0; H[i].si=0; } for(i=0;inum;i++) { cnt=1; d=a[i]%HashSize; if(H[d].key==0) { H[d].key=a[i]; H[d].si=cnt; } else { do { d=(d+1)%HashSize; cnt++; }while(H[d].key!=0); H[d].key=a[i]; H[d].si=cnt; } } printf(\n线性再探索哈希表已建成!); } 用二次探测再散列建立哈希表，代码实现如下： void CreateHash3(HashTable3 *h,int *a,int num)//二次探索表 { int i,p=-1,c,pp; for(i=0;inum;i++) { c=0; p=a[i]%HashSize; pp=p; while(h-elem[pp]!=NULL) { pp=Collision(p,c); if(pp0) { printf(第%d个记录无法解决冲突\n,i+1); continue; } } h-elem[pp]=(a[a[i]]); h-count++; printf(第%d个记录冲突次数为%d\n,i+1,c); } printf(\n建表完成！\n此哈希表容量为%d,当前表内存储的记录个数%d.\n,HashSize,h-count); } 二次探测再散列法解决冲突 int Collision(int p,int c) { int i,q; i=c/2+1; while(iHashSize) { if(c%2==0) { c++; q=(p+i*i)%HashSize; if(q=0) return q; else i=c/2+1; } else { q=(p-i*i)%HashSize; c++; if(q=0)return q; else i=c/2+1; } } return (-1); } 用线性再散列法查找，代码实现如下： void SearchHash1(HashTable1 *h,int data) { int d; d=data%HashSize; if(h[d].key==data) printf(数字%d的探查次数为：%d\n,h[d].key,h[d].si); else { do d=(d+1)%HashSize; while(h[d].key!=data dHashSize); if(dHashSize) printf(数字%d的探查次数为：%d\n,h[d].key,h[d].si); else printf(没有查找到你所输入的数\n); } 用二次探测再散列法查找 void SearchHash2(HashTable2 * h[],int data,int num) { int d; Node *q; d=data%num; q=h[d]-link; while(q-key!=data q-next!=NULL) q=q-next; if(q-next!=NULL) printf(数字%d的查找次数为：%d\n,q-key,q-next); else printf(没有找到你要查找的那个数\n); } 用链地址法查找，代码实现如下： void CreateHashTable2(HashTable2 *ht[],int *a,int num)//哈希表链地址； { int i,d,cnt; Node *s,*q; for(i=0;inum; i++) { ht[i]=(HashTable2 *)m