设计构造哈希表的完整算法.doc

一设计的目的与内容

通过本实验需要掌握构造哈希函数表,需要完成设计构造哈希表的完整算法,并求出平均查找长度。
2 实验内容
使用哈希函数:H(K)=3*K MOD 11
并采用开放地址法解决冲突,试在0到10的散列地址空间对关键字序列
( 22, 41, 53, 46, 30,13, 01,67)构造哈希函数表,并设计构造哈希表的完整算法,并求出平均查找长度。
二算法的基本思想
数据结构的设计
哈希函数 H ( key ) =3* key mod 11,哈希表的地址空间为 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未发生冲突。

开放地址法这个方法的基本思想是:当发生地址冲突时,按照某种方法继续探测哈希表中的其他存储单元,直到找到空位置为止。这个过程可用下式描述:
H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,……, k ( k ≤ m – 1))
其中: H ( key ) 为关键字 key 的直接哈希地址, m 为哈希表的长度, di 为每次再探测时的地址增量。采用这种方法时,首先计算出元素的直接哈希地址 H ( key ) ,如果该存储单元已被其他元素占用,则继续查看地址为 H ( key ) + d 2 的存储单元,如此重复直至找到某个存储单元为空时,将关键字为 key 的数据元素存放到该单元。增量 d 可以有不同的取法,并根据其取法有不同的称呼:
( 1 ) d i = 1 , 2 , 3 , ……线性探测再散列;
( 2 ) d i = 1^2 ,- 1^2 , 2^2 ,- 2^2 , k^2, -k^2……二次探测再散列;
( 3 ) d i = 伪随机序列伪随机再散列;
三源程序代码及测试结果
源程序代码
#include<>
#include<>
#define M 11
#define N 8
struct hterm
{
int key; //关键字值
int si; //散列次数
};
struct hterm hlist[M];
int i,adr,sum,d;
int x[N]={22,41,53,46,30,13,1,67}; //关键字赋值
float