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

《程序设计与算法分析》,需要完成设计构造哈希表的完整算法,并求出平均查找长度。2实验内容使用哈希函数:H(K)=3*KMOD11并采用开放地址法解决冲突,试在0到10的散列地址空间对关键字序列(22,41,53,46,30,13,01,67)构造哈希函数表,并设计构造哈希表的完整算法,并求出平均查找长度。(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未发生冲突。:当发生地址冲突时,按照某种方法继续探测哈希表中的其他存储单元,直到找到空位置为止。这个过程可用下式描述: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=伪随机序列伪随机再散列;#include<>#include<>#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;i<M;i++){hlist[i].key=0;hlist[i].si=0;}for(i=0;i<N;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);hl