数据结构实验9哈希查找

1、实验目的（1）复习顺序查找、二分查找、分块查找的基本算法及适用场合；（2）掌握哈希查找的基本方法及适用场合，并能在解决实际问题时灵活应用；（3）巩固在散列查找时解决冲突的方法及特点。2、实验内容（1）哈希表查找的实现（用线性探测法解决冲突）；（2）能对哈希表进行插入和查找。3、实验要求（1）分析算法思想，利用C（C+）语言完成程序设计。（2）上机调试通过实验程序。（3）输入数据，进行哈希插入和查找。（4）给出具体的算法分析，包括时间复杂度和空间复杂度等。（5）撰写实验报告。4、实验步骤与源程序实验步骤本程序共设计了五个函数来实现建表，显示，查找，插入，删除这几个主要功能，然后设计主 函数，串接程序，并进行调试，测试实验结果。源代码#inelude #in elude #in elude #in elude #in elude #defi ne MAXSIZE 12enum BOOLFalse,True;enum HAVEORNOTNULLKEY,HAVEKEY,DELKEY;录、有过记录但已被删除typedef struct int elemMAXSIZE;HAVEORNOT elemflagMAXSIZE;录但已被删除int count;HashTable;typedef struct int keynum;Record;void Ini tialHash(HashTable &);void Prin tHash(HashTable);BOOL SearchHash(HashTable,i nt,i nt&);BOOL In sertHash(HashTable &,Record);哈希表的最大容量，与所采用的哈希函数有关哈希表元素的三种状态，没有记录、有记定义哈希表的结构数据元素体/元素状态标志，没有记录、有记录、有过记哈希表中当前元素的个数/记录的数据域，只有关键字一项/初始化哈希表/显示哈希表中的所有元素/在哈希表中查找元素/在哈希表中插入元素BOOL DeleteHash(HashTable&,Record); / 在哈希表中删除元素哈希函数int Hash(i nt);void mai n() HashTable H;声明哈希表Hchar ch,j = y;int positio n,n ,k;Record R;BOOL temp;In itialHash(H);while(j!二n)printf(nt哈 希查找);prin tf(nt*H);prin tf(nt*1-建表*);prin tf(nt*2显示*);prin tf(nt*3-杳找*);prin tf(nt*4插入*);prin tf(nt*5删除*);prin tf(nt*0退出*);prin tf(nt*H);printf（nnt请输入菜单号：）;sca nf( %c,&ch);/输入操作选项switch(ch)case 1:pri ntf(n 请输入元素个数(10):);sca nf(%d,&n);prin tf(n);for( k=O;k n ;k+) printf(请输入第%3d个整数:,k+1);scanf(%d,&R.keynum); /输入要插入的记录 temp=I nsertHash(H,R);break;case 2:if(H.co unt)哈希表不空Prin tHash(H);elsepri ntf(n散列表为空表!n);break;case 3:if(!H.cou nt)pri ntf(n散列表为空表!n);哈希表空else printf(n请你输入要查找元素(int):);scanf(%d,&R.keynum);/输入待查记录的关键字temp二SearchHash(H,R.ke yn um,positi on);/ temp二True记录查找成功；temp二False没有找到待查记录if(temp)printf(n查找成功该元素位置是dnposition);elseprin tf(n本散列表没有该元素!n); break;哈希表已满/输入要插入的记录case 4:if(H.cou nt二二MAXSIZE) pri ntf(n散列表已经满!n);break; pri ntf(n请输入要插入元素(in t):);sca nf(%d,&R.key num);temp=I nsertHash(H,R);/ temp二True记录插入成功；temp二False:已存在关键字相同的记录if(temp)prin tf(n元素插入成功!n);elsepri ntf(n元素插入失败，相同元素本散列表已经存在!n);break;case 5:printf(n请你输入要删除元素(int):);seanf(%d,&R.keynum);/输入要删除记录的关键字temp二DeleteHash(H,R);/ temp二True记录删除成功；temp二False待删记录不存在if(temp)pri ntf(n 删除成功!n);elseprin tf(n删除元素不在散列表中!n);break;default: j = n;pri ntf(nt欢迎再次使用本程序，再见!n);void In itialHash(HashTble &H)int i;H.cou nt=O;for(i=0;iMAXSIZE;i + +) H.elemflagi二NULLKEY;void Pri ntHash(HashTable H)置int i;for(i=0;iMAXSIZE;i + +)pri ntf(%-4d,i);pri ntf(n);for(i=0;i= 5引-Fs专r专r-习-FhvKI-L工 檢sffiffisH Amx12 3 4 5第第第第第 AAAAA A-刖一別一別一讯八旦 青青青主星月(3) 显示请输入菜单号=20123456789101135679c q un t ： 5(4) 查找请输入菜单号：3请你输入要查找元素 ：3查找成功该元素位置是3(5)插入请输入菜单号：4请输入要插入兀素元素插入成功辛(6)删除请输入菜单号：5请你输入要删除元素 = 2删除成功？6、结果分析与实验体会本次实验是参考了范例程序，经过自己的改写，从而实现要求。先做简单的输出，一步步的再做其它格式的设置。这次的实验我们要做的是哈希查找，要求我们复习顺序查找，二分查找，分块查找等基本算法，进一步巩固散列查找时解决冲突的方法和特点，在调试程序的过程中，遇到很多 问题，但还是都得以解决。