数据结构哈希表有关实验

一、 设计课题：哈希表设计 二、 需求分析： 课题的目的和任务：根据数据元素的关键字和哈希函数建立哈希表并初始化哈希表，用开放定址法处理冲突，按屏幕输出的功能表选择所需的功能实现用哈希表对数据元素的插入，显示，查找，删除。 初始化哈希表时把elem[MAXSIZE]、elemflag[MAXSIZE]和count分别置0。创建哈希表时按哈希函数创建哈希表，输入数据元素的关键字时，以“0”结束输入且要求关键字为正整数，数据元素个数不允许超过表长MAXSIZE。 输出的形式:根据所选择的哈希表的功能输出相应提示语句和正确结果。 程序的功能：将一组个数不超过哈希表长度的数据元素，按其关键字和哈希函数存入哈希表中，如果产生冲突用开放定址法处理并找出相应的地址。能实现用哈希表对数据元素的插入，显示，查找，删除。 测试数据： maxsize=10 哈希函数：H（key）=key%7 处理冲突方法： 开放定址法 Hi=(H(key)+di)%13 i=1,2,3,…,9 三、实验概要设计： ADT HashTable { 数据对象：D1={ai|ai∈elem[MAXSIZE],i=0,1,2,…,0≦n≦MAXSIZE } elem [MAXSIZE]是哈希表中关键字的集合，MAXSIZE为哈希表长。} D2={ai|ai∈elemflag[MAXSIZE]是哈希表中有无关键字的标志的集合，MAXSIZE为哈希表长。} 基本操作： Hash(key) 初始条件：数据元素关键字key已存在 操作结果：根据哈希函数计算相应地址，并返回此地址。 InitialHash(HashTable &H) 初始条件：哈希表H已存在 操作结果：初始化哈希表把elem[MAXSIZE]、elemflag[MAXSIZE]和count分别置0。 SearchHash(HashTable &H,int k) 初始条件：哈希表H已存在 操作结果：在开放定址哈希表H中查找关键字为k的元素，若查找成功，并返回SUCCESS；否则返回UNSUCCESS。 InsertHash(HashTable &H,int e) 初始条件：哈希表H已存在 操作结果：查找不成功时插入数据元素e到开放定址哈希表H中，并返回SUCCESS；否则输出已有此数！插入失败！并返回UNSUCCESS。 CreateHash(HashTable &H) 操作结果：构造哈希表。 PrintHash(HashTable H) 初始条件：哈希表H已存在 操作结果：将哈希表存储状态显示输出。 DeleteHash(HashTable &H,int e) 初始条件：哈希表H已存在 操作结果：若通过哈希函数找到相应的位置并且此位置的elemflag[MAXSIZE]==1，删除相应位置的数据元素的关键字并把elemflag[MAXSIZE]==2，否则，输出无此数的提示语。 2. 本程序包括如下功能模块 哈希函数模块，冲突处理模块，哈希表初始化模块，哈希表创建模块，哈希表显示模块，按关键字查找模块，插入模块，删除模块和主程序模块。 四、基本操作的算法描述： 1.宏定义 #define MAXSIZE 10 #define SUCCESS 1 #define UNSUCCESS 0 2.数据类型、数据元素的定义 typedef struct { int elem[MAXSIZE]; int elemflag[MAXSIZE]; int count; }HashTable; 3. 哈希表的基本操作的算法描述 //初始化哈希函数 void InitialHash(HashTable &H)/*哈希表初始化*/ { int i; H.count=0; for(i=0;i<MAXSIZE;i++) { H.elem[i]=0; H.elemflag[i]=0; } } //哈希函数 int Hash(int kn) /*哈希函数H(key)=key MOD 7*/ { return (kn%7); } //查找函数 int SearchHash(HashTable &H,int k) /*查找关键字为k的元素*/ { int t,s; s=t=Hash(k); //调用哈希函数 xun: if(H.elem[t]==k&&H.elemflag[t]==1) return SUCCESS; //如果相应的地址上的数等于k，返回1 else if(H.elem[t]!=k&&H.elemflag[t]==1) { //相应地址有数但不等于k并且H.elemflag[t]==1 t=(t+1)%MAXSIZE; // 处理冲突 goto xun; } else return UNSUCCESS; //返回0 } //插入函数 int InsertHash(HashTable &H,int e)/*插入元素e*/ { int p; p=Hash(e); if(SearchHash(H,e) ) //调用查找函数，如果有此数返回1 { cout<<"已有此数！"<<endl; return UNSUCCESS; //插入是吧，返回0 } else //查找失败，返回0 { H.elemflag[p]=1; //把状态标志置1 H.elem[p]=e; //把关键字放入相应的地址 H.count++; //计数加1 return SUCCESS; //插入成功，返回1 } } //创建哈希表的函数 void CreateHash(HashTable &H)/*创建哈希表*/ { int s; int e; cout<<"请输入哈希表：(输入0结束！)"<<endl; cin>>e; while(e) { s=InsertHash(H,e); //调用插入函数 if(!s) { cout<<"此数已存在！"; cin>>e; } else cin>>e; } } //显示函数 void PrintHash(HashTable H) /*显示元素及其位置*/ { cout<<"哈希表地址："; int i; for(i=0;i<MAXSIZE;i++) cout<<i<<" "; cout<<endl<<"关键字: "; for(i=0;i<MAXSIZE;i++) cout<<H.elem[i]<<" "; cout<<endl<<"关键字标志："; for(i=0;i<MAXSIZE;i++) cout<<H.elemflag[i]<<" "; } //删除函数 int DeleteHash(HashTable &H,int e) /*删除元素e*/ { int i; int a=0; for(i=0;i<MAXSIZE;i++) if(H.elem[i]==e&&H.elemflag[i]==1) { H.elemflag[i]=2; H.count--; H.elem[i]=0; a++; return SUCCESS; } if(!a) { cout<<"无此数！"<<endl; return UNSUCCESS; } } //主函数 void main() { HashTable H; int m,k,p; int R; do{ cout<<endl<<"\t\t******************请选择功能********************"<<endl; cout<<"\t\t\t1.初始化哈希表"<<endl<<"\t\t\t2.创建哈希表"<<endl<<"\t\t\t3.查找" <<endl<<"\t\t\t4.插入"<<endl<<"\t\t\t5.删除"<<endl<<"\t\t\t6.输出哈希表："<<endl<<"\t\t\t0.退出"<<endl; cout<<"\t\t************************************************"<<endl; cin>>m; switch(m) { case 1: InitialHash(H);break; case 2: CreateHash(H);break; case 3: cout<<endl<<"请输入要查找的关键字:"; cin>>k; p=SearchHash(H,k); if(p) cout<<"查找成功！"<<endl; else cout<<"查找失败！"<<endl; break; case 4: cout<<endl<<"请输入要插入的关键字:"; cin>>R; p=InsertHash(H,R); if(p) cout<<"插入成功！"<<endl; else cout<<"插入失败！"<<endl; break; case 5: cout<<"请输出要删除的关键字："; cin>>R; p=DeleteHash(H,R); if(p) cout<<"删除成功！"<<endl; else cout<<"删除失败！"<<endl; break; case 6: PrintHash(H);break; case 0: break; default: cout<<endl<<"选择错误！";break; }