#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;
}
