查找，排序的应用

查找、排序的应用

《数据结构》

实 验 报 告 书

实验内容：查找、排序的应用 学院班级：计算机学院计算机科学与技术 姓 名：*****

学 号：20110********** 指导老师：高****

1

查找、排序的应用

前言

计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习计算机编程仅仅了解计算机语言是不够的，还必须掌握数据的组织、存储和运算的一般方法，这便是数据结构课程中所研究的内容，也是我们编写计算机程序的重要基础，由于它对计算机学科起到承前启后的作用，因此本课程被列为计算机等相关专业最重要的专业基础课；同时数据结构是计算机专业教学的一门核心课程。计算机各领域都要用到各种数据结构，而且要从事计算机科学与技术工作，尤其是计算机领域的软件开发工作，必须具备较强的数据结构基础。

数据结构课程内容丰富、学习量大，实践性强；隐含在各部分内容中的方法和技术多；算法设计具有动态性和抽象性等特点，看懂听明白与掌握会应用之间有相当大的一段距离。所以学生必须多实践才能进一步加深对课程的理解，理解和掌握算法设计所需的方法和技术，为整个专业学习打下良好的基础。

实验七查找、排序的应用

一、实验目的

1、本实验可以使学生更进一步巩固各种查找和排序的基本知识。 2、学会比较各种排序与查找算法的优劣。 3、学会针对所给问题选用最适合的算法。

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

二、实验内容

[问题描述]

对学生的基本信息进行管理。

2

查找、排序的应用

[基本要求]

设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、性别、成绩1、成绩2、总成绩等信息。要求实现以下功能：

1．总成绩要求自动计算；

2．查询：分别给定学生学号、姓名、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现）；

3． 排序：分别按学生的学号、成绩1、成绩2、总成绩进行排序（要求至少用两种排

序算法实现）。

[测试数据]

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

三、算法设计

本程序指定的人数进行输入学号，姓名，性别，成绩1，和成绩2，进行建立学生信息。姓名和性别分别用字符串型，学号、成绩1和成绩二用浮点型，并顺序表作为储存结构。建立好后，实现：查找、排序、退出功能。查找:三种查找选择，分别对学号以折半查找的方式查找，对姓名和性别以顺序查找。排序：分别以插入排序对学号进行排序，选择排序对成绩1、成绩2和总成绩进行排序。以下是具体实现： 定义记录结构：

typedefstruct //定义每个记录（数据元素）的结构 {

string xingming; //姓名 string xingbei; //性别 float xuehao; //学号

float chengji1,chengji2; //成绩1，成绩2 float zong; //总分 }RecordType;

定义顺序表结构：

typedefstruct //定义顺序表的结构 {

RecordType r[ MAXSIZE +1 ]; //存储顺序表的向量 int length; //顺序表的长度 }SqList;

建立学生信息：

void CreatList(SqList&ST)//创建学生的相关信息 {

cout<<\输入学生个数\ cin>>ST.length;

for(int i=0;i

cout<<\输入第\学生的信息\

3

查找、排序的应用

cout<<\学号\ cin>>ST.r[i].xuehao; cout<<\姓名\ cin>>ST.r[i].xingming; cout<<\性别\ cin>>ST.r[i].xingbei; cout<<\成绩1\ cin>>ST.r[i].chengji1; cout<<\成绩2\ cin>>ST.r[i].chengji2; }

cout<<\输入完毕\}

建立完后，计算每一个学生的成绩总分并把结构输出。总分在void zong(SqList&ST)这个函数中实现，具体见源程序。 输出在void shuchu(SqList&ST)函数中实现代码如下： void shuchu(SqList&ST)//输出 {

cout<<\学生的信息如下\

cout<<\学号 姓名 性别 成绩1 成绩2 总分 \ for(int i=0;i

cout<

为了使操作简单美观用菜单的形式进行选择相应操作，调用相应函数。 查找void chaxun(SqList&ST)：

对学号、姓名、性别查找具体见源程序，退出回到主菜单的功能。 排序void paixu(SqList&ST)：

对学号、成绩1、成绩2和总成绩排序，并有退出此排序回到主菜单的功能。

四、调试测试

输入学生个数：为了简单方便学生数为4个输入时，学号性别 成绩1成绩2进以乱序输入：如下：

4

查找、排序的应用

可以看到 输入的信息没有明显的什么顺序。 查询：输入1回车

根据学号查询:查找学号为2和3的同学的信息：

可以看到查找

成功。

输入2回车：根据姓名查询：查找姓名为小明和小李同学的信息：

可以看到查

找成功。

输入3回车：根据性别查询：分别分找为男和女同学的信息：

可以看到查找

成功。 排序：在上次的操作基础上按4退出子菜单进入主菜单再选择2进行排序操作子菜单:

5

查找、排序的应用

根据学号排序：按1回车如下：

可以看到已经按照学号

的升序顺序变得有序；

根据成绩1排序：按下2回车如下：

可以看到已经按照成绩

1的升序变得有序；

根据成绩2排序：按下3回车如下：

可以看到已经按照成绩

2的升序变得有序；

按总成绩排序：按下4回车如下：

可以看到已经按照总成

绩的升序变得有序；

测试完毕 测试结果成功。

五、总结：

本实验是关于查找和排序的实验，查找和排序都有很多种方法。只要给定相关的关键字就能查找出相关的信息，也能按照关键字重新排序信息。本实验综合性非常强，它包含顺序表的存储、查找、排序，而且多处用到调用的方法，调用贯穿于整个程序之中，用到折半查找和顺序查找，用到插入排序和选择排序。通过本实验我对查找和排序这两个章节的内容更加了解，虽然这两个章节内容学习

6

查找、排序的应用

的时候时间非常紧，有很多不懂和疑问，但是通过这次实验，有了很好的补充，同时对顺序表和调用做了一次很好的复习。

在本次实验的过程中，我也遇到了许多的问题，主要的就是不能很好的对查找和排序进行综合性的运用，在层次方面，不能做到成功的调用等等很多疑问，但是我通过查阅课本和上网查找相关的问题，最终得到了解决。

本程序还有待完善的地方，比如当输入数据有错误的时候，会出现死锁的现象，导致程序不能正常工作，学号和性别的输入也没有什么限制，可以在定义的类型内任意输入，显然这不能和事实相符，以后可以加一个判断输入内容的代码。

六、源代码

#include using namespace std; #include

#define MAXSIZE 100 //设记录不超过20个

typedefstruct //定义每个记录（数据元素）的结构 {

string xingming; //姓名 string xingbei; //性别 float xuehao; //学号

float chengji1,chengji2; //成绩1，成绩2 float zong; //总分 }RecordType;

typedefstruct //定义顺序表的结构 {

RecordType r[ MAXSIZE +1 ]; //存储顺序表的向量 int length; //顺序表的长度 }SqList;

voidcaidan(SqList&ST);

void CreatList(SqList&ST)//创建学生的相关信息 {

cout<<\输入学生个数\ cin>>ST.length;

for(int i=0;i

cout<<\输入第\学生的信息\ cout<<\学号\ cin>>ST.r[i].xuehao; cout<<\姓名\ cin>>ST.r[i].xingming; cout<<\性别\ cin>>ST.r[i].xingbei; cout<<\成绩1\ cin>>ST.r[i].chengji1; cout<<\成绩2\

7

查找、排序的应用

cin>>ST.r[i].chengji2; }

cout<<\输入完毕\}

void zong(SqList&ST) //计算总分 {

for(int i=0;i

ST.r[i].zong=ST.r[i].chengji1+ST.r[i].chengji2; } }

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

cout<<\学生的信息如下\

cout<<\学号 姓名 性别 成绩1 成绩2 总分 \ for(int i=0;i

cout<

void chaxun(SqList&ST) //查询信息 { l1: cout<

cout<<\根据学号查询\ cout<<\根据姓名查询\ cout<<\根据性别查询\ cout<<\退出\ intn,m;

string name; stringxb; cin>>m;

if(m==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; }

8

查找、排序的应用

l2: int a=0;

cout<<\输入要查找的学号\ cin>>n;

intlow,high,mid;

low=0;high=ST.length-1; // 置区间初值 while (low<=high) {

mid=(low+high)/2;

if(n==ST.r[mid].xuehao) {

cout<

else if(n

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

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

if(!a) {

cout<<\所查信息不存在!\ cout<<\请重新输入\ goto l2; }

goto l1; }

if(m==2) //顺序查找 { l3: int a=0;

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

for(int i=0;i

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

cout<

9

查找、排序的应用

if(!a) {

cout<<\所查信息不存在!\ cout<<\请重新输入\ goto l3; }

goto l1; }

if(m==3) //顺序查找 { l4: int a=0;

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

for(int i=0;i

if(xb==ST.r[i].xingbei) {

cout<

cout<<\所查信息不存在!\ cout<<\请重新输入\ goto l4; } goto l1; }

if(m==4) {

caidan(ST); } }

void paixu(SqList&ST) //排序 { l1: int n;

cout<

cout<<\根据学号排序\ cout<<\根据成绩1排序\

cout<<\根据成绩2排序\

10

查找、排序的应用

cout<<\根据总成绩排序\ cout<<\退出\ cout<>n;

if(n==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;

} shuchu(ST);

cout<<\排序完毕\ goto l1; }

if(n==2) //按成绩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; } } shuchu(ST);

cout<<\排序完毕\ goto l1; }

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

RecordType LI;

for(int i=0; i

for (int j=i+1;j

11

查找、排序的应用

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<<\排序完毕\ goto l1; }

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

RecordType LI;

for(int i=0; i

for (int j=i+1;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<<\排序完毕\ goto l1; }

if(n==5) //退出 {

caidan(ST); } }

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

cout<<\请选择要进入的模块\ cout<<\查询\ cout<<\排序\ cout<<\退出\ int c; cin>>c;

12

查找、排序的应用

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); }

13

本文来源：https://www.bwwdw.com/article/k1jd.html