查找排序应用.doc

实验五 查找、排序的应用 一、实验目的 1、本实验可以使学生更进一步巩固各种查找和排序的基本知识。 2、学会比较各种排序与查找算法的优劣。 3、学会针对所给问题选用最适合的算法。 4、掌握利用常用的排序与选择算法的思想来解决一般问题的方法和技巧。 二、实验内容 [问题描述] [基本要求] [测试数据] 将一个序列分为两部分，其中一部分记录的关键字均比另一部分关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。算法利用递归实现，依次将序列分为两部分，直至划分为最小，则可由部分有序，依次求得整体有序，程序完成，则 整个序列为一个有序序列。 哈希，按姓名查找 采用链地址法哈希，将组成姓名的各个字母加起来得到之和对N取余，即为hash下标，将相同的放在同一个链表中，查找时，只需在对应下标的链表里查找即可，并在hash里面定义变量，保存姓名所对应的学生stu[i]的下标 程序清单 #include iostream #include string using namespace std; #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(); void CreatList(SqList ST)//创建学生的相关信息 { cout输入学生个数endl; cinST.length; for(int i=0;iST.length;i++) { cout输入第i+1学生的信息endl; cout学号endl; cinST.r[i].xuehao; cout姓名endl; cinST.r[i].xingming; cout性别endl; cinST.r[i].xingbei; cout成绩1endl; cinST.r[i].chengji1; cout成绩2endl; cinST.r[i].chengji2; } cout输入完毕endl; } void zong(SqList ST) //计算总分 { for(int i=0;iST.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;iST.length;i++) { coutST.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) //查询信息 { coutendl; cout(1)根据学号查询endl; cout(2)根据姓名查询endl; cout(3)根据性别查询endl; cout(4)退出endl; int n,m; string name; string xb; cinm; if(m==1) //折半查找 { RecordType LI; //使学号变为有序 for(int i=1;iST.length;i++) { for(int j=i;j=1;j--) if(ST.r[j].xuehaoST.r