自主设计实验指导参考程序源代码

#include <dos.h> #include <conio.h> #include <math.h> #include <stdio.h> #include <stdlib.h> #define MAXSIZE 12 //哈希表的最大容量，与所采用的哈希函数有关 enum BOOL{False,True}; enum HAVEORNOT{NULLKEY,HAVEKEY,DELKEY}; //哈希表元素的三种状态，没有记录、有记录、有过记录但已被删除 typedef struct //定义哈希表的结构 { int elem[MAXSIZE]; //数据元素体 HAVEORNOT elemflag[MAXSIZE]; // 元素状态标志，没有记录、有记录、有过记录但已被删除 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("\n\t 哈 希 查 找 "); printf("\n\t**************************************"); printf("\n\t* 1-----建 表 *"); printf("\n\t* 2-----显 示 *"); printf("\n\t* 3-----查 找 *"); printf("\n\t* 4-----插 入 *"); printf("\n\t* 5-----删 除 *"); printf("\n\t* 0-----退 出 *"); printf("\n\t**************************************"); printf("\n\n\t请输入菜单号："); scanf(" %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 '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查找成功该元素位置是 %d\n",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("\n\t欢迎再次使用本程序，再见!\n"); } void InitialHash(HashTable &H) { // 哈希表初始化 int i; H.count=0; for(i=0;i<MAXSIZE;i++) H.elemflag[i]=NULLKEY; } void PrintHash(HashTable H) { // 显示哈希表所有元素及其所在位置 int i; for(i=0;i<MAXSIZE;i++) // 显示哈希表中记录所在位置 printf("%-4d",i); printf("\n"); for(i=0;i<MAXSIZE;i++) // 显示哈希表中记录值 if(H.elemflag[i]==HAVEKEY) printf("%-4d",H.elem[i]); else printf("%4c",' '); printf("\ncount:%d\n",H.count); // 显示哈希表当前记录数 } BOOL SearchHash(HashTable H,int k,int &p) { // 在开放定址哈希表H中查找关键字为k的数据元素，若查找成功，以p指示 // 待查数据元素在表中的位置，并返回True；否则，以p指示插入位置，并返回False int p1; p1=p=Hash(k); // 求得哈希地址 while(H.elemflag[p]==HAVEKEY&&k!=H.elem[p]) // 该位置中填有记录并且关键字不相等 { p++; // 冲突处理方法：线性探测再散列 if(p>=MAXSIZE) p=p%MAXSIZE; // 循环搜索 if(p==p1) return False; // 整个表已搜索完，没有找到待查元素 } if(k==H.elem[p]&&H.elemflag[p]==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.elemflag[p]=HAVEKEY; // 设置标志为HAVEKEY，表示该位置已有记录 H.elem[p]=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.elemflag[p]=DELKEY; // 设置标志为DELKEY，表明该元素已被删除 H.count--; // 哈希表当前长度减一 return True; } } int Hash(int kn) { return (kn%11); } // 哈希函数：H(key)=key MOD 11