数据结构-实验9-哈希查找

《算法设计与分析》实验报告-1-1、实验目的（1)复习顺序查找、二分查找、分块查找的基本算法及适用场合；（2)掌握哈希查找的基本方法及适用场合，并能在解决实际问题时灵活应用；（3)巩固在散列查找时解决冲突的方法及特点。2、实验内容（1)哈希表查找的实现（用线性探测法解决冲突）；（2)能对哈希表进行插入和查找。3、实验要求（1)分析算法思想，利用C（C++）语言完成程序设计。（2)上机调试通过实验程序。（3)输入数据，进行哈希插入和查找。（4)给出具体的算法分析，包括时间复杂度和空间复杂度等。（5)撰写实验报告。4、实验步骤与源程序⑴实验步骤本程序共设计了五个函数来实现建表，显示，查找，插入，删除这几个主要功能，然后设计主函数，串接程序，并进行调试，测试实验结果。⑵源代码#includedos.h#includeconio.h#includemath.h#includestdio.h#includestdlib.h#defineMAXSIZE12//哈希表的最大容量，与所采用的哈希函数有关enumBOOL{False,True};enumHAVEORNOT{NULLKEY,HAVEKEY,DELKEY};//哈希表元素的三种状态，没有记录、有记录、有过记录但已被删除typedefstruct//定义哈希表的结构{intelem[MAXSIZE];//数据元素体HAVEORNOTelemflag[MAXSIZE];//元素状态标志，没有记录、有记录、有过记录但已被删除intcount;//哈希表中当前元素的个数}HashTable;typedefstruct{intkeynum;//记录的数据域，只有关键字一项《算法设计与分析》实验报告-2-}Record;voidInitialHash(HashTable&);//初始化哈希表voidPrintHash(HashTable);//显示哈希表中的所有元素BOOLSearchHash(HashTable,int,int&);//在哈希表中查找元素BOOLInsertHash(HashTable&,Record);//在哈希表中插入元素BOOLDeleteHash(HashTable&,Record);//在哈希表中删除元素intHash(int);//哈希函数voidmain(){HashTableH;//声明哈希表Hcharch,j='y';intposition,n,k;RecordR;BOOLtemp;InitialHash(H);while(j!='n'){printf(\n\t哈希查找);printf(\n\t**************************************);printf(\n\t*1-----建表*);printf(\n\t*2-----显示*);printf(\n\t*3-----查找*);printf(\n\t*4-----插入*);printf(\n\t*5-----删除*);printf(\n\t*0-----退出*);printf(\n\t**************************************);printf(\n\n\t请输入菜单号：);scanf(%c,&ch);//输入操作选项switch(ch){case'1':printf(\n请输入元素个数(10):);scanf(%d,&n);《算法设计与分析》实验报告-3-printf(\n);for(k=0;kn;k++){printf(请输入第%3d个整数:,k+1);scanf(%d,&R.keynum);//输入要插入的记录temp=InsertHash(H,R);};break;case'2':if(H.count)//哈希表不空PrintHash(H);elseprintf(\n散列表为空表!\n);break;case'3':if(!H.count)printf(\n散列表为空表!\n);//哈希表空else{printf(\n请你输入要查找元素(int):);scanf(%d,&R.keynum);//输入待查记录的关键字temp=SearchHash(H,R.keynum,position);//temp=True:记录查找成功；temp=False:没有找到待查记录if(temp)printf(\n查找成功该元素位置是%d\n,position);elseprintf(\n本散列表没有该元素!\n);}break;case'4':if(H.count==MAXSIZE)//哈希表已满{printf(\n散列表已经满!\n);break;}printf(\n请输入要插入元素(int):);scanf(%d,&R.keynum);//输入要插入的记录temp=InsertHash(H,R);《算法设计与分析》实验报告-4-//temp=True:记录插入成功；temp=False:已存在关键字相同的记录if(temp)printf(\n元素插入成功!\n);elseprintf(\n元素插入失败，相同元素本散列表已经存在!\n);break;case'5':printf(\n请你输入要删除元素(int):);scanf(%d,&R.keynum);//输入要删除记录的关键字temp=DeleteHash(H,R);//temp=True:记录删除成功；temp=False:待删记录不存在if(temp)printf(\n删除成功!\n);elseprintf(\n删除元素不在散列表中!\n);break;default:j='n';}}printf(\n\t欢迎再次使用本程序，再见!\n);}voidInitialHash(HashTable&H){//哈希表初始化inti;H.count=0;for(i=0;iMAXSIZE;i++)H.elemflag[i]=NULLKEY;}voidPrintHash(HashTableH){//显示哈希表所有元素及其所在位《算法设计与分析》实验报告-5-置inti;for(i=0;iMAXSIZE;i++)//显示哈希表中记录所在位置printf(%-4d,i);printf(\n);for(i=0;iMAXSIZE;i++)//显示哈希表中记录值if(H.elemflag[i]==HAVEKEY)printf(%-4d,H.elem[i]);elseprintf(%4c,'');printf(\ncount:%d\n,H.count);//显示哈希表当前记录数}BOOLSearchHash(HashTableH,intk,int&p){//在开放定址哈希表H中查找关键字为k的数据元素，若查找成功，以p指示//待查数据元素在表中的位置，并返回True；否则，以p指示插入位置，并返回Falseintp1;p1=p=Hash(k);//求得哈希地址while(H.elemflag[p]==HAVEKEY&&k!=H.elem[p])//该位置中填有记录并且关键字不相等{p++;//冲突处理方法：线性探测再散列if(p=MAXSIZE)p=p%MAXSIZE;//循环搜索if(p==p1)returnFalse;//整个表已搜索完，没有找到待查元素}if(k==H.elem[p]&&H.elemflag[p]==HAVEKEY)//查找成功，p指示待查元素位置returnTrue;elsereturnFalse;//查找不成功}BOOLInsertHash(HashTable&H,Recorde)《算法设计与分析》实验报告-6-{//查找不成功时插入元素e到开放定址哈希表H中，并返回True，否则返回Falseintp;if(SearchHash(H,e.keynum,p))//表中已有与e有相同关键字的元素returnFalse;else{H.elemflag[p]=HAVEKEY;//设置标志为HAVEKEY，表示该位置已有记录H.elem[p]=e.keynum;//插入记录H.count++;//哈希表当前长度加一returnTrue;}}BOOLDeleteHash(HashTable&H,Recorde){//在查找成功时删除待删元素e，并返回True，否则返回Falseintp;if(!SearchHash(H,e.keynum,p))//表中不存在待删元素returnFalse;else{H.elemflag[p]=DELKEY;//设置标志为DELKEY，表明该元素已被删除H.count--;//哈希表当前长度减一returnTrue;}}intHash(intkn){return(kn%11);}//哈希函数：H(key)=keyMOD115、测试数据与实验结果（可以抓图粘贴）《算法设计与分析》实验报告-7-（1）菜单：（2）建表（3）显示（4）查找（5）插入（6）删除《算法设计与分析》实验报告-8-6、结果分析与实验体会本次实验是参考了范例程序，经过自己的改写，从而实现要求。先做简单的输出，一步步的再做其它格式的设置。这次的实验我们要做的是哈希查找，要求我们复习顺序查找，二分查找，分块查找等基本算法，进一步巩固散列查找时解决冲突的方法和特点，在调试程序的过程中，遇到很多问题，但还是都得以解决。