《查找、排序的应用 实验报告.doc》由会员分享，可在线阅读，更多相关《查找、排序的应用 实验报告.doc（14页珍藏版）》请在三一文库上搜索。
1、实验七 查找、排序的应用一、 实验目的1、本实验可以使学生更进一步巩固各种查找和排序的基本知识。2、学会比较各种排序与查找算法的优劣。3、学会针对所给问题选用最适合的算法。4、掌握利用常用的排序与选择算法的思想来解决一般问题的方法和技巧。二、实验内容问题描述对学生的基本信息进行管理。 基本要求设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、性别、成绩1、成绩2、总成绩等信息。要求实现以下功能：1总成绩要求自动计算；2查询：分别给定学生学号、姓名、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现）；3 排序：分别按学生的学号、成绩1、成绩2、总成绩进行排序（要求至少用两种排序
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=rmid.key，查找成功 若key
3、rmid.key，则low=mid+1重复上述操作，直至lowhigh时，查找失败b、顺序查找从表的一端开始逐个进行记录的关键字和给定值的比较。在这里从表尾开始并把下标为0的作为哨兵。void chaxun(SqList &ST) /查询信息 coutn*endl;cout (1)根据学号查询 endl;cout (2)根据姓名查询 endl;cout (3)根据性别查询 endl;cout (4)退出 endl;cout*endl;if(m=1)折半查找算法： for(int i=1;i=1;j-)if(ST.rj.xuehaoST.rj-1.xuehao)LI=ST.rj;ST.rj=ST
4、.rj-1;ST.rj-1=LI;int a=0;cout输入要查找的学号n;int low,high,mid;low=0;high=ST.length-1; / 置区间初值while (low=high) mid=(low+high)/2;if(n=ST.rmid.xuehao) coutST.rmid.xuehao ST.rmid.xingming ST.rmid.xingbei ST.rmid.chengji1 ST.rmid.chengji2 ST.rmid.zongendl;a=1;break;else if(nST.rmid.xuehao )high=mid-1; / 继续在前半区
5、间进行查找else low=mid+1; / 继续在后半区间进行查找 顺序查找算法: cout输入要查找的姓名name; for(int i=0;iST.length;i+) if(name=ST.ri.xingming) coutST.ri.xuehao ST.ri.xingming ST.ri.xingbei ST.ri.chengji1 ST.ri.chengji2 ST.ri.zongendl; a=1; 1、 插入排序 每步将一个待排序的记录，按其关键码大小，插入到前面已经排好序的一组记录的适当位置上，直到记录全部插入为止。 /按学号排序，使用插入排序RecordType LI; /
6、定义存储学号向量for(int i=1;i=1;j-)if(ST.rj.xuehaoST.rj-1.xuehao)LI=ST.rj;ST.rj=ST.rj-1;ST.rj-1=LI;2、选择排序首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换重复上述操作，共进行n-1趟排序后，排序结束。 /按成绩1排序,用选择排序RecordType LI; for(int i=0; iST.length;i+)for (int j=i+1;jST.rj.chengji1)LI=ST.rj;S
7、T.rj=ST.ri;ST.ri=LI; 六、运行测试结果输入学生信息以多种方式进行查找按总成绩进行排序六、实验总结 通过本次实验我对查找排序的应用有了一定得了解，知道了各种查找排序的基本知识。 同时，通过自己数次的调试、修改也搞懂了许多以前比较模糊的知识点，比如这次的界面是复制过来的，其中很多语句经过同学的讲解都理解了。但这次实验也有很多不尽人意的地方，我将在以后多学习同学优秀的地方也会在以后的学习过程中要尽量考虑周全，使程序更有实用价值，提高编程能力。七、源代码#include using namespace std;#include #define MAXSIZE 100 /设记录不超过
8、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)/创建学生的相关信
9、息cout输入学生个数ST.length;for(int i=0;iST.length;i+) cout输入第i+1学生的信息endl;cout学号ST.ri.xuehao;cout姓名ST.ri.xingming;cout性别ST.ri.xingbei;cout成绩1ST.ri.chengji1;cout成绩2ST.ri.chengji2;cout输入完毕endl;void zong(SqList &ST) /计算总分 for(int i=0;iST.length;i+)ST.ri.zong=ST.ri.chengji1+ST.ri.chengji2;void shuchu(SqList &
10、ST)/输出cout学生的信息如下endl;cout学号 姓名 性别 成绩1 成绩2 总分 endl;for(int i=0;iST.length;i+)coutST.ri.xuehao ST.ri.xingming ST.ri.xingbei ST.ri.chengji1 ST.ri.chengji2 ST.ri.zong endl;void chaxun(SqList &ST) /查询信息l1:coutendl;cout(1)根据学号查询endl;cout(2)根据姓名查询endl;cout(3)根据性别查询endl;cout(4)退出m;if(m=1) /折半查找RecordType L
11、I; /使学号变为有序for(int i=1;i=1;j-)if(ST.rj.xuehaoST.rj-1.xuehao)LI=ST.rj;ST.rj=ST.rj-1;ST.rj-1=LI;l2:int a=0;cout输入要查找的学号n;int low,high,mid;low=0;high=ST.length-1; / 置区间初值while (low=high) mid=(low+high)/2;if(n=ST.rmid.xuehao) coutST.rmid.xuehao ST.rmid.xingming ST.rmid.xingbei ST.rmid.chengji1 ST.rmid.c
12、hengji2 ST.rmid.zongendl;a=1;break;else if(nST.rmid.xuehao )high=mid-1; / 继续在前半区间进行查找else low=mid+1; / 继续在后半区间进行查找if(!a)cout所查信息不存在!endl;cout请重新输入endl;goto l2; goto l1;if(m=2) /顺序查找l3:int a=0; cout输入要查找的姓名name; for(int i=0;iST.length;i+) if(name=ST.ri.xingming) coutST.ri.xuehao ST.ri.xingming ST.ri.
13、xingbei ST.ri.chengji1 ST.ri.chengji2 ST.ri.zongendl; a=1; if(!a) cout所查信息不存在!endl; cout请重新输入endl; goto l3; goto l1;if(m=3) /顺序查找 l4:int a=0; cout输入要查找性别xb; for(int i=0;iST.length;i+) if(xb=ST.ri.xingbei) coutST.ri.xuehao ST.ri.xingming ST.ri.xingbei ST.ri.chengji1 ST.ri.chengji2 ST.ri.zongendl; a=1
14、; if(!a) cout所查信息不存在!endl; cout请重新输入endl; goto l4; goto l1;if(m=4) caidan(ST);void paixu(SqList &ST) /排序l1:int n;coutendl;cout(1)根据学号排序endl;cout(2)根据成绩1排序endl;cout(3)根据成绩2排序endl;cout(4)根据总成绩排序endl;cout(5)退出;coutn;if(n=1) /按学号排序，使用插入排序RecordType LI; /定义存储学号向量for(int i=1;i=1;j-)if(ST.rj.xuehaoST.rj-1.
15、xuehao)LI=ST.rj;ST.rj=ST.rj-1;ST.rj-1=LI; shuchu(ST);cout排序完毕endl;goto l1;if(n=2) /按成绩1排序,用选择排序RecordType LI; for(int i=0; iST.length;i+)for (int j=i+1;jST.rj.chengji1)LI=ST.rj;ST.rj=ST.ri;ST.ri=LI;shuchu(ST);cout排序完毕endl;goto l1;if(n=3) / 根据成绩2排序,使用选择法排序RecordType LI; for(int i=0; iST.length;i+)for
16、 (int j=i+1;jST.rj.chengji2)LI=ST.rj;ST.rj=ST.ri;ST.ri=LI;shuchu(ST);cout排序完毕endl;goto l1;if(n=4) /根据总成绩排序,使用选择法排序RecordType LI; for(int i=0; iST.length;i+)for (int j=i+1;jST.rj.zong)LI=ST.rj;ST.rj=ST.ri;ST.ri=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)退出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);