《数据结构》实验五哈希表

1、实验五 查找实验目的1 ） 掌握哈希表的构造和查找过程及其算法设计；2 ） 掌握哈希表的平均查找长度的计算。实验内容编写程序，实现哈希表的相关运算，并完成以下功能：建立关键字序列（ 16， 74， 60， 43， 54， 90 ， 46， 31， 29， 88 ， 77）对应的哈希表A0.12 ，哈希函数为 H（k）=k%13 ，并采用开放地址法中的线性探测法解决冲突。要求输出构造的哈希表。在上述哈希表中查找关键字为29 的记录，输出其位置和比较次数；在上述哈希表中删除关键字为77 的记录，再将其插入。输出上述哈希表查找成功时的平均查找长度。设计思路及程序代码（包括程序结构（即函数调用关系）

2、、算法功能描述或流程图、程序代码）#include#define MaxSize 100#define NULLKEY -1#define DELKEY -2typedef int KeyType;typedef char *InfoType;typedef structKeyType key;InfoType data;int count;HashData;typedef HashData HashTableMaxSize;void InsertHT(HashTable ha,int&n,KeyType k,int p)/将关键字 k 插入到哈希表中int i,adr;adr=k%p;if(

3、haadr.key=NULLKEY|haadr.key=DELKEY)/xj 可以直接放在哈希表中 haadr.key=k;haadr.count=1;elsei=1;doadr=(adr+1)%p;i+;while(haadr.key!=NULLKEY&haadr.key!=DELKEY);haadr.key=k;haadr.count=i;n+;void CreateHT(HashTable ha,KeyType x,int n,int m,int p)/创建哈希表int i,n1=0;for(i=0;im;i+)/ 哈希表置初值hai.key=NULLKEY;hai.count=0;fo

4、r(i=0;in;i+)InsertHT(ha,n1,xi,p);int SearchHT(HashTable ha,int p,KeyType k)/ 在哈希表中查找关键字kint i=0,adr;adr=k%p;while(haadr.key!=NULLKEY&haadr.key!=k)i+;/ 采用线性探查找下一个地址adr=(adr+1)%p;if(haadr.key=k)/ 查找成功return adr;else return -1;/ 查找失败int DeleteHT(HashTable ha,int p,int k,int &n)/ 删除哈希表中的关键字 int adr;adr=

5、SearchHT(ha,p,k);if(adr!=-1)/ 在哈希表中找到该关键字haadr.key=DELKEY;n-;/ 哈希表的长度减1return 1;else/ 在哈希表中未找到该关键字return 0;void DispHT(HashTable ha,int n,int m)/ 输出哈希表float avg=0;int i;printf( 哈希表的地址:t);for(i=0;im;i+)printf(%3d,i);printf(n);printf( 哈希表的关键字为 :t);for(i=0;im;i+)if(hai.key=NULLKEY|hai.key=DELKEY) print

6、f( );elseprintf(%3d,hai.key);printf(n);void ASL(HashTable ha,int n,int m,int p)/求平均查找长度int i;int succ=0,unsucc=0;for(i=0;im;i+)if(hai.key!=NULLKEY)succ+=hai.count;/ 累计成功时的总关键字比较次数printf( 成功情况下ASL(%d)=%gn,n,succ*1.0/n);int main()int x=16,74,60,43,54,90,46,31,29,88,77;int n=11,m=13,p=13,i,k=29;HashTab

7、le ha;printf(1)n);CreateHT(ha,x,n,m,p);/ 构造哈希表printf(n);DispHT(ha,n,m);/ 输出哈希表printf(2)n);printf( 查找关键字 29 的记录 :n);i=SearchHT(ha,p,k);if(i!=-1)printf(ha%d.key=%dn,i,k);printf( 查找关键字 29 的比较次数为 :%dn,i);elseprintf( 未找到 %dn,k);printf(3)n);k=77;printf( 删除关键字 %d:n,k);DeleteHT(ha,p,k,n);DispHT(ha,n,m);/ 输出

8、哈希表i=SearchHT(ha,p,k);if(i!=-1)printf(ha%d.key=%dn,i,k);elseprintf( 未找到 %dn,k);printf( 将删除的关键字 77 重新插入 :n,k);/ 重新插入关键字77InsertHT(ha,n,k,p);DispHT(ha,n,m);printf(4)n);printf( 查找成功的平均长度为 :n);ASL(ha,n,m,p);return 0;测试结果(程序运行结果采用截图的方式打印)* ,L:Debug5555xxe,哈希表的地址：0122哈箝泰的美镇宇为二77（2J怪找关键字29的记大m.b. key=29国我关键字加的匕减不圾为不 删除关键字可哈髭表的加圻：（：1 2 3哈花表的关键字为： 未找于m杼删除的关键字在重新氏74 5 6 754 16 43 31a29g i o n is 46 60 74 eesoq ID 11 1254 16 必 3129 4a 74 3哈春表的地西： L 哈希表的关键字力：3 g 10