查找与排序

实验七查找与排序

1. 实验目的

? ? ?

掌握常用查找算法的基本实现方式； 掌握各种排序算法的基本实现方式； 熟悉各种查找与排序算法的特点

2. 实验内容与基本要求

现有某地区某学校学生高考成绩数据（请见文本文件）若干，其中每位学生的信息包括考号、语文、数学、英语、理综、总分、全省排名、录取批次。请根据这些数据请建立一个顺序表。用户可通过数字键选择信息查找及排序功能。对程序的具体要求如下： 1） 程序启动后，显示下列选项信息：

1：排序 2：查找 0：退出

2） 输入数字“1”，进入排序区。进一步显示下列信息：

3：直接插入排序 4：简单选择排序 5：冒泡排序 6、高考总排名7 退出排序 ? 输入数字“3”，程序按照数学成绩进行直接插入排序并显示结果。 ? 输入数字“4”，程序按照语文成绩进行简单选择排序并显示结果。 ? 输入数字“5”，程序按照总分进行冒泡排序并显示结果。

? 输入数字“6”，程序进行高考总排名并显示结果，排名规则：总成绩、数学、

语文、英语、理综。即先按总成绩排，总成绩相同，按数学成绩的高低排名；若数学成绩也相同，按照语文成绩的高低排序；以此类推。注意排序方法的综合运用。

? 输入数字“7”，退出排序。

3） 可以在上述排序的基础上，进行查找实验。

8：顺序查找 9：折半查找 10：退出查找

? 输入数字“8”，程序提示由用户输入全省排名，然后按照全省排名进行顺序查

找并显示结果。

? 输入数字“9”，程序提示由用户输入总分，然后按照总分进行折半查找并显示

结果。

? 输入数字“10”，退出查找。

? 选做内容：在排序程序中，可以加入快速排序，归并排序算法；

在查找程序中，可以加入二叉排序树查找。

各模块名称以及功能说明：

long getlong(FILE *cfptr)函数：根据每一个结构体的长度为单

位长度，从txt文档的头开始计算，统计一共的学生人数。

long load(FILE *cfptr)函数：将txt文档里的信息存入stu[]里。

void zhijiecharu(struct data stu[],int count)函数：直接插

入排序，根据语文分数的高低，逐一按照关键字的大小插入到已经排好序的序列中的适当位置。

void jiandanxuanze(struct data stu[],int count)函数:根据

数学分数的高低，在所有的记录中选出关键字最小的记录，把它与第一个存储位置交换，然后再余下的记录中取出次小的关键字的对应记

录，将其余与第二个记录交换，不断重复到最后一个。

void maopao(struct data stu[],int count)函数：根据总分，

从第一个数据开始，两两比较相邻记录的关键字，即比较stu[i]和stu[i+1]的总分的大小，若倒序，则交换两者的位置，如此经过一趟排序，关键字最大的就放在了第一个位置，解这对之后的元素进行同样的处理，进行count-1次的操作。

void gaokaopaiming(struct data stu[],int count)函数：根

据总成绩、数学、语文、英语、理综的顺序进行排序，类似于冒泡排序，其中的判断语句为

（stu[j].total

void shunxuchazhao(struct data stu[],int count)函数：

在一个次数为count的for循环中，根据全省的排名进行查找，找到则输出相关的信息，找不到则输出“无数据存储”的信息。

void zhebanchazhao(struct data stu[],int count)函数：先

取表中间的位置的记录的总分和所输入的学生的关键字进行比较，若相等，则查找成功，如果给定值比记录的关键字大，则在后半部分继续进行折半查找，否则在前半部分进行折半查找。逐步缩小区域，知道找到关键字。

void exchange(struct data stu[],int count)函数： 根据总

分，对信息进行排序，以便供折半查找使用。

TNODE *creat(struct data stu[],int count)函数：按总分创

建二叉排序树，不断开辟空间，存入相关的信息，然后根据总分的比较，进行相应的连接，构成了二叉排序树。

TNODE *find(TNODE *p)函数：在二叉排序树里根据输入的关

键字，遍历查找学生信息。

void quicksort(struct data stu[],int low,int high)函数：利

用递归的方法快速查找。

int qpass(struct data stu[],int low ,int high)函数：选取一

个元素的关键字作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面。

void kuaisupaixu(struct data stu[],int count)函数：包含了

快速排序的函数，在调用时CASE里显得更简便。

void merge(struct data stu[],struct data stu_s[],int l,int m,int n)函数：该函数把数组看成count个记录的有序表，进行两

两归并，存入一个新的stu_s[]里，形成归并排序。

void mergepass(struct data stu[],struct data stu_s[],int count)函数：执行一次归并过程的函数，根据每一个元的长度，来

执行一趟归并排序。

void mergesort(struct data stu[],struct data stu_s[],int count)函数：2—路归并排序，初始每一个有序表的长度为1，然

后执行相应的判断，直到在stu_s[]里排序完毕，最后在重新存入stu[]中。

void guibingpaixu(struct data stu[],int count)函数：并

归的“主函数”，里面有相应归并函数，在case里使函数理解更加简

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