数据结构的哈希表使用C++实现

#include "iostream.h" #include "string.h" typedef int keytype; //定义关键字类型 const int maxlist=10; struct elemtype //定义学生结构体类型 { keytype key; char name[8]; int english; int math; }; //--------------------------------定义哈希函数类------------------------ class sqhash { elemtype *hash; int length; keytype p; int tongzhi; //在find()函数中，用来记录有相同记录是的下标 int kongwz; //在find()函数中，用来记录找到可用空间是的下标 public: sqhash(); ~sqhash(); void creat(int n,int m); int creathash(); int find(keytype k); //是标准的全部查找函数 int find1(keytype k); //是进行某一条记录查找的函数 int insert(keytype k); int cancel(keytype k); void printout(); }; //------------------------------------------------------------------- //------------------------------------（定义顺序连表）------------ class list { public: elemtype li[maxlist]; int size; list() { size=0; } int creatlist(); int insert(); void changorder(); int find(keytype k); void print(); }; //---------------------------------------------------------- sqhash::sqhash() { } sqhash::~sqhash() { delete []hash; } void sqhash::creat(int n,int m) { length=n; p=m; hash=new elemtype[length]; for(int i=0;i<length;i++) //hash[i].key=0; //怎么样的话，如果输入的k为0，所以会判断是相同记录存在的。 hash[i].key=-1; //所以，，用key==-1表示，该位置的空间是空的。 } int sqhash::find(keytype k) { int biaos; //用来标识查找的结果。 int p1,p2; p1=k%p; //所以p1就是对应的地址， p2=p1-1; //所以p2是p1的前一个地址， if(p2<0) //为了防止p1=0的时候，p2应该是在p1之前，所以形成循环。 { p2=length-1; } while((hash[p1].key!=-1)&&(p1!=p2)) //查找是否存在空闲的位置 p1=(p1+1)%length; if(hash[p1].key==-1) //存在空位置 { kongwz=p1; //所以保存对应的下标 biaos=1; //设置对应的标记 } if(p1==p2) biaos=0; //表示哈希函数表已经满。 for(int i=0;i<length;i++) if(hash[i].key==k) //表示查找是否有相同记录的学生记录 { biaos=2; //设置标记 tongzhi=i; //保存对应的下标 } return biaos; } int sqhash::find1(keytype k) { int k1; k1=find(k); if(k1==0||k1==1) //根据find()函数进行判断，该关键字是否可用 { cout<<"\n对不起！不存在对应的学生的记录。"; return 0; } if(k1==2) { cout<<"学号:"<<hash[tongzhi].key<<"姓名:"<<hash[tongzhi].name<<"英语成绩:"<<hash[tongzhi].english<<"数学成绩:"<<hash[tongzhi].math<<endl; } return 0; } int sqhash::creathash() { int k1,k; cout<<"\n请输入要插入的学生记录的学号，（-1结束）"; cin>>k; while(k!=-1) { k1=find(k); //所以k1的到关键字是否可用的判断信息 if(k1==0) { cout<<"\n对不起！要插入的表已经满！"; return 0; } if(k1==1) { cout<<"\n请输入学生的姓名，英语成绩，数学成绩:"; cin>>hash[kongwz].name>>hash[kongwz].english>>hash[kongwz].math; hash[kongwz].key=k; } if(k1==2) { cout<<"\n要插入的学生的记录与关键字与某条记录相同，值为："; cout<<"学号:"<<hash[tongzhi].key<<"姓名:"<<hash[tongzhi].name<<"英语成绩:"<<hash[tongzhi].english<<"数学成绩:"<<hash[tongzhi].math<<endl; } cout<<"\n请输入要插入的同学的学号，（-1结束）"; cin>>k; } } int sqhash::insert(keytype k) { int k1; k1=find(k); //所以k1得到关键字的相关信息 if(k1==0) { cout<<"\n对不起！要插入的表已经满！"; return 0; } if(k1==1) { cout<<"\n请输入学生的姓名，英语成绩，数学成绩:"; cin>>hash[kongwz].name>>hash[kongwz].english>>hash[kongwz].math; hash[kongwz].key=k; cout<<"\n恭喜！插入记录成功!"; } if(k1==2) { cout<<"\n要插入的学生的记录与关键字与某条记录相同，值为："; cout<<"学号:"<<hash[tongzhi].key<<"姓名:"<<hash[tongzhi].name<<"英语成绩:"<<hash[tongzhi].english<<"数学成绩:"<<hash[tongzhi].math<<endl; } return 0; } int sqhash::cancel(keytype k) { int p1; p1=find(k); if(p1==2) { cout<<"\n你要删除的记录的值是:"; cout<<"学号:"<<hash[tongzhi].key<<"姓名:"<<hash[tongzhi].name<<"英语成绩:"<<hash[tongzhi].english<<"数学成绩:"<<hash[tongzhi].math<<endl; hash[tongzhi].key=-1; //根据在哈希函数中，对应的地址的移动是对length的循环求余，所以进行逻辑上的删除，不能物理删除 cout<<"\n恭喜！删除成功!"; } if(p1==0||p1==1) { cout<<"\n对不起！找不到要删除的记录!"; } return 0; } void sqhash::printout() { for(int i=0;i<length;i++) cout<<"\n学号:"<<hash[i].key<<"姓名:"<<hash[i].name<<"英语成绩:"<<hash[i].english<<"数学成绩:"<<hash[i].math; } //---------------------------------------------------------------------- void list::changorder() { elemtype t; int i=1; int finish=0; while(i<size&&!finish) { for(int j=0;j<size-i;j++) { if(li[j].key>li[j+1].key) { t=li[j]; li[j]=li[j+1]; li[j+1]=t; } finish=0; } finish=1; i++; } } int list::creatlist() { int i; cout<<"请输入开始要输入的记录的个数"; cin>>i; if(i>maxlist) { cout<<"你所要输入的记录超过了顺序表的容量！！"; return 0; } for(int j=0;j<i;j++) { cout<<"\n请输入第"<<j<<"个学生的学号，姓名，英语成绩，高数成绩\n"; cin>>li[j].key>>li[j].name>>li[j].english>>li[j].math; } size=i; changorder(); } void list::print() { int i; for(i=0;i<size; i++) cout<<"\n i="<<i<<"学号:"<<li[i].key<<"姓名:"<<li[i].name <<" 英语成绩:"<<li[i].english<<" 高数成绩:"<<li[i].math; } int list::find(keytype k) { int low=0,high=size-1,mid; while(low<=high) { mid=(low+high)/2; if(li[mid].key<k) low=mid+1; else if(li[mid].key>k) high=mid-1; else return mid; } return -1; } //----------------------------------------------------------------------- int main() { /*程序的缺陷有在对于每一次学生的关键字，就是学号的输入，因为要类型匹配的问题， 所以应该是像课件的一样，定义一个“记录”对象，所以每一次对关键字的输入的接收就用关键字.key 所以就能保证类型的匹配。*/ int n,m,k; sqhash has; list f; elemtype a; do { cout<<"\n\n=================查找的演示========================="; cout<<"\n 1. 建立哈希表（开放地址法）"; cout<<"\n 2. 在哈希表中查找某位学生 "; cout<<"\n 3. 输出哈希表"; cout<<"\n 4 .插入一个学生记录"; cout<<"\n 5 .删除一个学生记录"; cout<<"\n 6. 建立有序表"; cout<<"\n 7. 折半查找（是对应有序表）"; cout<<"\n 8. 输出有序表"; cout<<"\n 9. 退出"; cout<<"\n========================================================"; cout<<"\n 输入您的选择(1,2,3,4,5,6,7,8,9):"; cin>>k; switch(k) { case 1: { cout<<"\n 请输入n值（n值应是记录总数的1.3-1.5倍）"; //所以才能充分发挥哈希函数 cin>>n; cout<<"\n 请输入P值（应是不大于n 的大质数）："; //所以是小于或等于N的质数 cin>>m; has.creat(n,m); has.creathash(); }break; case 2: { int k; cout<<"\b请输入要查找的学生的学号:"; cin>>k; has.find1(k); }break; case 3: { has.printout(); }break; case 4: { int i; cout<<"\n请输入要插入的学生的学号！"; cin>>i; has.insert(i); }break; case 5: { int k; cout<<"\n请输入要删除的学生的学号!"; cin>>k; has.cancel(k); }break; case 6: { f.creatlist(); }break; case 7: { cout<<"\n 请输入要查找的学生的学号"; cin>>a.key; int l=f.find(a.key); if(l==-1) { cout<<"对不起，你要查找的记录不存在"; } else { cout<<"\n i="<<l<<" 学号："<<f.li[l].key<<"姓名："<<f.li[l].name <<" 英语成绩："<<f.li[l].english<<" 高数成绩："<<f.li[l].math; } }break; case 8: { f.print(); }break; case 9:break; }