数据结构 实验9 哈希查找.doc

算法设计与分析 实验报告 - 8 -1、 实验目的（1) 复习顺序查找、二分查找、分块查找的基本算法及适用场合；（2) 掌握哈希查找的基本方法及适用场合，并能在解决实际问题时灵活应用；（3) 巩固在散列查找时解决冲突的方法及特点。2、 实验内容（1) 哈希表查找的实现（用线性探测法解决冲突）；（2) 能对哈希表进行插入和查找。3、 实验要求（1) 分析算法思想，利用C（C+）语言完成程序设计。（2) 上机调试通过实验程序。（3) 输入数据，进行哈希插入和查找。（4) 给出具体的算法分析，包括时间复杂度和空间复杂度等。（5) 撰写实验报告。4、 实验步骤与源程序 实验步骤本程序共设计了五个函数来实现建表，显示，查找，插入，删除这几个主要功能，然后设计主函数，串接程序，并进行调试，测试实验结果。 源代码#include #include #include #include #include #define MAXSIZE 12 /哈希表的最大容量，与所采用的哈希函数有关enum BOOLFalse,True;enum HAVEORNOTNULLKEY,HAVEKEY,DELKEY; /哈希表元素的三种状态，没有记录、有记录、有过记录但已被删除typedef struct /定义哈希表的结构 int elemMAXSIZE; /数据元素体 HAVEORNOT elemflagMAXSIZE; / 元素状态标志，没有记录、有记录、有过记录但已被删除 int count; / 哈希表中当前元素的个数 HashTable;typedef struct int keynum; / 记录的数据域，只有关键字一项Record;void InitialHash(HashTable&); / 初始化哈希表void PrintHash(HashTable); / 显示哈希表中的所有元素BOOL SearchHash(HashTable,int,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 哈 希 查 找 ); 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) 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); 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; case 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.keynum); / 输入要删除记录的关键字 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(HashTable H) / 显示哈希表所有元素及其所在位置 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; 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=HAVEKEY; / 设置标志为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); / 哈希函数：H(key)=key MOD 115、 测试数据与实验结果（可以抓图粘贴）（1）菜单：（2）建表（