数据结构课程设计报告(完整版本)-
/*
第八题：研究生入学考试成绩处理
1、需求分析：
假设某大学计算机应用技术专业招收研究生n名，现在要根据报考者的考试成绩择优录取。考试课程有政治、英语、数学、专业综合四门。考试成绩分为两类：第一类为每门课程都达到最低录取线；第二类为有一门或多门课程未达到最低录取线。录取方法是在每门课程达到最低录取线的考生中按总分从高到低录取。试设计一个成绩处理程序实现以上功能。
根据录取方法，打印输出n份录取通知书，列出录取者四门课程的成绩及总分（要求采用堆排序）。并能实现对任一考生或任一门课程成绩的查找（要求两种查找方式，根据考号或姓名进行查找，采用高效的查找算法）。录取通知书的格式如下：
2、设计 2．1设计思想： （1）数据结构设计
由于本题明确要求在进行排序时必须采用推排序的算法，而堆排序最常采用的数据存储结构便是顺序表存储结构，因此在我的设计中是采用的结构体数组将各个学生的信息进行存储，同时这也方便排序算法的实现。
typedef struct { string name; int Politics; int English; int Mathematics; int Major; int Total; string Num; }Student;
21 / 33
数据结构课程设计报告(完整版本)-
（2）算法设计
由于题目要求本程序的查找是针对考号和姓名两种方式进行查找的，而不是针对相应的可比较的数据进行查找，所以像二叉查找和二叉排序树这些查找方法基本都用不上，因此本程序采用的是“蛮力”查找的方法，及对整个结构体数组进行遍历，而与要查找的信息一一进行对比，只不过在进行比较的过程中用的是string类中的重载“=”，这样更加的方便快捷。 而堆排序的算法，由于学生成绩的录取是一个从高分到低分排序的过程，因此推排序的算法就是一个建立“大顶堆”的过程。
2.2设计表示 （1）、函数调用关系图及其说明如下 :
(2)函数接口说明：
22 / 33
数据结构课程设计报告(完整版本)-
由于个人的喜爱不同，而本人在参数传递的过程中喜欢用引用和指针进行传递，因此本程序用的是指针进行传递，因而每个参数都相当于全局变量，这样在接口方面方便而且不用重新开辟其他的空间。
主要函数如下:
Int HeapAdjust(Student (&S_USE)[MAX_SIZE],int s,int m);//堆排序
int HeapSort(Student (&S_USE)[MAX_SIZE]);//调整 int PanDuan(Student (&S_ALL)[MAX_SIZE],Student (&S_USE)[MAX_SIZE],Student (&S_UNUSE)[MAX_SIZE]);//判断该研究生是否有录取资格 才能进行堆排序
int Find(Student (&S_ALL)[MAX_SIZE]);//查找成绩 int Display();//输出成绩单
int PutIn(Student &S);//成绩录入 2.3详细设计
由于查找的算法是用的“蛮力”的算法，而对成绩的录入也非常的简单，因此详细设计这一块主要说说堆排序的详细设计算法。
堆排序的详细设计分析：首先题目要求是按四门课程的总分进行排序，由此我们知道我们要建立的堆是一个“大顶堆”，而建堆过程中主要解决的两个问题是：（1）如何由一个无序序列建成一个堆？（2）如何在输出堆元素之后，调整剩余的元素成为一个新的堆？在无序序列建立堆的过程中在我的程序中是用HeapAdjust()这个函数实现的，将建堆的过程看做事一个反复筛选的过程，则只需从从最后一个非终端断点n/2的下界开始向前一次进行筛选，若所比较的元素比其后继的元素要小则不需要进行交换，否则需要该元素与其父节点进行交换。即该过程中每一步都是将二叉树的子树建立成一个小顶堆的过程，这主要是方便在后面调整的过程中将堆顶元素和最后一个元素进行交换，即将其从大到小排序的过程。
int HeapAdjust(Student (&S_USE)[MAX_SIZE],int s,int m) { Student rc; int j; rc=S_USE[s]; for(j=2*s;j<=m;j*=2) { if(j 而调整的过程比较简单，即将队堆顶的元素与顺序表的最后一个元素 23 / 33 数据结构课程设计报告(完整版本)- 进行交换，然后将剩下的元素建堆的一个过程，主要函数实现如下： int HeapSort(Student (&S_USE)[MAX_SIZE]) { int i; Student tmp; for(i=count_U;i>=0;i--) S_USE[i]=S_USE[i-1]; //cout<<\ for(i=count_U/2;i>0;i--)//要不要减一 先记在这里 HeapAdjust(S_USE,i,count_U); for(i=count_U;i>1;i--) { tmp=S_USE[1]; S_USE[1]=S_USE[i]; S_USE[i]=tmp; HeapAdjust(S_USE,1,i-1); } for(i=0;i 3、调试分析 印象最深刻的是在二叉树的第一个元素是下标从1开始，而顺序表的数组的下标是从0开始，这个细节总会导致内存出错，最后通过在堆排序过程中，先将数组后移，排序完后将数组在前移解决了这个问题，因此印象较为深刻，其他的调试错误，一般都是在程序测试的过程中一一改正，问题不大。 4、用户手册 点击运行程序，在弹出的窗口中，会提示要输入的信息： 7、 首先提示输入的是学生的个数：此时输入你所需要输入的学 生的个数即可。 8、 提示信息为“请按照学生的姓名、政治、英语、数学和专业 综合的分数以及考号依次进行输入”：按照学生的信息一一进行输入即可 9、 提示信息为“请输入要录取学生的个数：”此时用户输入要录 取学生的个数，窗口中便会显示出录取学生的信息 10、 然后便是查找的过程，用户按提示进行输入，便可按考号和 姓名两种方式对所需要的信息进行查找。 5 测试数据及测试结果 在测试的过程中我一共用到了如下26组数据： aaa 97 98 85 91 1001 bbb 56 89 45 97 1002 24 / 33