下载文档原格式
北京物资学院信息学院实验报告
课程名_数据结构与算法
实验名称查找与排序
实验日期年月日实验报告日期年月日姓名______ ___ 班级_____ ________ 学号___
一、实验目的
1.掌握线性表查找的方法；
2.了解树表查找思想；
3.掌握散列表查找的方法.
4.掌握插入排序、交换排序和选择排序的思想和方法；
二、实验内容
查找部分
1.实现顺序查找的两个算法（P307）, 可以完成对顺序表的查找操作, 并根据查到和未查到两种情况输出结果；
2.实现对有序表的二分查找；
3.实现散列查找算法(链接法)，应能够解决冲突；
排序部分
4.分别实现直接插入排序、直接选择排序、冒泡排序和快速排序算法
三、实验地点与环境
3.1 实验地点
3.2实验环境
(操作系统、C语言环境)
四、实验步骤
（描述实验步骤及中间的结果或现象。
在实验中做了什么事情, 怎么做的, 发生的现象和中间结果, 给出关键函数和主函数中的关键段落）
五、实验结果
六、总结
（说明实验过程中遇到的问题及解决办法；个人的收获；未解决的问题等）。
列出常见的查找和排序方法主题：常见的查找和排序方法查找和排序是计算机科学中最基本和常见的问题之一。
在处理大量数据时，高效的查找和排序算法可以大大提高计算效率和性能。
本文将详细介绍常见的查找和排序方法，并逐步回答与之相关的问题。
一、查找方法1. 顺序查找（Sequential Search）：从头到尾逐一比较，直到找到目标元素或搜索结束。
对于无序数据集合，顺序查找是一种简单但低效的方法。
问题1：顺序查找的时间复杂度是多少？- 回答1：顺序查找的时间复杂度为O(n)，其中n是数据集合的大小。
2. 二分查找（Binary Search）：对有序数据集合，每次将待查找范围缩小一半，直到找到目标元素或搜索结束。
由于每次都可以排除一半的数据，二分查找是一种高效的查找算法。
问题2：二分查找要求数据集合必须有序吗？- 回答2：是的，二分查找要求数据集合必须有序，才能通过每次排除一半的方式进行查找。
3. 散列查找（Hashing）：根据关键字直接计算出元素在数据集合中的位置，通过查找该位置的元素来判断是否找到目标元素。
散列查找在理想情况下可以达到常数时间复杂度。
问题3：散列查找的时间复杂度是多少？- 回答3：散列查找的时间复杂度为O(1)，但在一些情况下，散列函数可能会产生冲突，导致查找的时间复杂度变为O(n)。
二、排序方法1. 冒泡排序（Bubble Sort）：比较相邻的元素，如果顺序不对则交换位置，重复这个过程直到整个数据集合排序完成。
问题4：冒泡排序的时间复杂度是多少？- 回答4：冒泡排序的时间复杂度为O(n^2)，其中n是数据集合的大小。
2. 插入排序（Insertion Sort）：将数据集合分为已排序和未排序两部分，逐个将未排序元素插入已排序部分的合适位置，直到整个数据集合排序完成。
问题5：插入排序有什么优化方法？- 回答5：可以使用二分查找找到插入位置，从而减少比较和移动的次数，提高插入排序的效率。
排序和查找的实验报告实验报告：排序和查找引言排序和查找是计算机科学中非常重要的基本算法。
排序算法用于将一组数据按照一定的顺序排列，而查找算法则用于在已排序的数据中寻找特定的元素。
本实验旨在比较不同排序和查找算法的性能，并分析它们的优缺点。
实验设计为了比较不同排序算法的性能，我们选择了常见的几种排序算法，包括冒泡排序、插入排序、选择排序、快速排序和归并排序。
我们使用相同的随机数据集对这些算法进行了测试，并记录了它们的执行时间和占用空间。
在查找算法的比较实验中，我们选择了顺序查找和二分查找两种常见的算法。
同样地，我们使用相同的随机数据集对这些算法进行了测试，并记录了它们的执行时间和占用空间。
实验结果在排序算法的比较实验中，我们发现快速排序和归并排序在大多数情况下表现最好，它们的平均执行时间和空间占用都要优于其他排序算法。
而冒泡排序和插入排序则表现较差，它们的执行时间和空间占用相对较高。
在查找算法的比较实验中，二分查找明显优于顺序查找，尤其是在数据规模较大时。
二分查找的平均执行时间远远小于顺序查找，并且占用的空间也更少。
结论通过本实验的比较，我们得出了一些结论。
首先，快速排序和归并排序是较优的排序算法，可以在大多数情况下获得较好的性能。
其次，二分查找是一种高效的查找算法，特别适用于已排序的数据集。
最后，我们也发现了一些排序和查找算法的局限性，比如冒泡排序和插入排序在大数据规模下性能较差。
总的来说，本实验为我们提供了对排序和查找算法性能的深入了解，同时也为我们在实际应用中选择合适的算法提供了一定的参考。
希望我们的实验结果能够对相关领域的研究和应用有所帮助。
注意事项：在磁盘上创建一个目录，专门用于存储数据结构实验的程序。
因为机房机器有还原卡，请同学们将文件夹建立在最后一个盘中，以学号为文件夹名。
实验八查找和排序一、实验目的掌握运用数据结构两种基本运算查找和排序,并能通过其能解决应用问题。
二、实验要求1．掌握本实验的算法。
2．上机将本算法实现。
三、实验内容为宿舍管理人员编写一个宿舍管理查询软件, 程序采用交互工作方式,其流程如下:建立数据文件，数据结构采用线性表，存储方式任选（建议用顺序存储结构），数据元素是结构类型（学号，姓名，性别，房号），元素的值可从键盘上输入，可以在程序中直接初始化。
数据文件按关键字（学号、姓名、房号）进行排序（排序方法任选一种），打印排序结果。
（注意字符串的比较应该用strcmp(str1,str2)函数）查询菜单: (查找方法任选一种)1. 按学号查询2. 按姓名查询3. 按房号查询打印任一查询结果（可以连续操作）。
参考：typedef struct {char sno[10];char sname[2];int sex; //以0表示女，1表示男int roomno;}DataType;struct SeqList{DataType *elem;int length;};void init(SeqList &L){L.elem=(DataType *)malloc(MAXSIZE*sizeof(DataType));L.length=0;}void printlist(SeqList L){ int i;cout<<" sno name sex roomno\n";for(i=0;i<L.length;i++)cout<<setw(7)<<L.elem[i].sno<<setw(10)<<L.elem[i].sname<<setw(3)<<L.elem[i].sex<<setw(6) <<L.elem[i].roomno<<endl;}。
数据结构复习--排序和查找现在正在学习查找和排序，为了节省时间提⾼效率，就正好边学习边整理知识点吧！知识点⼀：⼆分查找/折半查找1.⼆分查找的判定树（选择题）下列⼆叉树中，可能成为折半查找判定树（不含外部结点）的是： (4分)1.2.3.4.注：折半查找判定树是⼀棵⼆叉排序树，它的中序遍历结果是⼀个升序序列，可以在选项中的树上依次填上相应的元素。
虽然折半查找可以上取整也可以下取整但是⼀个查找判定树只能有⼀种取整⽅式。
如果升序序列是偶数个，那么终点应该偏左多右少。
在2选项中，由根节点左⼦树4个节点⽽右⼦树5个节点可以确定⽤的是向下取整策略，但是它的左⼦节点在左⼦树种对应的终点左边2个，右边个，明显是上取整策略，策略没有统⼀，所以是错的。
其他的选项类似分析。
2.⼆分查找法/折半查找法已知⼀个长度为16的顺序表L，其元素按关键字有序排列。
若采⽤⼆分查找法查找⼀个L中不存在的元素，则关键字的⽐较次数最多是： (2分)1. 72. 63. 54. 4 注：⼀次找到最边界的那⼀个树的情况下有最多次数 这个题中结点数16是个偶数：第⼀次（0+15）/2 7 第⼆次（8+15）/2 11第三次（12+15）/2 14 第四次（14+15）/2 14 第五次（15+15）/2 15（下取整的就向右计算求最多次数）第⼀次（0+15）/2 8 第⼆次（0+7）/2 4 第三次（0+3）/2 2 第四次（0+1)/2 0第五次（0+0）/2 0（下取整的话就向左求最多次数）若结点数是奇数15：第⼀次（0+14）/2 7 第⼆次（ 0+6）/2 3 第三次（0+2）/2 1第四次（0+0）/2 0第⼀次（0+14）/2 7 第⼆次（8+14）/2 11 第三次（12+14）/2 13第四次（14+14）/2 0这时候向左或者向右都是OK的（因为得到的数都是能够被2整除的）但是划重点了折半查找⼀个有序表中不存在的元素，若向下取整，则要最多⽐较[log2n]+1次，若向上取整，则要最多⽐较[log2(n+1)],其实就是求树的深度.（这⼀块⾃⼰的说法可能不够准确，希望⼤家看到有问题的可以指出来）结合实际，我们⽤[log2n]+1来算更简单并且计算[log2n]要取整数，因为可能会存在不是满⼆叉树的情况。
实验六数据查找与排序（3学时）实验性质：综合实验目的要求：1．理解各种查找的思想，实现对数据的查找。
例如用：直接查找法和折半查找法。
2．理解各种排序的思想，实现对数据的排序。
例如用：起泡排序和插入排序。
实验内容：1．任意输入10个整型数据，然后再输入一个数据进行查找。
设计的程序能对输入的数据进行查找，然后把数据所在的位置输出。
2．任意输入10个整型数据，并对输入的10个数据进行排序。
注意要点：实验中体会不同的查找、排序方法所具有的特点，关注其在效率上的不同。
直接查找#include <stdio.h>void main(){int a[10],i,n;printf("任意输入10个整形数:");for(i=0;i<10;i++){scanf("%d",&a[i]);}printf("再输入一个数据进行查找:");scanf("%d",&n);for(i=0;i<10;i++){if(n==a[i]){ break;}}if(i>=10){ printf("没有找到%d！",n); }else{ printf("找到了！the %d is at %d position",n,i); }}排序#include <stdio.h>#define NUM 10struct data{int value;int seat;} D[NUM],Dtmp;void main(){int i,j,k;printf("输入%d个整数:",NUM);for(i=0; i<NUM; D[i].seat=i++)scanf("%d",&D[i].value);printf("原始数据顺序:\n")for(i=0;i<NUM;i++) printf("%d ",D[i].value);for(i=0; i<NUM; i++)for(j=0;j<NUM-1-i;j++)if(D[j].value>D[j+1].value){Dtmp.value = D[j].value; D[j].value=D[j+1].value; D[j+1].value=Dtmp.value;Dtmp.seat = D[j].seat; D[j].seat=D[j+1].seat; D[j+1].seat=Dtmp.seat;}printf("排序后的数据:\n");for(i=0;i<NUM;i++) printf("%d[%d] ",D[i].value,D[i].seat);}。
排序与查找1.选择排序算法：N元数组a[0]~a[N-1]由小到大排序：第0步:找到a[0]~a[N-1]中的最小值元素与a[0]交换;第1步:找到a[1]~a[N-1]中的最小值元素与a[1]交换；第2步:找到a[2]~a[N-1]中的最小值元素与a[2]交换；…第i步:找到a[i]~a[N-1]中的最小值元素与a[i]交换;…第N-2步:找到a[N-2]~a[N-1]中的最小值元素与a[N-2]交换。
算法停止。
思考：由大到小排序算法如何改动？#include "stdio.h"#define N 10void SelSort(int a[N]) { /*选择排序函数*/int i,j,minj,t;for (i = 0;i < N-1;i++) {for (j = i + 1;j < N;j++)if(a[j] < a[i]) {t = a[i];a[i] = a[minj];a[minj] = t;}}}这样中间有些交换是没有必要的，设定一个minj变量记录当前一趟最小值的下标。
可以减少变量交换的次数。
改进如下：void SelSort(int a[N]) { /*改进选择排序函数*/int i,j,minj,t;for (i = 0;i < N-1;i++) {minj = i;for (j = i + 1;j < N;j++)if(a[j] < a[minj])minj = j;if(minj != i) {t = a[i];a[i] = a[minj];a[minj] = t;}}}void main(){int a[N],i;for(i = 0;i < N;i++)scanf("%d",a + i);SelSort(a);for (i = 0;i < N;i++)printf("%6d",a[i]);}2.插入排序引例：写一个函数，将一个整型数x插入到由小到大排列的整型数组a[0]~a[N-1]中，使得插入元素后的数组a[0]~a[N]保持升序。
查找和排序实验报告查找和排序实验报告一、引言查找和排序是计算机科学中非常重要的基础算法之一。
查找（Search）是指在一组数据中寻找目标元素的过程，而排序（Sort）则是将一组数据按照特定的规则进行排列的过程。
本实验旨在通过实际操作和实验验证，深入理解查找和排序算法的原理和应用。
二、查找算法实验1. 顺序查找顺序查找是最简单的查找算法之一，它的基本思想是逐个比较待查找元素与数据集合中的元素，直到找到目标元素或遍历完整个数据集合。
在本实验中，我们设计了一个包含1000个随机整数的数据集合，并使用顺序查找算法查找指定的目标元素。
实验结果显示，顺序查找的时间复杂度为O(n)。
2. 二分查找二分查找是一种高效的查找算法，它要求待查找的数据集合必须是有序的。
二分查找的基本思想是通过不断缩小查找范围，将待查找元素与中间元素进行比较，从而确定目标元素的位置。
在本实验中，我们首先对数据集合进行排序，然后使用二分查找算法查找指定的目标元素。
实验结果显示，二分查找的时间复杂度为O(log n)。
三、排序算法实验1. 冒泡排序冒泡排序是一种简单但低效的排序算法，它的基本思想是通过相邻元素的比较和交换，将较大（或较小）的元素逐渐“冒泡”到数列的一端。
在本实验中，我们设计了一个包含1000个随机整数的数据集合，并使用冒泡排序算法对其进行排序。
实验结果显示，冒泡排序的时间复杂度为O(n^2)。
2. 插入排序插入排序是一种简单且高效的排序算法，它的基本思想是将数据集合分为已排序和未排序两部分，每次从未排序部分选择一个元素插入到已排序部分的适当位置。
在本实验中，我们使用插入排序算法对包含1000个随机整数的数据集合进行排序。
实验结果显示，插入排序的时间复杂度为O(n^2)。
3. 快速排序快速排序是一种高效的排序算法，它的基本思想是通过递归地将数据集合划分为较小和较大的两个子集合，然后对子集合进行排序，最后将排序好的子集合合并起来。
实验七查找与排序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<stu[j+1].total)||((stu[j].total==stu[j+1].total)&&st u[j].math<stu[j+1].math)||(stu[j].total==stu[j+1].total)&&(stu[j ].math==stu[j+1].math)&&(stu[j].chinese<stu[j+1].chinese)||(s tu[j].total==stu[j+1].total)&&(stu[j].math==stu[j+1].math)&& (stu[j].chinese==stu[j+1].chinese)&&(stu[j].engilsh<stu[j+1].e ngilsh)||(stu[j].total==stu[j+1].total)&&(stu[j].math==stu[j+1]. math)&&(stu[j].chinese==stu[j+1].chinese)&&(stu[j].engilsh= =stu[j+1].engilsh)&&(stu[j].lizong<stu[j+1].lizong)，据此可以得到想要的排序结果。
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里使函数理解更加简洁主要功能函数的程序流程图：void zhijiecharu(struct data stu[],int count)void jiandanxuanze(struct data stu[],int count)void maopao(struct data stu[],int count)void gaokaopaiming(struct data stu[],int count)long load(FILE *cfptr)void shunxuchazhao(struct data stu[],int count)TNODE *creat(structdata stu[],int count)void zhebanchazhao(struct data stu[],int count)TNODE *find(TNODE *head)源代码：#include<stdio.h>#include<stdlib.h>#include<string.h>long size;struct data{double number;int chinese;int math;int engilsh;int lizong;int total;int order;char pici[10];}stu[200]; //顺序存储struct tnode{struct data s;struct tnode *lchild,*rchild;};typedefstruct tnode TNODE;long getlong(FILE *cfptr);//记录学生人数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);//根据总分进行冒泡排序void gaokaopaiming(struct data stu[],int count);//根据总成绩、数学、语文、英语、理综的顺序进行排序void shunxuchazhao(struct data stu[],int count);//顺序查找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);//快速排序的“主函数”void merge(struct data stu[],struct data stu_s[],int l,int m,int n);//归并两个有序序列void mergepass(struct data stu[],struct data stu_s[],int count);//2—路归并排序执行一趟的算法void mergesort(struct data stu[],struct data stu_s[],int count);//2—路归并排序void guibingpaixu(struct data stu[],int count);//归并排序的“主函数”long getlong(FILE *cfptr)//统计一共的考生人数{long begin,end,count;fseek(cfptr,0,SEEK_SET);begin=ftell(cfptr);fseek(cfptr,size,SEEK_END);end=ftell(cfptr);count=(end-begin)/size-1;return count;}long load(FILE *cfptr)//将txt文档里的考生信息读入数组中{int i;long count;fseek(cfptr,0,SEEK_SET);count=getlong(cfptr);fseek(cfptr,0,SEEK_SET);for(i=1;i<=count;i++){fscanf(cfptr,"%lf %d %d %d %d %d %d %s",&stu[i].number,&stu[i].chinese,&stu[i].math,&stu[i]. engilsh,&stu[i].lizong,&stu[i].total,&stu[i].order,stu[i].pici);}return count;}void paixu(struct data stu[],int count)//排序{int choice1,flag1=1;while(flag1){printf("3 直接插入排序 4 简单选择排序 5 冒泡排序 6 高考总排名 12 快速排序 13 归并排序7 退出排序\n");scanf("%d",&choice1);switch(choice1){case 3:zhijiecharu(stu,count);break;case 4:jiandanxuanze(stu,count);break;case 5:maopao(stu,count);break;case 6:gaokaopaiming(stu,count);break;case 12:kuaisupaixu(stu,count);break;case 13:guibingpaixu(stu,count);break;case 7:flag1=0;break;}}}void zhijiecharu(struct data stu[],int count)//按数学成绩直接插入排序{int i,j;for(i=count-1;i>=1;i--){stu[count+1]=stu[i];j=i+1;while(stu[count+1].math<=stu[j].math){stu[j-1]=stu[j];j++;}stu[j-1]=stu[count+1];}printf("按数学成绩直接插入后\n");printf(" 考号语文数学英语理综总分排名录取批次\n");for(i=1;i<=count;i++){printf("%0.f %d %d %d %d %d %d %s \n",stu[i].number,stu[i].chinese,stu[i].math,stu[i].engilsh,stu[i].lizong,stu[i].total,stu[i]. order,stu[i].pici);}}void jiandanxuanze(struct data stu[],int count)//根据语文成绩简单排序{int i,j,k;struct data temp;for(i=1;i<count;i++){k=i;for(j=i+1;j<=count;j++)if(stu[j].chinese>stu[k].chinese)k=j;if(i!=k){temp=stu[k];stu[k]=stu[i];stu[i]=temp;}}printf("按语文成绩简单选择后\n");printf(" 考号语文数学英语理综总分排名录取批次\n");for(i=1;i<=count;i++){printf("%0.f %d %d %d %d %d %d %s \n",stu[i].number,stu[i].chinese,stu[i].math,stu[i].engilsh,stu[i].lizong,stu[i].total,stu[i]. order,stu[i].pici);}}void maopao(struct data stu[],int count)//根据总分进行冒泡排序{struct data temp;int i,j;for(i=1;i<count;i++)for(j=1;j<count-i;j++)if(stu[j].total<stu[j+1].total){temp=stu[j];stu[j]=stu[j+1];stu[j+1]=temp;}printf("按总分冒泡排序后\n");printf(" 考号语文数学英语理综总分排名录取批次\n");for(i=1;i<=count;i++){printf("%0.f %d %d %d %d %d %d %s \n",stu[i].number,stu[i].chinese,stu[i].math,stu[i].engilsh,stu[i].lizong,stu[i].total,stu[i]. order,stu[i].pici);}}void gaokaopaiming(struct data stu[],int count)//根据总成绩、数学、语文、英语、理综的顺序进行排序{struct data temp;int i,j;for(i=1;i<count;i++)for(j=1;j<count-i;j++)if((stu[j].total<stu[j+1].total)||((stu[j].total==stu[j+1].total)&&stu[j].math<stu[j+1] .math)||(stu[j].total==stu[j+1].total)&&(stu[j].math==stu[j+1].math)&&(stu[j].chinese<stu[j+ 1].chinese)||(stu[j].total==stu[j+1].total)&&(stu[j].math==stu[j+1].math)&&(stu[j].chinese== stu[j+1].chinese)&&(stu[j].engilsh<stu[j+1].engilsh)||(stu[j].total==stu[j+1].total)&&(stu[j ].math==stu[j+1].math)&&(stu[j].chinese==stu[j+1].chinese)&&(stu[j].engilsh==stu[j+1].engils h)&&(stu[j].lizong<stu[j+1].lizong)){temp=stu[j];stu[j]=stu[j+1];stu[j+1]=temp;}printf("按总成绩、数学、语文、英语、理综的规则排序后\n");printf(" 考号语文数学英语理综总分排名录取批次\n");for(i=1;i<=count;i++){printf("%0.f %d %d %d %d %d %d %s \n",stu[i].number,stu[i].chinese,stu[i].math,stu[i].engilsh,stu[i].lizong,stu[i].total,stu[i]. order,stu[i].pici);}}int qpass(struct data stu[],int low ,int high)//快速排序中序列的划分算法{int i,j,k;struct data temp;i=low;j=high;temp=stu[low];k=stu[low].total;while(i<j)while((i<j)&&(stu[j].total<=k))j--;stu[i]=stu[j];while((i<j)&&(stu[i].total>k))i++;stu[j]=stu[i];}stu[i]=temp;return i;}void quicksort(struct data stu[],int low,int high)//快速查找递归算法{int i;if(low<high){i=qpass(stu,low,high);quicksort(stu,low,i-1);quicksort(stu,i+1,high);}}void kuaisupaixu(struct data stu[],int count)//快速查找递归算法{int i;quicksort(stu,1,count);printf("按总成绩、数学、语文、英语、理综的规则排序后\n");printf(" 考号语文数学英语理综总分排名录取批次\n");for(i=1;i<=count;i++){printf("%0.f %d %d %d %d %d %d %s \n",stu[i].number,stu[i].chinese,stu[i].math,stu[i].engilsh,stu[i].lizong,stu[i].total,stu[i]. order,stu[i].pici);}}void merge(struct data stu[],struct data stu_s[],int l,int m,int n)//归并两个有序序列{int i,j,k;i=l;j=m+1;k=l;while((i<=m)&&(j<=n))if(stu[i].total<=stu[j].total){stu_s[k]=stu[i];i++;}else{stu_s[k]=stu[j];j++;}k++;}if(i>m)for(;j<=n;j++,k++)stu_s[k]=stu[j];elsefor(;i<=m;i++,k++)stu_s[k]=stu[i];}void mergepass(struct data stu[],struct data stu_s[],int L,int n)//2—路归并排序执行一趟的算法{int i,j;i=1;while(i+2*L-1<=n){merge(stu,stu_s,i,i+L-1,i+2*L-1);i=i+2*L;}if(i+L-1<n)merge(stu,stu_s,i,i+L-1,n);elsefor(j=i;j<=n;j++)stu_s[j]=stu[j];}void mergesort(struct data stu[],struct data stu_s[],int n)//2—路归并排序{int L,i;L=1;while(L<n)mergepass(stu,stu_s,L,n);L=2*L;if(L<n){mergepass(stu,stu_s,L,n);L=2*L;}for(i=1;i<=n;i++){stu[i]=stu_s[i];}}}void guibingpaixu(struct data stu[],int count)//归并排序的“主函数”{int i;struct data stu_s[250];mergesort(stu,stu_s,count);printf("按总分排序后：\n");printf(" 考号语文数学英语理综总分排名录取批次\n");for(i=1;i<=count;i++){printf("%0.f %d %d %d %d %d %d %s \n",stu[i].number,stu[i].chinese,stu[i].math,stu[i].engilsh,stu[i].lizong,stu[i].total,stu[i]. order,stu[i].pici);}}void chazhao(struct data stu[],int count)//查找{int choice2,flag2=1;TNODE *head,*q;while(flag2){printf("8 顺序查找 9 折半查找 11 二叉排序树查找10 退出查找\n");scanf("%d",&choice2);switch(choice2){case 8:shunxuchazhao(stu,count);break;case 9: exchange(stu,count);zhebanchazhao(stu,count);break;case 10:flag2=0;break;case 11:{head=creat(stu,count);q=find(head);printf(" 考号语文数学英语理综总分排名录取批次\n");printf("%0.f %d %d %d %d %d %d %s \n",q->s.number,q->s.chinese,q->s.math,q->s.engilsh,q->s.lizong,q->s.total,q->s.order,q->s.pic i);}}}}void shunxuchazhao(struct data stu[],int count)//根据排名顺序查找{int i,k;printf("请输入您要查找的学生的全省排名：\n");scanf("%d",&k);for(i=1;i<=count;i++)if(stu[i].order==k){printf(" 考号语文数学英语理综总分排名录取批次\n");printf("%0.f %d %d %d %d %d %d %s \n",stu[i].number,stu[i].chinese,stu[i].math,stu[i].engilsh,stu[i].lizong,stu[i].total,stu[i]. order,stu[i].pici);break;}if(i>count)printf("您的输入有误！数据库中没有储存该排名的学生！\n");}void zhebanchazhao(struct data stu[],int count)//折半查找{int k,low,high,mid,flag3=1;low=1;high=count;printf("请输入您要查找的总分数对应的学生：\n");scanf("%d",&k);while(low<=high){mid=(low+high)/2;if(k==stu[mid].total){printf("您要查询的学生是：\n");printf(" 考号语文数学英语理综总分排名录取批次\n");printf("%0.f %d %d %d %d %d %d %s \n",stu[mid].number,stu[mid].chinese,stu[mid].math,stu[mid].engilsh,stu[mid].lizong,stu[mid].t otal,stu[mid].order,stu[mid].pici);flag3=0;break;}elseif(k>stu[mid].total)low=mid+1;elsehigh=mid-1;}if(flag3==1)printf("您的输入有误！数据库中没有储存该分数的学生！\n");}void exchange(struct data stu[],int count){int i,j;struct data temp;for(i=1;i<count;i++)for(j=1;j<count-i;j++)if(stu[j].total>stu[j+1].total){temp=stu[j];stu[j]=stu[j+1];stu[j+1]=temp;}}TNODE *creat(struct data stu[],int count) //生成二叉树根据总分对学生信息进行排序{TNODE *head,*s,*p,*q;int i;head=NULL;for(i=1;i<=count;i++){s=(TNODE *)malloc(sizeof(TNODE));s->s.chinese=stu[i].chinese;s->s.engilsh=stu[i].engilsh;s->s.lizong=stu[i].lizong;s->s.math=stu[i].math;s->s.number=stu[i].number;s->s.order=stu[i].order;s->s.total=stu[i].total;strcpy(s->s.pici,stu[i].pici);s->lchild=NULL;s->rchild=NULL;if(head==NULL)head=s;else{p=head;while(p!=NULL){q=p;if(s->s.total<p->s.total)p=p->lchild;elsep=p->rchild;}if(s->s.total<q->s.total)q->lchild=s;elseq->rchild=s;}}return head;}TNODE *find(TNODE *head) //根据总分进行查询，返回要查询的结点地址{TNODE *p;int m;p=head;printf("请输入你要查询的总分：");scanf("%d",&m);while(p!=NULL){if(p->s.total==m)return p;elseif(p->s.total>m)p=p->lchild;elsep=p->rchild;return p;}}int main(){FILE *fp;int choice,flag=1;long count;//记录学生总数if((fp=fopen("d:\\order.txt","rb+"))==NULL){printf("cannot open file cashbox.dat!\n");exit(0);}size=sizeof(struct data);//一个结构体占空间的大小count=load(fp);printf("**************高考成绩数据系统**************\n"); while(flag){printf("******* 1 排序 2 查找 3 退出 *******\n");scanf("%d",&choice);switch(choice){case 1:paixu(stu,count);printf("\n");break;case 2:chazhao(stu,count);printf("\n");break;case 3:flag=0;break;}}return 0;}运行结果：排序：功能3：功能4：功能5：功能6：功能12：功能13：查找：功能8：功能9：功能11：。
