数据结构 实验9 哈希查找

1、 算法设计与分析 实验报告 - 8 -1、 实验目的（1) 复习顺序查找、二分查找、分块查找的基本算法及适用场合；（2) 掌握哈希查找的基本方法及适用场合，并能在解决实际问题时灵活应用；（3) 巩固在散列查找时解决冲突的方法及特点。2、 实验内容（1) 哈希表查找的实现（用线性探测法解决冲突）；（2) 能对哈希表进行插入和查找。3、 实验要求（1) 分析算法思想，利用C（C+）语言完成程序设计。（2) 上机调试通过实验程序。（3) 输入数据，进行哈希插入和查找。（4) 给出具体的算法分析，包括时间复杂度和空间复杂度等。（5) 撰写实验报告。4、 实验步骤与源程序 实验步骤本程序共设计了五个函数

2、来实现建表，显示，查找，插入，删除这几个主要功能，然后设计主函数，串接程序，并进行调试，测试实验结果。 源代码#include <dos.h>#include <conio.h>#include <math.h>#include <stdio.h>#include <stdlib.h>#define MAXSIZE 12 /哈希表的最大容量，与所采用的哈希函数有关enum BOOLFalse,True;enum HAVEORNOTNULLKEY,HAVEKEY,DELKEY; /哈希表元素的三种状态，没有记录、有记录、有过记录但已被删

3、除typedef struct /定义哈希表的结构 int elemMAXSIZE; /数据元素体 HAVEORNOT elemflagMAXSIZE; / 元素状态标志，没有记录、有记录、有过记录但已被删除 int count; / 哈希表中当前元素的个数 HashTable;typedef struct int keynum; / 记录的数据域，只有关键字一项Record;void InitialHash(HashTable&); / 初始化哈希表void PrintHash(HashTable); / 显示哈希表中的所有元素BOOL SearchHash(HashTable,in

4、t,int&); / 在哈希表中查找元素BOOL InsertHash(HashTable&,Record); / 在哈希表中插入元素BOOL DeleteHash(HashTable&,Record); / 在哈希表中删除元素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 哈 希

5、查 找 "); 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(&

6、quot; %c",&ch); / 输入操作选项 switch(ch) case '1':printf("n请输入元素个数(<10): "); scanf("%d",&n); printf("n"); for( k=0;k<n;k+) printf("请输入第%3d个整数: ",k+1);scanf("%d",&R.keynum); / 输入要插入的记录 temp=InsertHash(H,R); ; break; case '

7、;2':if(H.count) / 哈希表不空 PrintHash(H); else printf("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:记录查

8、找成功；temp=False:没有找到待查记录 if(temp) printf("n查找成功该元素位置是 %dn",position); else printf("n本散列表没有该元素!n"); break; case '4':if(H.count=MAXSIZE) / 哈希表已满 printf("n散列表已经满!n"); break; printf("n请输入要插入元素(int):"); scanf("%d",&R.keynum); / 输入要插入的记录 temp=In

9、sertHash(H,R); / temp=True:记录插入成功；temp=False:已存在关键字相同的记录 if(temp) printf("n元素插入成功!n"); else printf("n元素插入失败，相同元素本散列表已经存在!n"); break; case '5':printf("n请你输入 要删除元素(int):"); scanf("%d",&R.keynum); / 输入要删除记录的关键字 temp=DeleteHash(H,R); / temp=True:记录删除成功

10、；temp=False:待删记录不存在 if(temp) printf("n删除成功!n"); else printf("n删除元素不在散列表中!n"); break; default: j='n' printf("nt欢迎再次使用本程序，再见!n");void InitialHash(HashTable &H) / 哈希表初始化 int i; H.count=0; for(i=0;i<MAXSIZE;i+) H.elemflagi=NULLKEY;void PrintHash(HashTable H)

11、/ 显示哈希表所有元素及其所在位置 int i; for(i=0;i<MAXSIZE;i+) / 显示哈希表中记录所在位置 printf("%-4d",i); printf("n"); for(i=0;i<MAXSIZE;i+) / 显示哈希表中记录值 if(H.elemflagi=HAVEKEY) printf("%-4d",H.elemi); else printf("%4c",' '); printf("ncount:%dn",H.count); / 显示哈希表

12、当前记录数BOOL SearchHash(HashTable H,int k,int &p) / 在开放定址哈希表H中查找关键字为k的数据元素，若查找成功，以p指示 / 待查数据元素在表中的位置，并返回True；否则，以p指示插入位置，并返回False int p1; p1=p=Hash(k); / 求得哈希地址 while(H.elemflagp=HAVEKEY&&k!=H.elemp) / 该位置中填有记录并且关键字不相等 p+; / 冲突处理方法：线性探测再散列 if(p>=MAXSIZE) p=p%MAXSIZE; / 循环搜索 if(p=p1) retu

13、rn False; / 整个表已搜索完，没有找到待查元素 if(k=H.elemp&&H.elemflagp=HAVEKEY) / 查找成功，p指示待查元素位置 return True; else return False; / 查找不成功 BOOL InsertHash(HashTable &H,Record e) / 查找不成功时插入元素e到开放定址哈希表H中，并返回True，否则返回False int p; if(SearchHash(H,e.keynum,p) / 表中已有与e有相同关键字的元素 return False; else H.elemflagp=HA

14、VEKEY; / 设置标志为HAVEKEY，表示该位置已有记录 H.elemp=e.keynum; / 插入记录 H.count+; / 哈希表当前长度加一 return True; BOOL DeleteHash(HashTable &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); / 哈