查找、排序的应用 实验报告

一、 实验目的

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<<\"\\n************************\"<cout<<\"************************\"<折半查找算法：

for(int i=1;i--

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

if(ST.r[j].xuehaoLI=ST.r[j];

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

2

精选文库

} 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.r[mid].xuehao)

{

cout<\"<a=1; break; }

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

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

顺序查找算法:

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

for(int i=0;iif(name==ST.r[i].xingming)

{

cout<--

3

精选文库

\"<a=1; }

1、 插入排序

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

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

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

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

--

4

六、运行测试结果

输入学生信息

以多种方式进行查找

-- 精选文库

5

精选文库

按总成绩进行排序

六、实验总结

通过本次实验我对查找排序的应用有了一定得了解，知道了

各种查找排序的基本知识。 同时，通过自己数次的调试、修改也搞懂了许多以前比较模糊的知识点，比如这次的界面是复制过来的，其中很多语句经过同学的讲解都理解了。但这次实验也有很多不尽人意的地方，我将在以后多学习同学优秀的地方．也会在以后的学习过程中要尽量考虑周全，使程序更有实用价值，提高编程能力。

-- 6

精选文库

七、源代码

#include using namespace std; #include

#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<<\"输入学生个数\"<>ST.length;

for(int i=0;icout<<\"输入第\"<>ST.r[i].xuehao; cout<<\"姓名\"<>ST.r[i].xingming; cout<<\"性别\"<>ST.r[i].xingbei; cout<<\"成绩1\"<>ST.r[i].chengji1; cout<<\"成绩2\"<>ST.r[i].chengji2;

--

7

精选文库

}

cout<<\"输入完毕\"<void zong(SqList &ST) //计算总分 {

for(int i=0;iST.r[i].zong=ST.r[i].chengji1+ST.r[i].chengji2; } }

void shuchu(SqList &ST)//输出 {

cout<<\"学生的信息如下\"<cout<<\"学号 姓名 性别 成绩1 成绩2 总分 \"<cout<void chaxun(SqList &ST) //查询信息 {

l1: cout<cout<<\"(1)根据学号查询\"<>m;

if(m==1) //折半查找 {

RecordType LI; //使学号变为有序 for(int i=1;i=1;j--)

--

8

精选文库

if(ST.r[j].xuehaoLI=ST.r[j];

ST.r[j]=ST.r[j-1]; ST.r[j-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.r[mid].xuehao) {

cout<else if(nhigh=mid-1; // 继续在前半区间进行查找 else

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

if(!a) {

cout<<\"所查信息不存在!\"<goto l1; }

if(m==2) //顺序查找 {

--

9

精选文库

l3: int a=0;

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

for(int i=0;iif(name==ST.r[i].xingming) {

cout<if(!a) {

cout<<\"所查信息不存在!\"<goto l1; }

if(m==3) //顺序查找 {

l4: int a=0;

cout<<\"输入要查找性别\"<>xb;

for(int i=0;iif(xb==ST.r[i].xingbei) {

cout<if(!a)

--

10

精选文库

{

cout<<\"所查信息不存在!\"<goto l1; } if(m==4) {

caidan(ST); } }

void paixu(SqList &ST) //排序 {

l1: int n;

cout<cout<<\"(1)根据学号排序\"<cout<<\"(3)根据成绩2排序\"<>n;

if(n==1) //按学号排序，使用插入排序 {

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

if(ST.r[j].xuehaoLI=ST.r[j];

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

}

shuchu(ST);

--

11

cout<<\"排序完毕\"<if(n==2) //按成绩1排序,用选择排序 {

RecordType LI;

for(int i=0; ifor (int j=i+1;jif(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<<\"排序完毕\"<if(n==3) // 根据成绩2排序,使用选择法排序 {

RecordType LI;

for(int i=0; ifor (int j=i+1;jif(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<<\"排序完毕\"<--

精选文库

12

goto l1; }

if(n==4) //根据总成绩排序,使用选择法排序 {

RecordType LI;

for(int i=0; ifor (int j=i+1;jif(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<<\"排序完毕\"<if(n==5) //退出 {

caidan(ST); } }

void caidan(SqList &ST)//选择菜单 {

cout<<\"请选择要进入的模块\"<>c; if(c==1) {

chaxun(ST);

--

精选文库

13

}

if(c==2) {

paixu(ST); }

if(c==3) {

exit(0); } }

void main() {

SqList ST; CreatList(ST); zong(ST); shuchu(ST); caidan(ST); }

-- 精选文库

14