数据结构课程设计报告-多关键字排序的实现.doc

学 号： 0120810340631 课 程 设 计课程名称数据结构设计题目多关键字排序的实现班 级0806班姓 名张军指导教师姚寒冰2010年7月2日课程设计任务书学生姓名： 张 军 专业班级： 0806 班 指导教师： 姚寒冰 工作单位： 计算机科学系 题 目: 多关键字排序的实现 初始条件： 利用多关键字排序进行高考分数处理，除了需对总分进行排序外，不同的专业对单科分数的要求不同，因此在总分相同的情况下，按用户提出的单科分数的次序要求排出考生录取的次序（详见题集p169）。假设待排序的记录数不超过1000，表中记录的关键字数不超过5，各个关键字的范围均为0至100。按用户给定的进行排序的关键字的优先关系，输出排序结果。测试用例自己设计。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容： 1、 问题描述简述题目要解决的问题是什么。2、 设计存储结构设计、主要算法设计（用类C语言或用框图描述）、测试用例设计；3、 调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4、 经验和体会（包括对算法改进的设想）5、 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出，6、 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。时间安排：1、第18周（6月28日至7月2日）完成。2、7月2日8：00到计算中心检查程序、交课程设计报告、源程序（CD盘）。指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日1 设计题目:多关键字排序的程序设计2 问题描述:利用多关键字排序进行高考分数处理，除了需对总分进行排序外，不同的专业对单科分数的要求不同，因此在总分相同的情况下，按用户提出的单科分数的次序要求排出考生录取的次序3 设计我设计的程序是有数学、英语、语文、理综4科各为0到100分。按照总分、数学、英语、语文、理综的优先顺序进行排序。由于本实验约定按LSD进行多关键字的排序。在对个关键字进行排序时采用两种策略：其一是利用稳定的内部排序法，其二是利用“分配”和“收集”的方法。所以我设计了两个程序。首先他们都是以最低位优先来排序的，由于有总分参与排序，可以不考虑理综的分数，故先按照语文分数从高到低排，再按照英语分数排，然后是数学、总分。第一个程序我用的是选择排序法，以单链表储存，因为要求是稳定的内部排续法，所以在每趟找到最大值之后将该结点插入到已排好的结点之后，以满足它是稳定的。第二个程序我参考了教材上288页的“分配”、“收集”的算法，用静态链表存储分数。在一趟排序中，将结点分配到相应的链队列中去，再按从高到低链接起来。两个程序以相同的操作界面演示。按数学、英语、语文、理综的顺序输入成绩，输入1或0确定是否还有考生。当输入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数据关系：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指向储存有各考生成绩链表的头节点。操作结果：按名次顺序输出考生的名次和分数。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 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中的成绩做链式基数排序。void ShowRank(SLList *l)操作结果：按名次顺序输出考生的名次和分数。ADT SLList3.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)/对英语成绩排序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;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.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 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);3.3 测试用例设计第一个考生分数为 93 97 87 88第二个考生分数为 97 93 88 87第三个考生分数为 86 83 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+;产生现在的程序就行了。第二个程序刚开始运行的时候输出了2个考生的信息后程序遇到问题需要关闭，调试问题指向coutrank ri.keys0 ri.keys1 ri.keys2 ri.keys3 ri.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，故产生此错误。将其改成while(j=0)for(j-;j0&!fj;j-);if(fj&j=0)rt.next=fj;t=ej;后运行成功5结束语本次课程设计我做的是多关键字LSD排序，在上数据结构课时，我只是对LSD排序有了一个初步的认识，对“分配”和“收集”的方法也没有深究。在做这次实验时，我又重新翻开书本进行了一次深入的研究，LSD(最低位优先）法是从最次位关键字起进行排序，然后再对高一位的关键字进行排序，依次重复，直至对最高位关键字进行排序后便成为一个有序序列。“分配”和“收集”方法是在一趟排序中，将结点分配到相应的链队列中去，然后再链接起来。编程过程中我还用到了静态链表这个以前没有用过的数据结构，在静态链表中用整型的游标代替指针指示结点在数组中的相对位置。在做第一个程序时，我用选择排序，起初我是每进行一次选择找到最高分后把该结点的数据和已排好的结点的下一个结点数据交换。后来又想到这不是稳定的排序，才改为每趟选择找到最高分后将该结点插入到已排好的结点之后，满足稳定的要求。在实验中，我还总结了一下选择排序与“分配”和“收集”法的优缺点，在记录较少的情况下，前者是一个不错的选择，但是当记录非常多的时候，后者便体现出优势。从它们所需的辅助储存空间来看，前者很有优势，而后者需要2*RADIX个计数单元。总之，通过这次课程设计，不仅编程能力，找错能力和耐心得到的提高，我对数据结构这门课的理解也更深入了一个层次。在本实验中主要侧重的是排序的方法，考生信息很简单，主要只有分数。要使程序更完美，还可以向结构体中增加其它性息，如姓名、考号、性别等，使信息更完整。附录F1 源代码稳定的内部排序法:#includeusing namespace std;struct studentint rank;/名次float math,english,chinese,science,total;student *next;student *Creat()/输入接收考生的各科成绩student *p,*q,*h;int k;p=new student;p-next=NULL;cout输入考生数学、英语、语文、理综分数p-math;cinp-english;cinp-chinese;cinp-science;h=new student;h-next=p;cout继续输入考生成绩则输入1，否则输入0k;while(k=1)/判断是否继续输入q=p;p=new student;q-next=p;p-next=NULL;cout输入考生数学、英语、语文、理综分数p-math;cinp-english;cinp-chinese;cinp-science;cout继续输入考生成绩则输入1，否则输入0k;for(p=h-next;p;p=p-next)p-total=(p-math+p-english+p-chinese+p-science);/算总分return h;void Insert(student *p,student *q,student *h)/将q指向的节点插到p指向的节点之前student *p1,*q1;for(p1=h;p1-next!=p;)p1=p1-next;for(q1=h;q1-next!=q;)q1=q1-next;q1-next=q-next;q-next=p1-next;p1-next=q;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)/对英语成绩排序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;for(;l;l=l-next)if(s-totaltotal) s=l;Insert(p,s,h);s-rank=r+;/记录名次void ShowRank(student *h)/按名次顺序输出考生的名次和分数student *p;cout考生名次和分数分别为：next;p;p=p-next)coutrank total math english chinese scienceendl;int main()student *h;h=Creat();Rank(h);ShowRank(h); cout输入任意字符串结束*c;/为了让程序在这里停一下return 0;“分配”和“收集”的排序：#includeusing namespace std;#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;SLList Creat()/接收考生的各科成绩SLList *l;int i=1,k=1;l=new SLList;l-keynum=5;l-recnum=0;while(k=1)/判断是否继续输入cout输入考生数学、英语、语文、理综分数l-ri.keys1;cinl-ri.keys2;cinl-ri.keys3;cinl-ri.keys4;l-ri.keys0=(l-ri.keys1+l-ri.keys2+l-ri.keys3+l-ri.keys4);(l-recnum)+;cout继续输入考生成绩则输入1，否则输入0k;i+;return *l;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.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 f101,e101;int i;for(i=0;irecnum);i+) l-ri.next=i+1;l-rl-recnum.next=0;for(i=3;i0;-i)Dist