数据结构实验9哈希查找

1、intkeynum;/记录的数据域,只有关键字一项1、实验目的(1)复习顺序查找、二分查找、分块查找的根本算法及适用场合；(2)掌握哈希查找的根本方法及适用场合,并能在解决实际问题时灵活应用；(3)稳固在散列查找时解决冲突的方法及特点.2、实验内容(1)哈希表查找的实现(用线性探测法解决冲突)；(2)能对哈希表进行插入和查找.3、实验要求(1)分析算法思想,利用 C(C+)语言完成程序设计.(2)上机调试通过实验程序.(3)输入数据,进行哈希插入和查找.(4)给出具体的算法分析,包括时间复杂度和空间复杂度等.(5)撰写实验报告.4、实验步骤与源程序实验步骤本程序共设计了五个函数来实现建表,显示

2、,查找,插入,删除这几个主要功能,然后设计主函数,串接程序,并进行调试,测试实验结果.源代码#include#include#include#include#include#defineMAXSIZE12/哈希表的最大容量,与所采用的哈希函数有关enumBOOLFalse,True;enumHAVEORNOTNULLKEY,HAVEKEY,DELKEY;脸希表元素的三种状态,没有记录、有记录、有过记录但已被删除typedefstruct/定义哈希表的结构intelemMAXSIZE;/数据元素体HAVEORNOTelemflagMAXSIZE;/元素状态标志,没有记录、有记录、有过记录但已被删

3、除intcount;/哈希表中当前元素的个数HashTable;typedefstructRecord;voidInitialHash(HashTable&);/初始化口口布表voidPrintHash(HashTable);/显示哈希米中的所有兀素BOOLSearchHash(HashTable,int,int&);/在哈希表中查找兀素BOOLInsertHash(HashTable&,Record);/在哈希表中插入兀素BOOLDeleteHash(HashTable&,Record);/在哈希表中删除兀素intHash(int);/哈希函数voidmain

4、()HashTableH;/声明哈希表 Hcharch,j=y;intposition,n,k;RecordR;BOOLtemp;InitialHash(H);while(j!=n)printf(nt哈希查找:printf(nt*);printf(nt*1建表*printf(nt*2-显示*printf(nt*3-查找*printf(nt*4-插入*printf(nt*5-删除*printf(nt*0-退出*););););););printf(nt*);printf(nnt 请输入菜单号：);scanf(%c,&ch);/输入操作选项switch(ch)case1:printf(n

5、请输入元素个数(10):);for(k=0;kn;k+)printf请输入第3d 个整数：,k+1;scanf(%d,&R.keynum);/输入要插入的记录temp=InsertHash(H,R);break;case2:if(H.count)/哈希表不空PrintHash(H);elseprintf(n 散列表为空表！n);break;case3:if(!H.count)printf(n 散列表为空表!n);/哈希表空elseprintf(n 请你输入要查找元素(int):);scanf(%d,&R.keynum);/输入待查记录的关键字temp=SearchHash(H,

6、R.keynum,position);/temp=True:记录查找成功；temp=False:没有找到待查记录if(temp)printf(n 查找成功该元素位置是%dn,position);elseprintf(n 本散列表没有该元素!n);break;break;printf(n 请输入要插入元素(int):);scanf(%d,&R.keynum);/temp=InsertHash(H,R);case4:if(H.count=MAXSIZE)/哈希表已满printf(n散列表已经满！n;输入要插入的记录/temp=True:记录插入成功；temp=False:已存在关键字相同的

7、记录default:j=n;printf(nt 欢送再次使用本程序,再见!n);voidInitialHash(HashTable&H)/inti;H.count=0;for(i=0;i=MAXSIZE)p=p%MAXSIZE;/if(p=p1)returnFalse;/素if(k=H.elemp&H.elemflagp=HAVEKEY)/returnTrue;elsereturnFalse;/inti;for(i=0;iMAXSIZE;i+)/显示哈希表中记录所在位置printf(%-4d,i);printf(n);for(i=0;iMAXSIZE;i+)/显布哈希表中记录值

8、if(H.elemflagi=HAVEKEY)printf(%-4d,H.elemi);elseprintf(%4c,);printf(ncount:%dn,H.count);/显示哈希表当前记录数p 指示插入位置,并返回 False求得哈希地址该位置中填有记录并且关键字不冲突处理方法：线性探测再散列循环搜索整个表已搜索完,没有找到待查元查找成功,p 指示待查元素位置查找不成功/查找不成功时插入元素 e 到开放定址哈希表 H 中,并返回 True,否那么返回 Falseintp;if(SearchHash(H,e.keynum,p)素returnFalse;elseH.elemflagp 尸

9、HAVEKEY;已有记录H.elemp=e.keynum;/H.count+;returnTrue;BOOLDeleteHash(HashTable&H,Recorde)/在查找成功时删除待删元素 e,intp;if(!SearchHash(H,e.keynum,p)returnFalse;else并返回 True,否那么返回/H.elemflagp 尸 DELKEY;被删除H.count-;returnTrue;intHash(intkn)return(kn%11);/表中已有与 e 有相同关键字的元设置标志为 HAVEKEY 表不该位置插入记录哈希表当前长度加一False表中不存在待删元素设置标志为 DELKEY 说明该元素已哈希表当前长度减一哈希函数：H(key)=keyMOD115、测试数据与实验结果(可以抓图粘贴)(1)菜单:(3)显示请输入菜单号：2)12345&78101135&7勺:uiint：S(4)查找请输入菜单号,3青你输入要查找元素(皿七门堂我成功该元素位置是才(5)插入请输入菜单号,4胃输入要插入元素无素插入成功,(6)删除请输入菜单号,5青你输入要删除元素Cnt八2删除成功t6、结果分析与实验体会本次实验是参考了范例程序,经过自己的改写,从而实现要求.先做简单的输出,一步步的再做其*MK二二二找一表示我人盘二