查找与排序_实验报告讲解.doc

西安交通大学实验报告 课程 数据结构 实验名称 查找与排序应用 第 1 页 共 页 系别__ 自动化 实 验 日 期 / 2014 年 12 月 6 日 专业班级 自动化43班 实 验 报 告 日 期 2014 年 12月 12 日 姓名 李欣阳 学号 2140504066 报 告 退 发 ( 订正 、 重做 ) 同 组 人 无 教 师 审 批 签 字 一、实验目的 1. 掌握多个关键字排序方法与实现； 2. 能利用LSD策略和分配收集策略解决实际的排序问题； 3. 进一步联系栈、队列、结构体的使用。 二、实验内容与要求 基本要求：按用户给定的进行排序的关键字的优先关系，输出排序结果。 内容提要：在进行高考分数处理时，除了需对总分进行排序外，不同专业对单科分数要求不同，因此尚需在总分相同的情况下，按用户提出的单科分数的次序要求排出考生录取的次序，待排序的记录数不少于100个，表中记录包括3门课程成绩和总分，单科成绩范围均为0至100。 （1）单科成绩通过随机方法产生，并且定义成绩优先级：总分优先级最高，单科成绩的优先级自行定义。 （2）采用两类策略进行排序： a.其一采用LSD策略进行多关键字的排序，至少实现3类稳定排序算法（如直接插入排序，折半插入排序等）来对总分和单科成绩进行分别排序，得到最终排序结果，不同的关键字可以采用不同的排序算法进行。 b.其二是利用“分配”和“收集”策略，得到最终排序结果。 （3）在实验报告中并综合比较这两类策略的复杂度。 三、问题分析 3.1 基于LSD策略的多关键字排序方法 LSD算法全称是最低位优先排序法，是实现多个不同优先级关键字排序的一种方法。假设一组记录序列有多个关键字（K1，K2，K3，…,KnKn相同的记录按Kn-1排，Kn-1相同的记录按 Kn-1并以此类推First指针始终指向最小值，last指针始终指向最大值。若当前元素比第一个元素大则放在当前元素的后面，否则放前面，待所有元素插入完全以后将首尾连接起来形成一个循环的链表。 冒泡排序：将元素进行两两比较，小的往下移。用两个循环嵌套即可完成全部排序。 3.3分配和收集策略排序 由于学生各科成绩分布在0-100区间内，总分成绩是分布在0-300区间内的任意随机数，因此要实现对各科成绩的分配，需要301个连队列来存储关键字不同的学生成绩记录，其中在对英语、语文、数学排序时只用到编号为0-100的连队列只有在按总分排序时才会用到CreateRec：用于生成待排序的成绩记录序列。实现该函数需要调用标准函数库#includetime.h，基于系统时间产生 int n=4; printf(-----------------------------高考成绩原始记录----------------------------------\n); printf( 序号 英语 语文 数学 总分\n); srand((unsigned)time(NULL)); for (i=0; ipeople; i++) { sr[i].key[n-1]=0; sr[i].order=i+1; ar[i][0]=sr[i].order; printf(%6d,sr[i].order); for(j=0;jn-1;j++) { sr[i].key[j]=rand()%100; ar[i][j+1]= sr[i].key[j]; sr[i].key[n-1]=sr[i].key[n-1]+sr[i].key[j]; ar[i][4]=sr[i].key[n-1]; printf( %6d,sr[i].key[j]); } printf( %6d,sr[i].key[n-1]); printf(\n); } } （3）成绩序列输出函数Print：其作用是输出结构体形式存储的学生成绩序列，实现方式就是利用循环结构逐次输出，此处不再详细解释。 void Print(score sr[],int people){ //记录输出函数 printf(