《数据结构课程设计报告-多关键字排序的实现》由会员分享，可在线阅读，更多相关《数据结构课程设计报告-多关键字排序的实现（17页珍藏版）》请在金锄头文库上搜索。
1、学 号： 0120810340631课 程 设 计课程名称 数据结构设计题目 多关键字排序的实现班 级 0806 班姓 名 张军指导教师 姚寒冰2010 年 7 月 2 日1课程设计任务书学生姓名： 张 军 专业班级： 0806 班 指导教师： 姚寒冰 工作单位： 计算机科学系 题 目: 多关键字排序的实现 初始条件：利用多关键字排序进行高考分数处理，除了需对总分进行排序外，不同的专业对单科分数的要求不同，因此在总分相同的情况下，按用户提出的单科分数的次序要求排出考生录取的次序（详见题集 p169） 。假设待排序的记录数不超过 1000，表中记录的关键字数不超过 5，各个关键字的范围均为 0
2、至 100。按用户给定的进行排序的关键字的优先关系，输出排序结果。测试用例自己设计。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）课程设计报告按学校规定格式用 A4 纸打印（书写） ，并应包含如下内容： 1、 问题描述简述题目要解决的问题是什么。2、 设计存储结构设计、主要算法设计（用类 C 语言或用框图描述） 、测试用例设计；3、 调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4、 经验和体会（包括对算法改进的设想）5、 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出，6、 设计
3、报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为 0 分。时间安排：1、第 18 周（6 月 28 日至 7 月 2 日）完成。2、7 月 2 日 8：00 到计算中心检查程序、交课程设计报告、源程序（CD 盘） 。指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日21 设计题目:多关键字排序的程序设计2 问题描述:利用多关键字排序进行高考分数处理，除了需对总分进行排序外，不同的专业对单科分数的要求不同，因此在总分相同的情况下，按用户提出的单科分数的次序要求排出考生录取的次序3 设计我设计的程序是有数学、英语、语文、理综 4 科各为 0 到 100 分。按照总分、数学
4、、英语、语文、理综的优先顺序进行排序。由于本实验约定按 LSD 进行多关键字的排序。在对个关键字进行排序时采用两种策略：其一是利用稳定的内部排序法，其二是利用“分配”和“收集”的方法。所以我设计了两个程序。首先他们都是以最低位优先来排序的，由于有总分参与排序，可以不考虑理综的分数，故先按照语文分数从高到低排，再按照英语分数排，然后是数学、总分。第一个程序我用的是选择排序法，以单链表储存，因为要求是稳定的内部排续法，所以在每趟找到最大值之后将该结点插入到已排好的结点之后，以满足它是稳定的。第二个程序我参考了教材上 288 页的“分配” 、 “收集”的算法，用静态链表存储分数。在一趟排序中，将结点
5、分配到相应的链队列中去，再按从高到低链接起来。两个程序以相同的操作界面演示。按数学、英语、语文、理综的顺序输入成绩，输入 1 或 0 确定是否还有考生。当输入 0 确定所有考生都已输入时，则按名次顺序输出考生的名次和分数。由于本次设计上交.exe 文件，直接双击它运行完后不会停留在 Press any key to 3continue 所以输出的结果一闪而过，我在最后加了如下代码：cout*c;使程序能够在这里停一下，来观察输出的结果。3.1 数据结构设计稳定的内部排序法：struct studentint rank;/名次float math,english,chinese,science,
6、total;student *next;ADT student数据对象：D=a i|ai|属于 student，i=1 ，2，.,n,n=0数据关系：R1=|ai-1,ai 属于 D，i=2 ，.，n基本操作：student *Creat()操作结果：用链表接收考生的各科成绩。void Insert(student *p,student *q,student *h)初始条件：p 和 q 为指向链表中两个节点的指针，h 为指向头节点的指针。操作结果：将 q 指向的节点插到 p 指向的节点之前。void Rank(student *h)初始条件：h 指向储存有各考生成绩链表的头节点。操作结果：把指
7、针按总分、数学、英语、语文、理综的优先顺序重新排列。void ShowRank(student *h)初始条件：h 指向储存有各考生成绩链表的头节点。操作结果：按名次顺序输出考生的名次和分数。ADT student4“分配”和“收集”的排序：#define MAX_NUM_OF_KEY 5#define RADIX 101#define MAX_SPACE 1000struct SLCellfloat keysMAX_NUM_OF_KEY;int next;struct SLListSLCell rMAX_SPACE;int keynum;int recnum;ADT SLList数据对象：D
8、：D=a|a 属于 SLList数据关系：R ：数据元素同属一个集合。基本操作：P：SLList Creat()操作结果：用 SLList 接收考生的各科成绩。void Distribute(SLCell *r,int i,int *f,int *e)初始条件：存在以 i 为下标的关键字。操作结果：以下标为 i 的关键字为准做一趟分配。void Collect(SLCell *r,int i,int *f,int *e)初始条件：存在以 i 为下标的关键字。操作结果：以下标为 i 的关键字为准做一趟收集。void RadixSort(SLList *l)操作结果：对*l 中的成绩做链式基数排序
9、。void ShowRank(SLList *l)操作结果：按名次顺序输出考生的名次和分数。ADT SLList53.2 主要算法设计稳定的内部排序法：void Rank(student *h)/把指针按总分、数学、英语、语文、理综的优先顺序重新排列student *p,*s,*l;int r=1;for(p=h-next;p;p=s-next)/对语文成绩排序s=p;l=p;for(;l;l=l-next)/从 p 所指向的节点开始向后找最高分的节点，用 s 指向它if(s-chinesechinese) s=l;Insert(p,s,h);for(p=h-next;p;p=s-next)/
10、对英语成绩排序s=p;l=p;for(;l;l=l-next)if(s-englishenglish) s=l;Insert(p,s,h);for(p=h-next;p;p=s-next)/对数学成绩排序s=p;l=p;for(;l;l=l-next)if(s-mathmath) s=l;Insert(p,s,h);for(p=h-next;p;p=s-next)/对总分排序s=p;l=p;6for(;l;l=l-next)if(s-totaltotal) s=l;Insert(p,s,h);s-rank=r+;/记录名次“分配”和“收集”的排序：void Distribute(SLCell
11、*r,int i,int *f,int *e)/以下标为 i 的关键字为准做一趟分配int j,p;for(j=RADIX-1;j=0;-j) fj=0;/各字表初始化为空表for(p=r0.next;p;p=rp.next)j=rp.keysi;if(!fj) fj=p;else rej.next=p;ej=p;/将下标 p 所指的节点插入第 j 个子表中void Collect(SLCell *r,int i,int *f,int *e)/做一趟收集int j,t;for(j=RADIX-1;!fj;j-);/找第一个非空子表r0.next=fj;t=ej;while(j=0)for(j-
12、;j0&!fj;j-);/找下一个非空子表if(fj&j=0)rt.next=fj;t=ej;/链接两个非空子表rt.next=0;void RadixSort(SLList *l)/对*l 中的成绩做链式基数排序int f101,e101;int i;for(i=0;irecnum);i+) l-ri.next=i+1;l-rl-recnum.next=0;for(i=3;i0;-i)Distribute(l-r,i,f,e);Collect(l-r,i,f,e);73.3 测试用例设计第一个考生分数为 93 97 87 88第二个考生分数为 97 93 88 87第三个考生分数为 86 8
13、3 80 81这样测试就会存在第一个考生和第二个考生总分相同的情况，数学分数高的排在前面。如果名次为顺序为第二个、第一个、第三个则输出为正确结果。4 调试报告起初第一个程序输出结果10 97 93 88 8711 93 97 87 8812 86 83 80 81这样看来排序没有排错，只是名次记录错了。可见错误在 rank 的值上，每次记录一次 rank，r 的值会自加一次。后发现在对每个关键字排完序后都记录了rank。故 r 的值会过大。只需要在对最后一次排序（总分的排序）后记录 rank的值就行了。删掉前面几个 for 循环中的 p-rank=r+;产生现在的程序就行了。第二个程序刚开始运
14、行的时候输出了 2 个考生的信息后程序遇到问题需要关闭，调试问题指向coutri.keys0ri.keys1ri.keys2ri.keys3ri.keys4ri.keys 的值为 0x3345d4d8我推断 i 的值有问题，果然 i 的值是-858993460while(j=0)for(j-;j0&!fj;j-);if(fj)rt.next=fj;t=ej;在 j=0 时进入 while 循环，for(j-;j0&!fj;j-); 后 j=-1。执行 if(fj)rt.next=fj;t=ej;，而 e数组下标不能为-1，故产生此错误。8将其改成while(j=0)for(j-;j0&!fj;
15、j-);if(fj&j=0)rt.next=fj;t=ej;后运行成功5 结束语本次课程设计我做的是多关键字 LSD 排序，在上数据结构课时，我只是对 LSD排序有了一个初步的认识，对“分配”和“收集”的方法也没有深究。在做这次实验时，我又重新翻开书本进行了一次深入的研究，LSD( 最低位优先）法是从最次位关键字起进行排序，然后再对高一位的关键字进行排序，依次重复，直至对最高位关键字进行排序后便成为一个有序序列。 “分配”和“收集”方法是在一趟排序中，将结点分配到相应的链队列中去，然后再链接起来。编程过程中我还用到了静态链表这个以前没有用过的数据结构，在静态链表中用整型的游标代替指针指示结点在数组中的相对位置。在做第一个程序时，我用选择排序，起初我是每进行一次选择找到最高分后把该结点的数据和已排好的结点的
