《数据结构实验9哈希查找》由会员分享，可在线阅读，更多相关《数据结构实验9哈希查找（8页珍藏版）》请在金锄头文库上搜索。
1、 算法设计与分析 实验报告 - 8 -1、 实验目的（1) 复习顺序查找、二分查找、分块查找的基本算法及适用场合；（2) 掌握哈希查找的基本方法及适用场合，并能在解决实际问题时灵活应用；（3) 巩固在散列查找时解决冲突的方法及特点。2、 实验内容（1) 哈希表查找的实现（用线性探测法解决冲突）；（2) 能对哈希表进行插入和查找。3、 实验要求（1) 分析算法思想，利用C（C+）语言完成程序设计。（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 elemflagMAXSI
3、ZE; / 元素状态标志，没有记录、有记录、有过记录但已被删除 int count; / 哈希表中当前元素的个数 HashTable;typedef struct int keynum; / 记录的数据域，只有关键字一项Record;void InitialHash(HashTable&); / 初始化哈希表void PrintHash(HashTable); / 显示哈希表中的所有元素BOOL SearchHash(HashTable,int,int&); / 在哈希表中查找元素BOOL InsertHash(HashTable&,Record); / 在哈希表中插入元素BOOL Delet
4、eHash(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 哈 希 查 找 ); printf(nt*); printf(nt* 1-建 表 *); printf(nt* 2-显 示 *); printf(nt* 3-查 找 *); printf(nt* 4-插 入 *); printf(nt*
5、 5-删 除 *); printf(nt* 0-退 出 *); printf(nt*); printf(nnt请输入菜单号：); scanf( %c,&ch); / 输入操作选项 switch(ch) case 1:printf(n请输入元素个数(10): ); scanf(%d,&n); 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)
6、; 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:记录查找成功；temp=False:没有找到待查记录 if(temp) printf(n查找成功该元素位置是 %dn,position); else printf(n本散列表没有该元素!n); break; c
7、ase 4:if(H.count=MAXSIZE) / 哈希表已满 printf(n散列表已经满!n); break; printf(n请输入要插入元素(int):); scanf(%d,&R.keynum); / 输入要插入的记录 temp=InsertHash(H,R); / temp=True:记录插入成功；temp=False:已存在关键字相同的记录 if(temp) printf(n元素插入成功!n); else printf(n元素插入失败，相同元素本散列表已经存在!n); break; case 5:printf(n请你输入 要删除元素(int):); scanf(%d,&R.k
8、eynum); / 输入要删除记录的关键字 temp=DeleteHash(H,R); / temp=True:记录删除成功；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;iMAXSIZE;i+) H.elemflagi=NULLKEY;void PrintHash(Hash
9、Table H) / 显示哈希表所有元素及其所在位置 int i; for(i=0;iMAXSIZE;i+) / 显示哈希表中记录所在位置 printf(%-4d,i); printf(n); for(i=0;iMAXSIZE;i+) / 显示哈希表中记录值 if(H.elemflagi=HAVEKEY) printf(%-4d,H.elemi); else printf(%4c, ); printf(ncount:%dn,H.count); / 显示哈希表当前记录数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+;
