数据结构实验解答 排序问题 需要实例
1.设n个学生数据信息（学号、姓名及多门课程的成绩）已存放在一个文件，以顺序表作为学生信息的存储结构，从文件中读取所有学生数据信息创建学生信息表。完成如下实验内容：
（1）堆排序思想求解k大值：从文件中读取所有学生数据信息创建学生信息表；利用堆排序算法思想，从所有的学生数据中求解出前k个最高总成绩，并显示这些学生信息；
（2）快速排序求第k大值：从文件中读取所有学生数据信息创建学生信息表，利用快速排序思想，从所有的学生数据中求解出总成绩为第k大的学生信息并显示。
2.针对以上每个实验内容，编写相应的测试程序，并选取适当的测试数据，通过运行结果验证算法和程序设计的正确性，并进一步验证排序方法的稳定性，并分析、比较不同排序算法的效率。
这是要把所有的排序算法都弄一遍啊。。。。
数据文件内容（第一行是学生人数，后面每一行表示：学号、姓名、课程1成绩、课程2成绩、总成绩）：
5
1 井自玄 76 81 157
2 王丹阳 97 89 186
3 王帅华 72 63 135
4 王昊 85 64 149
5 刘琦 65 91 156
（1）堆排序
代码：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef struct _student
{
int id;
char name[20];
int kc1;
int kc2;
int zcj; //总成绩
}Student;
//定义顺序表
typedef struct _node
{
Student stu[MAXSIZE];
int size;
}LinkNode;
//堆排序
void swap(Student array[], int x, int y) {
Student key = array[x];
array[x] = array[y];
array[y] = key;
}
// 从小到大排序
void Down(Student array[], int i, int n) { // 最后结果就是大顶堆
int parent = i; // 父节点下标
int child = 2 * i + 1; // 子节点下标
while (child < n) {
if (child + 1 < n && array[child].zcj < array[child + 1].zcj) { // 判断子节点那个大，大的与父节点比较
child++;
}
if (array[parent].zcj < array[child].zcj) { // 判断父节点是否小于子节点
swap(array, parent, child); // 交换父节点和子节点
parent = child; // 子节点下标 赋给 父节点下标
}
child = child * 2 + 1; // 换行，比较下面的父节点和子节点
}
}
void BuildHeap(Student array[], int size) {
for (int i = size / 2 - 1; i >= 0; i--) { // 倒数第二排开始, 创建大顶堆，必须从下往上比较
Down(array, i, size); // 否则有的不符合大顶堆定义
}
}
void HeapSort(Student array[], int size) {
BuildHeap(array, size); // 初始化堆
for (int i = size - 1; i > 0; i--) {
swap(array, 0, i); // 交换顶点和第 i 个数据
// 因为只有array[0]改变，其它都符合大顶堆的定义，所以可以从上往下重新建立
Down(array, 0, i); // 重新建立大顶堆
}
}
//显示数组
void showAll(LinkNode ls,int n)
{
int i,j=0;
printf("--------------------------------------------------------------\n");
printf("%6s %10s %6s %6s %6s\n","学号","姓名","课程1","课程2","总成绩");
printf("--------------------------------------------------------------\n");
for(i=ls.size-1;i>=0 && j<n;i--,j++)
printf("%6d %10s %6d %6d %6d\n",ls.stu[i].id,ls.stu[i].name,ls.stu[i].kc1,ls.stu[i].kc2,ls.stu[i].zcj);
}
int main()
{
LinkNode ls;
int i=0,k;
FILE *fp =fopen("studata2.txt","r");
ls.size = 0;
printf("请输入k的值：");
scanf("%d",&k);
//读文件
if(fp == 0)
{
printf("文件打开失败\n");
return 0;
}
fscanf(fp,"%d",&ls.size); //得到学生总数
for(i=0;i<ls.size && (!feof(fp));i++)
{
fscanf(fp,"%d %s %d %d %d",&ls.stu[i].id,ls.stu[i].name,&ls.stu[i].kc1,&ls.stu[i].kc2,&ls.stu[i].zcj);
}
fclose(fp);
//堆排序
HeapSort(ls.stu,ls.size);
showAll(ls,k);
return 0;
}
（2）快速排序代码（测试数据一样，运行结果也一样，就不贴图了）：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef struct _student
{
int id;
char name[20];
int kc1;
int kc2;
int zcj; //总成绩
}Student;
//定义顺序表
typedef struct _node
{
Student stu[MAXSIZE];
int size;
}LinkNode;
//快速排序
void QuickSort(Student nums[],int L ,int R){
int i,j=L;
Student temp,k=nums[R];
if(L<R){
for(i=L;i<R;i++){
if(nums[i].zcj<k.zcj){
temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
j++;
}
}
temp=nums[R];
nums[R]=nums[j];
nums[j]=temp;
QuickSort(nums,L,j-1);
QuickSort(nums,j+1,R);
}
return ;
}
//显示数组
void showAll(LinkNode ls,int n)
{
int i,j=0;
printf("--------------------------------------------------------------\n");
printf("%6s %10s %6s %6s %6s\n","学号","姓名","课程1","课程2","总成绩");
printf("--------------------------------------------------------------\n");
for(i=ls.size-1;i>=0 && j<n;i--,j++)
printf("%6d %10s %6d %6d %6d\n",ls.stu[i].id,ls.stu[i].name,ls.stu[i].kc1,ls.stu[i].kc2,ls.stu[i].zcj);
}
int main()
{
LinkNode ls;
int i=0,k;
FILE *fp =fopen("studata2.txt","r");
ls.size = 0;
printf("请输入k的值：");
scanf("%d",&k);
//读文件
if(fp == 0)
{
printf("文件打开失败\n");
return 0;
}
fscanf(fp,"%d",&ls.size); //得到学生总数
for(i=0;i<ls.size && (!feof(fp));i++)
{
fscanf(fp,"%d %s %d %d %d",&ls.stu[i].id,ls.stu[i].name,&ls.stu[i].kc1,&ls.stu[i].kc2,&ls.stu[i].zcj);
}
fclose(fp);
//堆排序
QuickSort(ls.stu,0,ls.size-1);
showAll(ls,k);
return 0;
}
回答：对于快速排序和堆排序求前K大数据，需要对快速排序和堆排序的原理理清楚，这里的结构体和文件输入输出并不十分困难，所以只写了简单的数组版本，根据最原始的快排和堆排进行更改的；代码如下：
#include <stdio.h>
#define MAX_SIZE 20
typedef int Type;
void printArr(Type arr[], int length)
{
int i;
for (i = 0; i < length; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int Partition(Type arr[], int low, int high)
{
Type temp = arr[low];
Type pivot = arr[low];
while (low < high)
{
while (low < high && arr[high] >= pivot)
{
high--;
}
arr[low] = arr[high];
while (low < high && arr[low] <= pivot)
{
low++;
}
arr[high] = arr[low];
}
arr[low] = temp;
return low;
}
void quickSort(Type arr[], int low, int high, int length, int k)
{
if (low < high)
{
int pivot = Partition(arr, low, high);
if(pivot < k)
{
quickSort(arr, low, pivot - 1, length, k);
}
else
{
quickSort(arr, pivot + 1, high, length, k);
}
}
printArr(arr, length);
}
int main()
{
Type arr[] = { 5, 3, 1, 7, 9, 2, 4, 6, 8, 10 };
int length = sizeof(arr) / sizeof(Type);
int k = 6;
quickSort(arr, 0, length - 1, length, k);
printf("%d", arr[length - k]);
}
#include <stdio.h>
#define MAX_SIZE 20
typedef int Type;
void printArr(Type arr[], int length)
{
int i;
for (i = 0; i < length; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
void heapAdjust(Type arr[], int low, int high)
{
Type temp = arr[low];
int i;
for (i = 2 * low; i < high; i *= 2)
{
if (i < high && arr[i] < arr[i + 1])
{
i++;
}
if (temp >= arr[i])
{
break;
}
arr[low] = arr[i];
low = i;
}
arr[low] = temp;
}
void createHeap(Type arr[], int length)
{
int i;
for (i = length / 2; i >= 0; i--)
{
heapAdjust(arr, i, length);
}
}
void heapSort(Type arr[], int length, int k)
{
createHeap(arr, length);
int i;
Type temp;
for (i = length - 1; i > length - k - 1; i--)
{
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapAdjust(arr, 0, i - 1);
printArr(arr, length);
}
}
int main()
{
Type arr[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 };
int length = sizeof(arr) / sizeof(Type);
int k = 5;
heapSort(arr, length, k);
}
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632