哈希查找_数据结构实验报告

《哈希查找_数据结构实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、南昌航空大学实验报告课程名称：数据结构实验名称：实验九查找班级：学生姓名：学号：指导教师评定：签名:题目：编程实现哈希表的造表和查找算法。要求：用除留余数法构造哈希函数，用二次探测再散列解决冲突。一、需求分析1.用户可以根据自己的需求输入一个顺序表（哈希表）2.通过用除留余数法构造哈希函数，并用开放地址的二次探测再散列解决冲突。3.在经过排序后显示该哈希表。4.程序执行的命令包括：（1）创建哈希表（2）输出哈希表（3）二次探测再散列解决冲突二、概要设计⒈为实现上述算法，需要顺序表的抽象数据类型：ADTHas

2、h{数据对象D：D是具有相同特征的数据元素的集合。各数据元素均含有类型相同，可唯一标识数据元素的关键字。数据关系R：数据元素同属一个集合。基本操作P:Creathash(&h)操作结果：构造一个具有n个数据元素的哈希查找表h。destroyhash(&h)初始条件：哈希查找表h存在。操作结果：销毁哈希查找表h。displayhash（h）初始条件：哈希查找表h存在。操作结果：显示哈希查找表h。hash(h，&k)初始条件：哈希查找表h存在。操作结果：通过除留余数法得到地址用k返回。hash2(i，&k)初始

3、条件：哈希查找表h存在存在，i是除留余数法得到的地址。操作结果：返回二次探测再散列解决冲突得到的地址k。search(h，key)初始条件：哈希查找表h存在。10操作结果：查找表h中的key，若查找成功，返回其地址，否则返回-1insert(&h，key)初始条件：哈希查找表h存在。操作结果：若表h中没有key，则在h中插入key。search1(h,key,&p)初始条件：哈希查找表h存在。操作结果：在表h中查找key，若没有，则返回p的插入的地址，否则返回-1。}ADTHash2.本程序有三个模块：⑴主

4、程序模块main(){初始化；{接受命令；显示结果；｝｝⑵创建hash表的模块：主要建立一个哈希表；⑶解决冲突模块：利用开放地址的二次探测再散列解决冲突；(4)输出哈希表模块：显示已创建哈希表。三、详细设计⒈元素类型，结点类型typedefstruct{intkey;}keytype;typedefstruct{keytypeelem[100];intlength;/*当前的长度*/intsize;/*哈希表的总长*/}hashtable;/*全局变量*/inta=0,b=0;/*哈希函数*/2.对抽象数据

5、类型中的部分基本操作的伪码算法如下：/*哈希函数*/inthash(hashtable*h,intk){returnk%h->size;}10/*二次探测再散列解决冲突*/inthash2(inti,intt){if(i%2==0)t=t+pow(++a,2);elset=t-pow(++b,2);returnt;}/*创建哈希表*/voidcreat(hashtable*h){inti,j,key,t,p;printf("inputhashsizeandlength:");scanf("%d%d",&h-

6、>size,&h->length);for(i=0;isize;i++)h->elem[i].key=-1;printf("inputdata:");for(j=0;jlength;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!=-1&&h->elem[p].key!=key&&isize/2){p=has

7、h2(i,t);i++;}a=b=0;h->elem[p].key=key;}}}/*查找哈希表中的元素，返回元素的地址，否则返回-1*/intsearch(hashtable*h,intkey){intp,t,i=0;p=hash(h,key);t=p;10while(h->elem[p].key!=-1&&h->elem[p].key!=key&&isize/2){p=hash2(i,t);i++;}if(h->elem[p].key==key)returnp;elsereturn(-1);}/

8、*查找哈希表的元素，返回p的插入的位置*/voidsearch1(hashtable*h,intkey,int*p){intt,s,c=0;t=hash(h,key);s=t;while(h->elem[t].key!=-1&&h->elem[t].key!=key&&csize/2){t=hash2(c,s);c++;}if(h->elem[t].key==key)*p=t;else{t=-1;*p=t