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

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

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

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

3、思想•••开放地址法这个方法的基本思想是：当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。这个过程可用下式描述:Hi(key)=(H(key)+di)modm(i=1,2,,k(k

4、称呼：(1)di=1,2,3,……线性探测再散列；(2)di=1A2,-1A2,2A2,-2A2,kA2,-kA2二次探测再散列;(3)di=伪随机序列伪随机再散列;三源程序代码及测试结果源程序代码#include#include#defineM11#defineN8structhtermintkey;〃关键字值};structhtermhlist

5、MJ;inttadr^sum^d;〃关键字赋值intx[N]={22,41,53,46,30,13,1,67};floataverage;voidchashO〃创建哈希表for(i

6、=0;i

7、i])%M;d=adr;if(hlist[adr]>key=0){hlist[adr].key=x[i];hlist[adr].si=l;}else{do〃冲突处理{d=(d+l)%M;sum=sum+l;while(hlist[d]>key!=0);hlist[d]

8、ut«setw(4)«i;cout«endl;cout«n哈希表关键字：”；for(i=0;ivM;i++)cout«setw(4)«hlist[i

9、.key;cout«endl;cout«n搜索长度：”；for(i=0;isi;average=average/N;cout«"平均搜索长度：ASL(n«N«n)=H«average«endl;}voidmain(){chash();dha

10、sh();CD回2.测试结果■G:VC++'MicrosoftVisualStudioMyProjects123456Debug123456.exe":哈希表地址：tels^=乎均毅索长度:Pressanykeyto0123226741301312ASL<8>=2.125continue45605346011813210163・存在的问题及解决Configuration:123456-Win32DebugCompiling...123.cpp执彳亍cl.exeMS®-

11、G:UC^»MicrosoFtUisuolS