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