哈希查找 数据结构实验报告.doc
文本预览下载声明
南昌航空实验报告
课程名称：数据结构 实验名称：
班级：姓名：：
指导教师评定：签名:
题目：编程实现哈希表的造表和查找算法。
要求：用除留余数法构造哈希函数，用二次探测再散列解决冲突。
需求分析
用户可以根据自己的需求输入一个顺序表（哈希表）
通过用除留余数法构造哈希函数，并用开放地址的二次探测再散列解决冲突。
在经过排序后显示该哈希表。
程序执行的命令包括：
（1）创建哈希表 （2）输出哈希表 （3）二次探测再散列解决冲突
二、概要设计
⒈ 为实现上述算法，需要顺序表的抽象数据类型：
ADT Hash {
数据对象D：D是具有相同特征的数据元素的集合。各数据元素均含有类型相同，可唯一标识数据元素的关键字。
数据关系R：数据元素同属一个集合。
基本操作P:
Creathash(h)
操作结果：构造一个具有n个数据元素的哈希查找表h。
destroyhash(h)
初始条件：哈希查找表h存在。
操作结果：销毁哈希查找表h。
displayhash（h）
初始条件：哈希查找表h存在。
操作结果：显示哈希查找表h。
hash(h，k)
初始条件：哈希查找表h存在。
操作结果：通过除留余数法得到地址用k返回。
hash2 (i，k)
初始条件：哈希查找表h存在存在，i是除留余数法得到的地址。
操作结果：返回二次探测再散列解决冲突得到的地址k。
search (h，key)
初始条件：哈希查找表h存在。
操作结果：查找表h中的key，若查找成功，返回其地址，否则返回-1
insert (h，key)
初始条件：哈希查找表h存在。
操作结果：若表h中没有key，则在h中插入key。
search1(h, key,p)
初始条件：哈希查找表h存在。
操作结果：在表h中查找key，若没有，则返回p的插入的地址，否则返回-1。
}ADT Hash
2. 本程序有三个模块：
⑴ 主程序模块
main(){
初始化；
{
接受命令；
显示结果；
｝
｝
⑵ 创建hash表的模块：主要建立一个哈希表；
⑶解决冲突模块：利用开放地址的二次探测再散列解决冲突；
(4)输出哈希表模块：显示已创建哈希表。
三、详细设计
⒈元素类型，结点类型
typedef struct
{
int key;
}keytype;
typedef struct
{
keytype elem[100];
int length; /*当前的长度*/
int size; /*哈希表的总长*/
}hashtable;
/*全局变量*/
int a=0,b=0;
/*哈希函数*/
2.对抽象数据类型中的部分基本操作的伪码算法如下：
/*哈希函数*/
int hash(hashtable *h,int k)
{
return k%h-size;
}
/*二次探测再散列解决冲突*/
int hash2(int i,int t)
{ if(i%2==0)
t=t+pow(++a,2);
else
t=t-pow(++b,2);
return t;
}
/*创建哈希表*/
void creat(hashtable *h)
{ int i,j,key,t,p;
printf(input hash size and length:);
scanf(%d%d,h-size,h-length);
for(i=0;ih-size;i++)
h-elem[i].key=-1;
printf(input data:\n);
for(j=0;jh-length;j++)
{ scanf(%d,key);
p=hash(h,key);
if(h-elem[p].key==-1)
h-elem[p].key=key;
else
{ i=0;
t=p;
while(h-elem[p].key!=-1h-elem[p].key!=keyih-size/2)
{ p=hash2(i,t);
i++;
}
a=b=0;
h-elem[p].key=key;
}
}
}
/*查找哈希表中的元素，返回元素的地址，否则返回-1*/
int search(hashtable *h,int key)
{
显示全部