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

南昌航空大学实验报告课程名称： 数据结构 实验名称： 实验九 查找 班 级： 学生姓名： 学号： 指导教师评定： 签 名: 题目：编程实现哈希表的造表和查找算法。要求：用除留余数法构造哈希函数，用二次探测再散列解决冲突。一、 需求分析1. 用户可以根据自己的需求输入一个顺序表（哈希表）2. 通过用除留余数法构造哈希函数，并用开放地址的二次探测再散列解决冲突。3. 在经过排序后显示该哈希表。4. 程序执行的命令包括：（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，若查找成功，返回其地址，否则返回-1insert (&h，key)初始条件：哈希查找表h存在。操作结果：若表h中没有key，则在h中插入key。 search1(h, key,&p)初始条件：哈希查找表h存在。操作结果：在表h中查找key，若没有，则返回p的插入的地址，否则返回-1。 ADT Hash2. 本程序有三个模块： 主程序模块 main()初始化；接受命令；显示结果； 创建hash表的模块：主要建立一个哈希表；解决冲突模块：利用开放地址的二次探测再散列解决冲突；(4)输出哈希表模块：显示已创建哈希表。三、详细设计元素类型，结点类型typedef struct int key;keytype;typedef struct keytype elem100; 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;isize;i+) h-elemi.key=-1; printf(input data:n); for(j=0;jlength;j+) scanf(%d,&key); p=hash(h,key); if(h-elemp.key=-1) h-elemp.key=key; else i=0; t=p; while(h-elemp.key!=-1&h-elemp.key!=key&isize/2) p=hash2(i,t); i+; a=b=0; h-elemp.key=key; /*查找哈希表中的元素，返回元素的地址，否则返回-1*/int search(hashtable *h,int key) int p,t,i=0; p=hash(h,key); t=p; while(h-elemp.key!=-1&h-elemp.key!=key&isize/2) p=hash2(i,t); i+; if(h-elemp.key=key) return p; else return(-1);/*查找哈希表的元素，返回p的插入的位置*/void search1(hashtable *h,int key,int *p) int t,s,c=0; t=hash(h,key); s=t; while(h-elemt.key!=-1&h-elemt.key!=key&csize/2) t=hash2(c,s); c+; if(h-elemt.key=key) *p=t; else t=-1; *p=t; /*插入数据元素到开放地址哈希表中*/void insert(hashtable *h,int key) int p; p=search(h,key); if(p!=-1) printf(the location is:%dn,p); else search1(h,key,&p); +h-size; +h-length; h-elemh-size.key=key; /*输出哈希表*/void printhash(hashtable *h) int i; for(i=0;isize;i+) printf(%-4.2d,i); printf(n); for(i=0;isize;i+) printf(-); printf(n); for(i=0;isize;i+) printf(%-4.2d,h-elemi.key);3.主函数和其他函数的伪码算法/*主函数*/void main() hashtable t; int i,key,key1,c; creat(&t); printf(output the hash:nn); printhash(&t); printf(nncurrent the length is:%dn,t.length); printf(ninput a search key:); scanf(%d,&key); c=search(&t,key); if(c!=-1) printf(its location is:%dn,c); else printf(cant search the key!n); printf(nnadd the key:); scanf(%d,&key1); insert(&t,key1); printf(n); for(i=0;it.size;i+) printf(%-4.2d,i); printf(n); for(i=0;i2*t.size;i+) printf(-); printf(n); for(i=0;isize和h-length有时会用错。4. 算法的时空分析各操作的算法时间复杂度比较合理hash，hash2为O(1)；creat， search，search1，insert，printhash为O(n), 注：n为哈希表的长度。（注：也可用平均查找长度ASL）5.本次实验采用数据抽象的程序设计方法，将程序化为三层次结构，设计时思路清晰，使调试也较顺利，各模块有较好的可重用性。五、用户手册 本程序的运行环境为windows xp操作系统，并且在TC2.0中运行，执行文件为Exp9.c；2. 进入演示程序后，完成编译，再点击超级工具集里的中文DOS环境运行选项，进入DOS环境中，用户根据需求键入相应的数据，可以看到相应的结果。六、测试结果在dos下输入数据元素： 88 64 24 75 02 15 68 54 28 39 61并且查找数据元素28和插入数据元素27则在dos界面输入如图所示：七、附录：源程序 #include stdio.h#include math.h#define SIZE 100typedef struct int key;keytype;typedef struct keytype elem100; int length; /*当前的长度*/ int size; /*哈希表的总长*/hashtable;/*全局变量*/int a=0,b=0;/*哈希函数*/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;isize;i+) h-elemi.key=-1; printf(input data:n); for(j=0;jlength;j+) scanf(%d,&key); p=hash(h,key); if(h-elemp.key=-1) h-elemp.key=key; else i=0; t=p; while(h-elemp.key!=-1&h-elemp.key!=key&isize/2) p=hash2(i,t); i+; a=b=0; h-elemp.key=key; /*查找哈希表中的元素，返回元素的地址，否则返回-1*/int search(hashtable *h,int key) int p,t,i=0; p=hash(h,key); t=p; while(h-elemp.key!=-1&h-elemp.key!=key&isize/2) p=hash2(i,t); i+; if(h-elemp.key=key) return p; else return(-1);/*查找哈希表的元素，返回p的插入的位置*/void search1(hashtable *h,int key,int *p) int t,s,c=0; t=hash(h,key); s=t; while(h-elemt.key!=-1&h-elemt.key!=key&csize/2) t=hash2(c,s); c+; if(h-elemt.key=key) *p=t; else t=-1; *p=t; /*插入数据元素到开放地址哈希表中*/void insert(hashtable *h,int key) int p; p=search(h,key); if(p!=-1) printf(the location is:%dn,p); else search1(h,key,&p); +h-size; +h-length; h-elemh-size.key=key; /*输出哈希表*/void printhash(hashtable *h) int i; for(i=0;isize;i+) printf(%-4.2d,i); printf(n); for(i=0;isize;i+) printf(-); printf(n); for(i=0;isize;i+) printf(%-4.2d,h-elemi.key);/*主函数*/void main() hashtable t; int i,key,key1,c; creat(&t); printf(output the hash:nn); printhash(&t); printf(nncurrent the length is:%dn,t.length); printf(ninput a search key:); scanf(%d,&key); c=search(&t,key); if(c!=-1) printf(its location is:%dn,c); else printf(cant search the key!n); printf(nnadd the key:); scanf(%