实验七 查找、排序的应用

一、 实验目的

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，查找成功 若keyr[mid].key，则low=mid+1

重复上述操作，直至low>high时，查找失败

b、顺序查找

从表的一端开始逐个进行记录的关键字和给定值的比较。在这里从表尾开始并把下标为0的作为哨兵。

void chaxun(SqList &ST) //查询信息

{ cout<<\ cout<<\根据学号查询 ~\ cout<<\根据姓名查询 ~\ cout<<\根据性别查询 ~\ cout<<\退出 ~\

cout<<\if(m==1)

折半查找算法：

for(int i=1;i

for(int j=i;j>=1;j--)

if(ST.r[j].xuehao

LI=ST.r[j];

ST.r[j]=ST.r[j-1]; ST.r[j-1]=LI;

} int a=0;

cout<<\输入要查找的学号\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<

\\\\\

a=1; break; }

else if(n

high=mid-1; // 继续在前半区间进行查找 else

low=mid+1; // 继续在后半区间进行查找

顺序查找算法:

cout<<\输入要查找的姓名\ cin>>name;

for(int i=0;i

if(name==ST.r[i].xingming) {

cout<

\\\

\\

a=1; }

1、 插入排序

每步将一个待排序的记录，按其关键码大小，插入到前面已经排

好序的一组记录的适当位置上，直到记录全部插入为止。 //按学号排序，使用插入排序

RecordType LI; //定义存储学号向量 for(int i=1;i=1;j--)

if(ST.r[j].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

for (int j=i+1;j

{if(ST.r[i].chengji1>ST.r[j].chengji1) {LI=ST.r[j];

ST.r[j]=ST.r[i];

ST.r[i]=LI;

六、运行测试结果

输入学生信息

以多种方式进行查找