设计构造哈希表的完整算法,求出平均查找长度

1、程序设计与算法分析实验报告一设计的目的与内容1设计目的通过本实验需要掌握构造哈希函数表，需要完成设计构造哈希表的完整算法，并求出平均查找长度。2实验内容使用哈希函数：H（K）=3*K MOD 11并采用开放地址法解决冲突，试在 0到10的散列地址空间对关键字序列（22, 41, 53, 46, 30,13, 01,67构造哈希函数表，并设计构造哈希表的完整算法，并求出平均查找长度。二算法的基本思想1数据结构的设计哈希函数 H （ key ） =3* key mod 11 ，哈希表的地址空间为 010，对关键字 序列（22,41, 53, 46, 30,13, 01,67按线性探测再散列和二次探

2、测再散列的方法 分别构造哈希表。（1 ）线性探测再散列：3* 22 % 11 = 0 ; 3*41 % 1仁2 ; 3*53 % 11 = 5 ; 3* 46%11=6 ; 3*30%11=2发生冲突，下一个存储地址（2+ 1 ） % 11 = 3 ;3*13%11=6发生冲突，下一个存储地址（6 + 1 ）% 11 = 7 ;3*01%11=3发生冲突，下一个存储地址（3 + 1 ）% 11 = 4 ;3*67%11=3发生冲突，下一个存储地址是：（3 + 1 ） % 11 = 4发生冲突； 下一个存储地址（4 + 1 ） %11=5发生冲突；下一个存储地址（5 + 1 ） %11=6 发生

3、冲突；下一个存储地址（6+ 1 ） %11=7发生冲突；下一个存储地址（7 + 1 ) %11=8未发生冲突。2算法的基本思想开放地址法 这个方法的基本思想是：当发生地址冲突时，按照某种方法 继续探测哈希表中的其他存储单元，直到找到空位置为止。这个过程可用下式 描述：H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,， k ( k w m)其中：H ( key )为关键字key的直接哈希地址，m为哈希表的长度，di为 每次再探测时的地址增量。采用这种方法时，首先计算出元素的直接哈希地址H ( key ),如果该存储单元已被其他元素占用，则继续查看

4、地址为 H ( key ) + d 2的存储单元，如此重复直至找到某个存储单元为空时，将关键字为key的数据元素存放到该单元。增量d可以有不同的取法，并根据其取法有不同的称呼：(1 )d i =1 ,2 ,3 ,线性探测再散列；(2 )d i =1A2，-1A2,2A2，- 2A2 , kA2,-kA2二次探测再散列；(3) d i =伪随机序列 伪随机再散列；三源程序代码及测试结果1.源程序代码#include#include#define M 11#define N 8struct htermint key; /关键字值int si;/散列次数;struct hterm hlistM;/关

5、键字赋值int i,adr,sum,d;int xN=22,41,53,46,30,13,1,67;float average;void chash()/ 创建哈希表for (i=0;iM;i+)hlisti.key=0;hlisti.si=0;for (i=0;iN;i+)sum=0;adr=(3*xi)%M;d=adr;if (hlistadr.key=0)hlistadr.key=xi;hlistadr.si=1;elsedo / 冲突处理d=(d+1)%M;sum=sum+1;while (hlistd.key!=0);hlistd.key=xi;hlistd.si=sum+1;voi

6、d dhash()/ 输出哈希表cout 哈希表地址： ;for(i=0;iM;i+)cout setw(4) i;cout endl; cout 哈希表关键字： ;for (i=0;iM;i+)cout setw(4) hlisti.key;cout endl;cout 搜索长度： ;for (i=0;i M;i+)cout setw(4) hlisti.si;cout endl; average=0;for (i=0;iM;i+)average=average+hlisti.si;average=average/N;cout 平均搜索长度：ASL( N )= average endl; v

7、oid main()chash();dhash();2.测试结果啥希表地址： 嚣I耕雀字 呼均Press anij keyai2145fi?891022674105346013 fl 1131201102A6ASL=2.125to cant inuei=i 回3.存在的问题及解决-Configuratian： I23i56 - Uin32 &ebug Compiling.123ppGAUC+Nicrosoft UisialudioVlyProjects123ii56123xpp( 1 fl) ; error C2236: unexpected struct 世errf执彳亍壮时出错*123.o

8、hj - 1 error(s), 9 uarnlngfs解决方法：struct htermint key;int si;“ ”后面少了一个“；”。四分析与讨论（1 ）线性探测再散列:/关键字值散列次数22 % 11 = 0 ;41 % 1仁8 ;53 % 11 = 9 ;46%11=2 ; 30%11=7 ;13%11=2发生冲突，下一个存储地址（2 + 1 ） % 11 = 3 ;01%11 = 1 ;67%11 = 1发生冲突，下一个存储地址是：（1 + 1 ） % 11 = 2发生冲突； 下一个存储地址（2 + 1 ） %11=3发生冲突；下一个存储地址（3 + 1 ） %11=4 未发生冲突。五心的体会在这次数据结构设计中遇到了很多实际性的问题，在实际设计才发现，书本上理论性的 东西和在实际运用中的还是