数据结构实验——学生管理系统的设计与实现

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