#include <iostream.h>
#include <string.h>
#define ERROR 0
#define OK 1
#define SIZE 100
typedef int Status;
typedef struct {
char no[8]; //学号
char name[20]; //姓名
int score; //成绩
}Student;
typedef struct{
Student *elem; //定义指向Student的指针
int length;//当前长度
int listsize;
}SqList;
/*输入学生信息*/
Status InitList_Sq(SqList &L,int n){
int i;
L.elem=new Student[SIZE];
L.length=1; //留下L.elem[0]作为哨兵
for(i=1;i<n+1;i++) //输入学生信息
{
cout<<"学号：";
cin>>L.elem[i].no;
cout<<"姓名：";
cin>>L.elem[i].name;
cout<<"成绩：";
cin>>L.elem[i].score;
cout<<endl;
L.length++;
}
return OK;
}
/*打印学生信息*/
Status Display_Sq(SqList L){
cout<<"位置"<<" 学号 "<<"姓名 "<<"成绩"<<endl;
for(int j=1;j<L.length;j++){
cout<<" "<<j<<":"<<" "<<L.elem[j].no<<" "<<L.elem[j].name<<" "<<L.elem[j].score<<endl;
}
return OK;
}
/*插入学生信息到表*/
Status Insert_Sq(SqList &L,int n){
if(L.length==SIZE){ //考虑表中空间已满的情况
cout<<"操作失败，系统空间已满！"<<endl;
return ERROR;
}
if(n<1||n>L.length){
cout<<"操作失败，您要插入的位置不存在！"<<endl;
return ERROR;
}
for(int i=L.length-1;i>=n;i--)
L.elem[i+1]=L.elem[i]; //依次将各学生的信息赋给其下一个位置
cout<<"输入要插入的学生信息："<<endl;
cout<<"学号：";
cin>>L.elem[n].no;
cout<<"姓名：";
cin>>L.elem[n].name;
cout<<"成绩：";
cin>>L.elem[n].score;
L.length++; //表长增加1
cout<<"插入学生信息成功！"<<endl;
return OK;
}
/*删除学生信息*/
Status Delete_Sq(SqList &L,int n){
if(n<1||n>L.length){
cout<<"操作失败，您要删除的位置不存在！"<<endl;
return ERROR;
}
for(int i=n;i<=L.length-1;i++)
L.elem[i]=L.elem[i+1]; //依次将各学生的信息赋给其上一个位置
L.length--; //表长减少1
cout<<"删除学生信息成功！"<<endl;
return OK;
}
/*统计学生总数*/
Status GetLen_Sq(SqList &L){
cout<<" "<<L.length-1<<" 人"<<endl;
return OK;
}
/*按姓名直接插入排序*/
void InsertSort(SqList &L)
{int i,j;
for(i=2;i<L.length;++i)
if(strcmp(L.elem[i].name,L.elem[i-1].name)==-1)
{ L.elem[0]=L.elem[i]; // 复制为哨兵
L.elem[i]=L.elem[i-1];
for(j=i-2;strcmp(L.elem[0].name,L.elem[j].name)==-1;--j)
L.elem[j+1]=L.elem[j]; // 记录后移
L.elem[j+1]=L.elem[0]; //插入到正确位置
}
}
/*按姓名折半插入排序*/
Status BInsertSort (SqList &L)
{
int low,high,m;
for(int i=2;i<L.length;++i){
L.elem[0]=L.elem[i]; // 复制为哨兵
low=1;
high=i-1;
while(low<=high){ //利用折半方法找到插入位置
m=(low+high)/2;
if(strcmp(L.elem[0].name,L.elem[m].name)<0)
high=m-1;
else
low=m+1;
}
for(int j=i-1;j>=high+1;--j) //纪录后移
L.elem[j+1]=L.elem[j];
L.elem[high+1]=L.elem[0];
}
return OK;
}
/*按学号快速排序*/
int pivotloc;
char pivotkey[10];
int Partition(SqList &L,int low,int high){
L.elem[0]=L.elem[low];
strcpy(pivotkey,L.elem[low].no);
while(low<high){
while(low<high&&strcmp(L.elem[high].no,pivotkey)>=0) //若有比哨兵小的high，则将其赋给low，否则high前移
--high;
L.elem[low]=L.elem[high];
while(low<high&&strcmp(L.elem[low].no,pivotkey)<=0) //若有比哨兵大的low，则将其赋给high，否则low后移
++low;
L.elem[high]=L.elem[low];
}
L.elem[low]=L.elem[0];
return low;
}
void QSort(SqList &L,int low,int high){
if(low<high){
pivotloc=Partition(L,low,high);
QSort(L,low,pivotloc-1); //递归调用对左子表排序
QSort(L,pivotloc+1,high); //递归调用对右子表排序
}
}
/*按姓名折半查找（递归）*/
int Search_Bin(SqList &L,char *s,int low,int high){
int m;
if(low<=high){
m=(low+high)/2;
if(strcmp(s,L.elem[m].name)==0)
return m;
else if(strcmp(s,L.elem[m].name)<0)
return Search_Bin(L,s,low,m-1); //对左子表折半查找
else
return Search_Bin(L,s,m+1,high); //对右子表折半查找
}
return -1;
}
/*按学号进行折半查找（非递归）*/
int Search_Bin1(SqList &L,char *s){
int m,low=1,high=L.length-1;
while(low<=high){
m=(low+high)/2;
if(strcmp(s,L.elem[m].no)==0)
return m;
else if(strcmp(s,L.elem[m].no)<0)
high=m-1;
else
low=m+1;
}
return -1;
}
void main(){
int no;
int n;
char names[20],nos[10];
SqList L;
L.length=1;
while(1)
{
cout<<"**************************** 欢迎使用学生信息管理系统！*************************"<<"\n";//菜单选项
cout<<"(1)输入学生信息"<<"\n";
cout<<"(2)逐个显示学生的相关信息"<<"\n";
cout<<"(3)插入学生信息到指定位置"<<"\n";
cout<<"(4)删除指定位置的学生记录"<<"\n";
cout<<"(5)统计表中学生人数"<<"\n";
cout<<"(6)利用直接插入排序按姓名进行排序"<<"\n";
cout<<"(7)利用折半插入排序按姓名进行排序"<<"\n";
cout<<"(8)利用快速排序按学号进行排序"<<"\n";
cout<<"(9)根据姓名进行折半查找，成功返回此学生的学号和成绩"<<"\n";
cout<<"(10)根据学号进行折半查找，成功返回此学生的姓名和成绩"<<"\n";
cout<<"(11)退出系统"<<"\n";
cout<<"\n";
cout<<"请选择您需要的服务:";
cin>>no;
switch(no){
case 1:cout<<"请输入学生个数：";
cin>>n;
InitList_Sq(L,n);
break;
case 2:
if(L.length==1){ //判断表是否为空
cout<<"学生表为空，无可显示的学生信息!"<<endl;
break;
}
cout<<"输出学生信息："<<endl;
Display_Sq(L); //调用函数
break;
case 3:
if(L.length==1){
cout<<"学生表为空，无可供插入的位置!"<<endl;
break;
}
cout<<"请输入插入位置：";
cin>>n;
Insert_Sq(L,n);
Display_Sq(L);
break;
case 4:
if(L.length==1){
cout<<"学生表为空，无可供删除的学生信息!"<<endl;
break;
}
cout<<"请输入删除位置：";
cin>>n;
Delete_Sq(L,n);
Display_Sq(L);
break;
case 5:
if(L.length==1){
cout<<"现表中的学生总数为 0 人"<<endl;
break;
}
cout<<"现表中的学生总数为";
GetLen_Sq(L);
break;
case 6:
if(L.length==1){
cout<<"学生表为空，无排序结果!"<<endl;
break;
}
InsertSort(L);
cout<<"按姓名进行直接插入法排序的结果为："<<endl;
Display_Sq(L);
break;
case 7:
if(L.length==1){
cout<<"学生表为空，无排序结果!"<<endl;
break;
}
BInsertSort(L);
cout<<"按姓名折半插入排序的结果为："<<endl;
Display_Sq(L);
break;
case 8:
if(L.length==1){
cout<<"学生表为空，无排序结果!"<<endl;
break;
}
QSort(L,1,L.length-1);
cout<<"按学号进行快速排序的结果为："<<endl;
Display_Sq(L);
break;
case 9:
if(L.length==1){
cout<<"学生表为空，无可供查找的学生信息!"<<endl;
break;
}
InsertSort(L); //先进行姓名的直接插入排序
cout<<"请输入查找学生的姓名：";
cin>>names;
int n1,low,high;
low=1;
high=L.length-1;
n1=Search_Bin(L,names,low,high); //调用折半查找
if(n1==-1){
cout<<"未找到该姓名的学生！"<<endl;
break;
}
cout<<"学号:"<<L.elem[n1].no<<endl;
cout<<"成绩:"<<L.elem[n1].score<<endl;
break;
case 10:
if(L.length==1){
cout<<"学生表为空，无可供查找的学生信息!"<<endl;
break;
}
QSort(L,1,L.length-1); //先进行学号的快速排序
cout<<"请输入查找学生的学号：";
cin>>nos;
int n2;
n2=Search_Bin1(L,nos); //调用折半查找
if(n2==-1){
cout<<"未找到该学号的学生！"<<endl;
break;
}
cout<<"姓名:"<<L.elem[n2].name<<endl;
cout<<"成绩:"<<L.elem[n2].score<<endl;
break;
case 11:
return;
}
cout<<"\n";
}
}
