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

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，哈希表的地址空间为 0 10，对关键字序列（ 22, 41, 53, 46, 3

2、0,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发生

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

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

5、N 8struct htermint key; /关键字值int si; /散列次数;struct hterm hlistM;int i,adr,sum,d;int xN=22,41,53,46,30,13,1,67; /关键字赋值float average;void chash() /创建哈希表for (i=0;i<M;i+)hlisti.key=0;hlisti.si=0;for (i=0;i<N;i+) sum=0;adr=(3*xi)%M;d=adr;if (hlistadr.key=0)hlistadr.key=xi;hlistadr.si=1;elsedo /冲突处理d

6、=(d+1)%M;sum=sum+1;while (hlistd.key!=0);hlistd.key=xi;hlistd.si=sum+1;void dhash() /输出哈希表cout <<" 哈希表地址："for(i=0;i<M;i+)cout << setw(4) <<i;cout << endl;cout<<"哈希表关键字："for (i=0;i<M;i+)cout<< setw(4) << hlisti.key;cout << endl

7、;cout << " 搜索长度："for (i=0;i<M;i+)cout << setw(4) << hlisti.si;cout << endl;average=0;for (i=0;i<M;i+)average=average+hlisti.si;average=average/N;cout << "平均搜索长度： ASL("<< N <<")="<< average << endl;void main()ch

8、ash();dhash(); 2. 测试结果3. 存在的问题及解决解决方法：struct htermint key; /关键字值int si; /散列次数“”后面少了一个“； ”。四 分析与讨论（ 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未发生冲突。五 心的体会在这次数据结构设计中遇到了很多实际性的问题，在实际设计才发现，书本上理论性的东西和在实际运用中的还是有一定的出入，