《数据结构实验哈希查找》由会员分享，可在线阅读，更多相关《数据结构实验哈希查找（9页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析 试验报告- 1 -1、试验目的1)复习挨次查找、二分查找、分块查找的根本算法及适用场合；2)把握哈希查找的根本方法及适用场合，并能在解决实际问题时机敏应用；3)稳固在散列查找时解决冲突的方法及特点。2、试验内容1)哈希表查找的实现用线性探测法解决冲突；2)能对哈希表进展插入和查找。3、试验要求1)分析算法思想，利用CC+语言完成程序设计。2)上机调试通过试验程序。3)输入数据，进展哈希插入和查找。4)给出具体的算法分析，包括时间简单度和空间简单度等。5)撰写试验报告。4、试验步骤与源程序 试验步骤本程序共设计了五个函数来实现建表，显示，查找，插入，删除这几个主要功能，然后设计主
2、函数，串接程序，并进展调试，测试试验结果。 源代码 #include #include #include #include #include #define MAXSIZE 12/哈希表的最大容量，与所承受的哈希函数有关enum BOOLFalse,True;enum HAVEORNOTNULLKEY,HAVEKEY,DELKEY; /哈希表元素的三种状态，没有记录、有记录、有过记录但已被删除typedef struct/定义哈希表的构造 int elemMAXSIZE;/数据元素体HAVEORNOT elemflagMAXSIZE;/ 元素状态标志，没有记录、有记录、有过记录但已被删除int
3、 count;/ 哈希表中当前元素的个数HashTable; typedef structint keynum;/记录的数据域，只有关键字一项1 /8算法设计与分析 试验报告- 2 -Record;void InitialHash(HashTable&);/ 初始化哈希表void PrintHash(HashTable);/ 显示哈希表中的全部元素BOOL SearchHash(HashTable,int,int&);/ 在哈希表中查找元素BOOL InsertHash(HashTable&,Record);/ 在哈希表中插入元素BOOL DeleteHash(HashTable&,Recor
4、d);/ 在哈希表中删除元素int Hash(int);/ 哈希函数void main() HashTable H;/ 声明哈希表H char ch,j=”y”;int position,n,k; Record R;BOOL temp; 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(“n
5、t*“); printf(“nnt 请输入菜单号：“);scanf(“ %c“,&ch);/ 输入操作选项switch(ch)case ”1”:printf(“n 请输入元素个数(10): “); scanf(“%d“,&n);2 / 8算法设计与分析 试验报告- 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);elsepri
6、ntf(“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 查找成功该元素位置是 %dn“,position); elseprintf(“n 本散列表没有该元素!n“);break;case
7、”4”:if(H.count=MAXSIZE)/ 哈希表已满 printf(“n 散列表已经满!n“); break;printf(“n 请输入要插入元素(int):“);scanf(“%d“,&R.keynum);/ 输入要插入的记录temp=InsertHash(H,R);3 / 8算法设计与分析 试验报告- 4 -/ temp=True:记录插入成功；temp=False:已存在关键字一样的记录if(temp)printf(“n 元素插入成功!n“); elseprintf(“n 元素插入失败，一样元素本散列表已经存在!n“); break;case ”5”:printf(“n 请你输入
8、 要删除元素(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(“nt 欢送再次使用本程序，再见!n“);void InitialHash(HashTable &H)/ 哈希表初始化int i; H.count=0;for(i=0;iMAXSIZE;i+)H.elemflag
9、i=NULLKEY;void PrintHash(HashTable H)/ 显示哈希表全部元素及其所在位4 / 8算法设计与分析 试验报告- 5 -置int i;for(i=0;iMAXSIZE;i+)/ 显示哈希表中记录所在位置printf(“%-4d“,i);printf(“n“);for(i=0;i=MAXSIZE)p=p%MAXSIZE;/循环搜寻if(p=p1)return False;/ 整个表已搜寻完，没有找到待查元素if(k=H.elemp&H.elemflagp=HAVEKEY)/ 查找成功，p 指示待查元素位置return True;elsereturn False;/
10、查找不成功BOOL InsertHash(HashTable &H,Record e)5 / 8算法设计与分析 试验报告- 6 - / 查找不成功时插入元素e 到开放定址哈希表H 中，并返回True，否那么返回False int p;if(SearchHash(H,e.keynum,p)/ 表中已有与 e 有一样关键字的元素return False; else H.elemflagp=HAVEKEY;/ 设置标志为HAVEKEY，表示该位置已有记录H.elemp=e.keynum;/ 插入记录H.count+;/ 哈希表当前长度加一return True;BOOL DeleteHash(Has
11、hTable &H,Record e) / 在查找成功时删除待删元素e，并返回True，否那么返回False int p;if(!SearchHash(H,e.keynum,p)/ 表中不存在待删元素return False;else H.elemflagp=DELKEY;/ 设置标志为DELKEY，说明该元素已被删除H.count-;/ 哈希表当前长度减一return True;int Hash(int kn)return (kn%11); / 哈希函数：H(key)=key MOD 115、测试数据与试验结果可以抓图粘贴6 / 8算法设计与分析 试验报告- 7 -（1） 菜单：（2） 建表（3） 显示（4） 查找（5） 插入（6） 删除7 / 8算法设计与分析 试验报告- 8 -6、结果分析与试验体会本次试验是参考了范例程序，经过自己的改写，从而实现要求。先做简洁的输出，一步步的再做其它格式的设置。这次的试验我们要做的是哈希查找，要求我们复习挨次查找，二分查找，分块查找等根本算法，进一步稳固散列查找时解决冲突的方法和特点，在调试程序的过程中，遇到很多问题，但还是都得以解决。
