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

《程序设计与算法分析》实验报告一设计的目的与内容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,46,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+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)，如果该存储单元已被其他元素占用，则继续查看地址为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.源程序代码#includeiostream.h#includeiomanip.h#defineM11#defineN8structhterm{intkey;//关键字值intsi;//散列次数};structhtermhlist[M];inti,adr,sum,d;intx[N]={22,41,53,46,30,13,1,67};//关键字赋值floataverage;voidchash()//创建哈希表{for(i=0;iM;i++){hlist[i].key=0;hlist[i].si=0;}for(i=0;iN;i++){sum=0;adr=(3*x[i])%M;d=adr;if(hlist[adr].key==0){hlist[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;iM;i++)coutsetw(4)i;coutendl;cout哈希表关键字：;for(i=0;iM;i++)coutsetw(4)hlist[i].key;coutendl;cout搜索长度：;for(i=0;iM;i++)coutsetw(4)hlist[i].si;coutendl;average=0;for(i=0;iM;i++)average=average+hlist[i].si;average=average/N;cout平均搜索长度：ASL(N)=averageendl;}voidmain(){chash();dhash();}2.测试结果3.存在的问题及解决解决方法：structhterm{intkey;//关键字值intsi;//散列次数}}“}”后面少了一个“；”。四分析与讨论（1）线性探测再散列：22％11=0；41％11=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未发生冲突。五心的体会在这次数据结构设计中遇到了很多实际性的问题，在实际设计才发现，书本上理论性的东西和在实际运用中的还是有一定的出入，随意有些问题要不断地更正以前的错误思维。通过这次设计，我懂得了学习的重要性，了解到理论知识与实践相结合的重要意义，学会了坚持、耐心和努力，这将为自己以后的学习和工作做出了最好的榜样。我觉得学习我们最重要的是要把自己平时学习的东西应用到世界中。