实验七查找、排序的应用一、实验目的1、本实验可以使学生更进一步巩固各种查找和排序的基本知识。

2、学会比较各种排序与查找算法的优劣。

3、学会针对所给问题选用最适合的算法。

4、掌握利用常用的排序与选择算法的思想来解决一般问题的方法和技巧。

二、实验内容[问题描述]对学生的基本信息进行管理。

[基本要求]设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、性别、成绩1、成绩2、总成绩等信息。

要求实现以下功能：1．总成绩要求自动计算；2．查询：分别给定学生学号、姓名、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现）；3．排序：分别按学生的学号、成绩1、成绩2、总成绩进行排序（要求至少用两种排序算法实现）。

[测试数据]由学生依据软件工程的测试技术自己确定。

三、实验前的准备工作1、掌握哈希表的定义，哈希函数的构造方法。

2、掌握一些常用的查找方法。

1、掌握几种常用的排序方法。

2、掌握直接排序方法。

四、实验报告要求1、实验报告要按照实验报告格式规范书写。

2、实验上要写出多批测试数据的运行结果。

3、结合运行结果，对程序进行分析。

五、算法设计a、折半查找设表长为n，low、high和mid分别指向待查元素所在区间的下界、上界和中点,key为给定值。

初始时，令low=1,high=n,mid=(low+high)/2，让key与mid指向的记录比较，若key==r[mid].key，查找成功若key<r[mid].key，则high=mid-1若key>r[mid].key，则low=mid+1重复上述操作，直至low>high时，查找失败b、顺序查找从表的一端开始逐个进行记录的关键字和给定值的比较。

在这里从表尾开始并把下标为0的作为哨兵。

void chaxun(SqList &ST) //查询信息{ cout<<"\n************************"<<endl;cout<<"~ (1)根据学号查询 ~"<<endl;cout<<"~ (2)根据姓名查询 ~"<<endl;cout<<"~ (3)根据性别查询 ~"<<endl;cout<<"~ (4)退出 ~"<<endl;cout<<"************************"<<endl; if(m==1) 折半查找算法：for(int i=1;i<ST.length;i++)//使学号变为有序for(int j=i;j>=1;j--)if(ST.r[j].xuehao<ST.r[j-1].xuehao){LI=ST.r[j];ST.r[j]=ST.r[j-1];ST.r[j-1]=LI;}int a=0;cout<<"输入要查找的学号"<<endl;cin>>n;int low,high,mid;low=0;high=ST.length-1; // 置区间初值while (low<=high){mid=(low+high)/2;if(n==ST.r[mid].xuehao){cout<<ST.r[mid].xuehao<<""<<ST.r[mid].xingming<<""<<ST.r[mid].xingbei<<""<<ST.r[mid].chengji1<<""<<ST.r[mid].chengji2<<""<<ST.r[mid].zong<<endl;a=1;break;}else if(n<ST.r[mid].xuehao )high=mid-1; // 继续在前半区间进行查找elselow=mid+1; // 继续在后半区间进行查找顺序查找算法:cout<<"输入要查找的姓名"<<endl;cin>>name;for(int i=0;i<ST.length;i++){if(name==ST.r[i].xingming){cout<<ST.r[i].xuehao<<""<<ST.r[i].xingming<<""<<ST.r[i].xingbei<<""<<ST.r[i].chengji1<<""<<ST.r[i].chengji2<<""<<ST.r[i].zong<<endl;a=1;}1、插入排序每步将一个待排序的记录，按其关键码大小，插入到前面已经排好序的一组记录的适当位置上，直到记录全部插入为止。

//按学号排序，使用插入排序RecordType LI; //定义存储学号向量for(int i=1;i<ST.length;i++)for(int j=i;j>=1;j--)if(ST.r[j].xuehao<ST.r[j-1].xuehao){LI=ST.r[j];ST.r[j]=ST.r[j-1];ST.r[j-1]=LI;}2、选择排序首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换重复上述操作，共进行n-1趟排序后，排序结束。

//按成绩1排序,用选择排序RecordType LI;for(int i=0; i<ST.length;i++)for (int j=i+1;j<ST.length;j++){if(ST.r[i].chengji1>ST.r[j].chengji1){LI=ST.r[j];ST.r[j]=ST.r[i];ST.r[i]=LI;六、运行测试结果输入学生信息以多种方式进行查找按总成绩进行排序六、实验总结通过本次实验我对查找排序的应用有了一定得了解，知道了各种查找排序的基本知识。

同时，通过自己数次的调试、修改也搞懂了许多以前比较模糊的知识点，比如这次的界面是复制过来的，其中很多语句经过同学的讲解都理解了。

但这次实验也有很多不尽人意的地方，我将在以后多学习同学优秀的地方．也会在以后的学习过程中要尽量考虑周全，使程序更有实用价值，提高编程能力。

七、源代码#include <iostream>using namespace std;#include <string>#define MAXSIZE 100 //设记录不超过20个typedef struct //定义每个记录（数据元素）的结构{string xingming; //姓名string xingbei; //性别float xuehao; //学号float chengji1,chengji2; //成绩1，成绩2 float zong; //总分}RecordType;typedef struct //定义顺序表的结构{RecordType r[ MAXSIZE +1 ]; //存储顺序表的向量 int length; //顺序表的长度}SqList;void caidan(SqList &ST);void CreatList(SqList &ST)//创建学生的相关信息{cout<<"输入学生个数"<<endl;cin>>ST.length;for(int i=0;i<ST.length;i++){cout<<"输入第"<<i+1<<"学生的信息"<<endl;cout<<"学号"<<endl;cin>>ST.r[i].xuehao;cout<<"姓名"<<endl;cin>>ST.r[i].xingming;cout<<"性别"<<endl;cin>>ST.r[i].xingbei;cout<<"成绩1"<<endl;cin>>ST.r[i].chengji1;cout<<"成绩2"<<endl;cin>>ST.r[i].chengji2;}cout<<"输入完毕"<<endl;}void zong(SqList &ST) //计算总分{for(int i=0;i<ST.length;i++){ST.r[i].zong=ST.r[i].chengji1+ST.r[i].chengji2;}}void shuchu(SqList &ST)//输出{cout<<"学生的信息如下"<<endl;cout<<"学号姓名性别成绩1 成绩2 总分 "<<endl;for(int i=0;i<ST.length;i++){cout<<ST.r[i].xuehao<<" "<<ST.r[i].xingming<<" "<<ST.r[i].xingbei<<" "<<ST.r[i].chengji1<<""<<ST.r[i].chengji2<<" " <<ST.r[i].zong<<" "<<endl;}}void chaxun(SqList &ST) //查询信息{l1: cout<<endl;cout<<"(1)根据学号查询"<<endl;cout<<"(2)根据姓名查询"<<endl;cout<<"(3)根据性别查询"<<endl;cout<<"(4)退出"<<endl;int n,m;string name;string xb;cin>>m;if(m==1) //折半查找{RecordType LI; //使学号变为有序for(int i=1;i<ST.length;i++)for(int j=i;j>=1;j--)if(ST.r[j].xuehao<ST.r[j-1].xuehao){LI=ST.r[j];ST.r[j]=ST.r[j-1];ST.r[j-1]=LI;}l2: int a=0;cout<<"输入要查找的学号"<<endl;cin>>n;int low,high,mid;low=0;high=ST.length-1; // 置区间初值while (low<=high){mid=(low+high)/2;if(n==ST.r[mid].xuehao){cout<<ST.r[mid].xuehao<<" "<<ST.r[mid].xingming<<" "<<ST.r[mid].xingbei<<" "<<ST.r[mid].chengji1<<" "<<ST.r[mid].chengji2<<" "<<ST.r[mid].zong<<endl;a=1;break;}else if(n<ST.r[mid].xuehao )high=mid-1; // 继续在前半区间进行查找elselow=mid+1; // 继续在后半区间进行查找}if(!a){cout<<"所查信息不存在!"<<endl;cout<<"请重新输入"<<endl;goto l2;}goto l1;}if(m==2) //顺序查找{l3: int a=0;cout<<"输入要查找的姓名"<<endl;cin>>name;for(int i=0;i<ST.length;i++){if(name==ST.r[i].xingming){cout<<ST.r[i].xuehao<<" "<<ST.r[i].xingming<<" "<<ST.r[i].xingbei<<" "<<ST.r[i].chengji1<<" "<<ST.r[i].chengji2<<" "<<ST.r[i].zong<<endl;a=1;}}if(!a){cout<<"所查信息不存在!"<<endl;cout<<"请重新输入"<<endl;goto l3;}goto l1;}if(m==3) //顺序查找{l4: int a=0;cout<<"输入要查找性别"<<endl;cin>>xb;for(int i=0;i<ST.length;i++){if(xb==ST.r[i].xingbei){cout<<ST.r[i].xuehao<<" "<<ST.r[i].xingming<<" "<<ST.r[i].xingbei<<" "<<ST.r[i].chengji1<<" "<<ST.r[i].chengji2<<" "<<ST.r[i].zong<<endl;a=1;}}if(!a){cout<<"所查信息不存在!"<<endl;cout<<"请重新输入"<<endl;goto l4;}goto l1;}if(m==4){caidan(ST);}}void paixu(SqList &ST) //排序{l1: int n;cout<<endl;cout<<"(1)根据学号排序"<<endl;cout<<"(2)根据成绩1排序"<<endl;cout<<"(3)根据成绩2排序"<<endl;cout<<"(4)根据总成绩排序"<<endl;cout<<"(5)退出";cout<<endl;cin>>n;if(n==1) //按学号排序，使用插入排序{RecordType LI; //定义存储学号向量for(int i=1;i<ST.length;i++)for(int j=i;j>=1;j--)if(ST.r[j].xuehao<ST.r[j-1].xuehao){LI=ST.r[j];ST.r[j]=ST.r[j-1];ST.r[j-1]=LI;}shuchu(ST);cout<<"排序完毕"<<endl;goto l1;}if(n==2) //按成绩1排序,用选择排序{RecordType LI;for(int i=0; i<ST.length;i++)for (int j=i+1;j<ST.length;j++){if(ST.r[i].chengji1>ST.r[j].chengji1){LI=ST.r[j];ST.r[j]=ST.r[i];ST.r[i]=LI;}}shuchu(ST);cout<<"排序完毕"<<endl;goto l1;}if(n==3) // 根据成绩2排序,使用选择法排序{RecordType LI;for(int i=0; i<ST.length;i++)for (int j=i+1;j<ST.length;j++){if(ST.r[i].chengji2>ST.r[j].chengji2){LI=ST.r[j];ST.r[j]=ST.r[i];ST.r[i]=LI;}}shuchu(ST);cout<<"排序完毕"<<endl;goto l1;}if(n==4) //根据总成绩排序,使用选择法排序{RecordType LI;for(int i=0; i<ST.length;i++)for (int j=i+1;j<ST.length;j++){if(ST.r[i].zong>ST.r[j].zong){LI=ST.r[j];ST.r[j]=ST.r[i];ST.r[i]=LI;}}shuchu(ST);cout<<"排序完毕"<<endl;goto l1;}if(n==5) //退出{caidan(ST);}}void caidan(SqList &ST)//选择菜单{cout<<"请选择要进入的模块"<<endl;cout<<"(1)查询"<<endl;cout<<"(2)排序"<<endl;cout<<"(3)退出"<<endl;int c;cin>>c;if(c==1){chaxun(ST);}if(c==2){paixu(ST);}if(c==3){exit(0);}}void main(){SqList ST;CreatList(ST);zong(ST);shuchu(ST);caidan(ST);}。