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

《设计构造哈希表的完整算法,求出平均查找长度》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、6,30,13,01,67）按线性探测再散列和二次探测再散列的方法分别构造哈希表。（1）线性探测再散列：3*22％11=0；3*41％11=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+

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

4、单元已被其他元素占用，则继续查看地址为H(key)+d2的存储单元，如此重复直至找到某个存储单元为空时，将关键字为key的数据元素存放到该单元。增量d可以有不同的取法，并根据其取法有不同的称呼：（1）di＝1，2，3，……线性探测再散列；（2）di＝1^2，－1^2，2^2，－2^2，k^2，-k^2……二次探测再散列；（3）di＝伪随机序列伪随机再散列；三源程序代码及测试结果1.源程序代码#include#include#defineM11#defineN8str

5、ucthterm{intkey;//关键字值intsi;//散列次数};structhtermhlist[M];inti,adr,sum,d;intx[N]={22,41,53,46,30,13,1,67};//关键字赋值floataverage;voidchash()//创建哈希表{for(i=0;i

6、ist[adr].key=x[i];hlist[adr].si=1;}else{do//冲突处理{d=(d+1)%M;sum=sum+1;}while(hlist[d].key!=0);hlist[d].key=x[i];hlist[d].si=sum+1;}}}voiddhash()//输出哈希表{cout<<"哈希表地址：";for(i=0;i

7、list[i].key;cout<