数据结构课程设计多关键字实验报告.doc

淮 海 工 学 院 计算机工程学院课程设计报告设计名称： 数据结构课程设计 选题名称： 多关键字排 姓 名： 学 号： 专业班级： 系 （院）： 计算机工程学院 设计时间： 2013.12.232013.1.5 设计地点： 软件工程实验室、教室 成绩：指导教师评语： 签名： 年 月 日数据结构课程设计报告 第 27 页，共 页1课程设计目的1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。2课程设计任务与要求：任务多关键字的排序是根据多个不同的要求来进行的，在某些方面，有其一定的实用范围。例如:在对高考学生的成绩进行分析和处理的时候，各个学校录取学生除了需要考虑总分的情况，不同的专业对单科的分数的要求也有所不同。因此在总分相同的情况下，还需要根据学校定的单科分数的高低来考虑考生录取的优先次序。总体要求：1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。 2、.设计的题目要求达到一定工作量（300行以上代码），并具有一定的深度和难度。3、程序设计语言推荐使用C/C+，程序书写规范，源程序需加必要的注释;4、每位同学需提交可独立运行的程序；5 、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于10页（代码不算）；6、 课程设计实践作为培养学生动手能力的一种手段，单独考核。题目要求： (1) 假设待排序的记录数不超过10000，表中记录的关键字数不超过5，各个关键字的范围均为0至100。按用户给定的进行排序的关键字的优先关系，输出排序结果。 (2) 约定按LSD法进行多关键字的排序。在对各个关键字进行排序时采用两种策略:其一是利用稳定的内部排序法，其二是利用分配和收集的方法。并综合比较这两种策略。 3课程设计说明书一 需求分析在进行高考分数的处理时，除了需对总分进行排序外，不同的专业对单科的分数的要求不同，因此尚需在总分相同的情况下，按用户提出的单科分数的次序要求排出考生录取的次序。针对这一问题，设计一个用C语言描述的高考成绩排名系统。按学科关键字高考总分进行排序的情况下，各科程序排序。本程序规定如下：1. 创建高考成绩表包含语文、数学、英语、综合四门成绩，以及考号姓名等考生信息存放到名为高考成绩.txt文本中。2. 对考生成绩可以实现查找、显示等功能。3. 可以输入成绩进行排序也可以从文件中读取数据进行排序。4. 对学生的成绩排序，在总分不同的时候按照各自的排序，在总分相同的情况下。5. 对单科成绩进行排序时分别用稳定的冒泡排序和“分配”和“收集”的方法进行排序。二 概要设计1.规定成绩个数、成绩记录的最大记录数、和存储每个成绩的数组队列#define MAX_NUM_OF_KEY 5#define RADIX 101#define MAX_SPACE 10002.定义结构体存储考生成绩信息struct SLCellint keysMAX_NUM_OF_KEY;char name20;int number; int next; ;3.定义静态链表struct SLListSLCell rMAX_SPACE;int keynum;int recnum;ADT SLList数据对象：D：D=a|a属于SLList数据关系：R：数据元素同属一个集合。基本操作：P：SLList * Creat()操作结果：用SLList存储输入的考生的信息，但是不存入文件中。void read(SLList *l) 操作结果：从文件中读取考生的各科成绩进行操作。void search(SLList *l) 操作结果：可以按考号或姓名查找考生的各科成绩。void Distribute(RecordTypel *r,int i,int *f,int *e)初始条件：存在以i为下标的关键字。操作结果：以下标为i的关键字为准做一趟分配。void Collect(RecordTypel *r,int i,int *f,int *e)初始条件：存在以i为下标的关键字。操作结果：以下标为i的关键字为准做一趟收集。void RadixSortMaths(SLList *l)操作结果：对*l中的成绩做链式基数排序，以数学成绩为关键字排序。void RadixSortChinese(SLList *l)操作结果：对*l中的成绩做链式基数排序，以语文成绩为关键字排序。void RadixSortEnglish(SLList *l)操作结果：对*l中的成绩做链式基数排序，以英语成绩为关键字排序。void RadixSortzonghe(SLList *l)操作结果：对*l中的成绩做链式基数排序，以理综成绩为关键字排序。void RadixSort(SLList *l) 操作结果：按用户选择的关键字排序并输出排序结果void RadixSortTotal(SLList *l)操作结果：对总分排序void ShowRank(SLList *l)操作结果：按名次顺序输出考生名次 考号 姓名 总分 数学 英语 语文 理综分数ADT SLList系统流程图如下：多关键字排序系统 查询 取得考生信息的方式 各种排序手动输入从文件读取按姓名查询按考号查询总分相同按语文成绩排序总分相同按英语成绩排序总分相同按数学成绩排序总分相同按综合成绩排序考号姓名各科成绩三 详细设计1.存储文件的书写void read(SLList *l)2.考生信息输入SLList * Creat() 3.查找函数void search(SLList *l)4.链式基数排序void Distribute(SLCell *r,int i,int *f,int *e)/*以下标为i的关键字为准做一趟分配*/int j,p;for(j=RADIX-1;j=0;-j)/将RADIX个队列初始化为空队列fj=0;for(p=r0.next;p;p=rp.next)j=rp.keysi;if(!fj)/将下标p所指的节点插入第j个队列中fj=p;elserej.next=p;ej=p;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;/t指向最后一个非空队列中的最后节点/*对*l中的成绩做链式基数排序,链表的记录按从小到大的顺序连接*/void RadixSortChinese(SLList *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);void RadixSortMaths(SLList *l)/数学int f101,e101;int i;for(i=0;irecnum;i+) l-ri.next=i+1;l-rl-recnum.next=0;for(i=1;ir,i,f,e);Collect(l-r,i,f,e);void RadixSortEnglish(SLList *l)/英语int f101,e101;int i;for(i=0;irecnum;i+) l-ri.next=i+1;l-rl-recnum.next=0;for(i=1;ir,i,f,e);Collect(l-r,i,f,e);void RadixSortzonghe(SLList *l)/综合int f101,e101;int i;for(i=0;irecnum;i+) l-ri.next=i+1;l-rl-recnum.next=0;for(i=1;ir,i,f,e);Collect(l-r,i,f,e);void RadixSortTotal(SLList *l)/对总分排序SLCell *r;r=l-r;int f401,e401;int j,p,t;for(j=400;j=0;-j) fj=0;for(p=r0.next;p;p=rp.next)j=rp.keys0;if(!fj) fj=p;elserej.next=p;ej=p;for(j=400;!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 ShowRank(SLList *l)/按名次顺序输出考生名次 学号 姓名 总分 语文 数学 英语 综合分数int rank=1,i;cout 名次 考号 名字 总分 语文 数学 英语 综合r0.next;rankrecnum;rank+)cousetw(2)rank;coutsetw(10)ri.numbersetw(10);coutsetw(10)ri.keys0;cout setw(10)ri.keys1setw(10)ri.keys2;cout setw(10)ri.keys3setw(10)ri.keys4ri.next;四 设计与调试分析刚开始的时候我设计了文件的插入、删除、修改、查询等功能，后来我用了静态链表存储，同时在文件读取的时候我设置了每次读取的最大值为10所以在插入、删除之后就出现了乱码的情况，所以我就放弃了插入、删除的功能，只写了查询的功能。在写查询的时候我本来想用两个子函数和一个查找主函数的，可是后来在主函数中用switch语句调用两个子函数出错。后来我把函数写在switch语句中就对了。在选择功能界面和排序界面时也出错了，一开始我用的是switch语句套在switch语句中，总是出现错误，而且检查不出来。后来我把套在里面的switch语句写在另外一个函数里，然后再调用这样就没有错误了。写文件的时候把值直接赋给指针了，所以导致我一直出错，后来进过看书弄懂了。链式基数排序的程序是按照书上的写的，所以没什么大问题。五 用户手册1 主界面：1手动输入考生成绩进行排序2显示文件中已经存储的考生成绩信息3各种查询考生成绩信息4各种排序5输出排序后的考生成绩信息6.退出2 选择1，进入手动输入考生成绩信息界面：依次分别输入考生考号、姓名、语文、数学、英语、综合，输入完成按回车键。若想继续输入按1，不再输入按0。2 选择2，进入显示考生信息界面（从文件中读取考生成绩信息）3 选择3，进入查询界面：1按考号查找2按姓名查找4 选择4，进入排序界面：1总分相同时按语文成绩排序2总分相同时按英语成绩排序3总分相同时按数学成绩排序4总分相同时按综合成绩排序。5 选择5，输出排好顺序的考生成绩信息，按总分排序。六 测试成果1. 手动输入考生信息测试结果2. 从文件中读取考生信息进行排序七 附录（源程序清单）#include#include#include#include#include #define MAX_NUM_OF_KEY 5 /关键字最多为5#define RADIX 101#define MAX_SPACE 1000 /待排序的数最大为1000struct SLCellint keysMAX_NUM_OF_KEY;/子关键字数组 char name20;int number; int next;/*定义一个静态链表*/struct SLListSLCell rMAX_SPACE;int keynum;int recnum; ;SLList * Creat() /手动输入考生的高考成绩信息SLList *l;int i=1,flag=1;l=new SLList;l-keynum=5;l-recnum=0;while(flag) /判断是否继续输入cout请输入考生考号、姓名、语文、数学、英语、综合l-ri.number; ; cinl-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，否则输入0flag;i+;return l;void read(SLList *l)/读入文件int num=10;/定义从文件中读取数据的最大值，可更改l-keynum=5;l-recnum=0; cout 考号 姓名 语文 数学 英语 综合endl;ifstream infile (高考成绩.txt,ios:in); /判断文件是否能够打开if ( ! infile )cout 打开文件失败endl; for (int i=1;il-ri.number;coutsetw(2)ri.number; infile ;coutsetw(10);infile l-ri.keys1;coutsetw(10)ri.keys1;infile l-ri.keys2;coutsetw(10)ri.keys2; infile l-ri.keys3;coutsetw(10)ri.keys3;infile l-ri.keys4;coutsetw(10)ri.keys4ri.keys0=(l-ri.keys1+l-ri.keys2+l-ri.keys3+l-ri.keys4); (l-recnum)+; infile.close();/*查找函数*/void search(SLList *l)char name20;int number; int i;int j;cout按考号查找输入0，按姓名查找输入1j;switch (j) case 0:coutnumber;for (i=1;iri.number=number) /判断输入的学号是否正确 cout 考号 名字 语文 数学 英语 综合endl; cout setw(2)ri.numbersetw(10); cout setw(10)ri.keys1setw(10)ri.keys2; cout setw(10)ri.keys3setw(10)ri.keys4endl; break; case 1: coutname;for (i=1;,name)=0) cout 考号 姓名 语文 数学 英语 综合endl; cout setw(2)ri.numbersetw(10); cout setw(10)ri.keys1setw(10)ri.keys2; cout setw(10)ri.keys3setw(10)ri.keys4=0;-j)/将RADIX个队列初始化为空队列fj=0;for(p=r0.next;p;p=rp.next)j=rp.keysi;if(!fj)/将下标p所指的节点插入第j个队列中fj=p;elserej.next=p;ej=p;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;/t指向最后一个非空队列中的最后节点/*对*l中的成绩做链式基数排序,链表的记录按从小到大的顺序连接*/void RadixSortChinese(SLList *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);void RadixSortMaths(SLList *l)/数学int f101,e101;int i;for(i=0;irecnum;i+) l-ri.next=i+1;l-rl-recnum.next=0;for(i=1;ir,i,f,e);Collect(l-r,i,f,e);void RadixSortEnglish(SLList *l)/英语int f101,e101;int i;for(i=0;irecnum;i+) l-ri.next=i+1;l-rl-recnum.next=0;for(i=1;ir,i,f,e);Collect(l-r,i,f,e);void RadixSortzonghe(SLList *l)/综合int f101,e101;int i;for(i=0;irecnum;i+) l-ri.next=i+1;l-rl-recnum.next=0;for(i=1;ir,i,f,e);Collect(l-r,i,f,e);void RadixSortTotal(SLList *l)/对总分排序SLCell *r;r=l-r;int f401,e401;int j,p,t;for(j=400;j=0;-j) fj=0;for(p=r0.next;p;p=rp.next)j=rp.keys0;if(!fj) fj=p;elserej.next=p;ej=p;for(j=400;!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 ShowRank(SLList *l)/按名次顺序输出考生名次 学号 姓名 总分 语文 数学 英语 综合分数int rank=1,i;cout 名次 考号 名字 总分 语文 数学 英语 综合r0.next;rankrecnum;rank+)cout setw(2)rank;cout setw(10)ri.numbersetw(10);cout setw(10)ri.keys0;cout setw(10)ri.keys1setw(10)ri.keys2;cout setw(10)ri.keys3setw(10)ri.keys4ri.next;void RadixSort(SLList *l) int x,k=1;while(k!=0) cout*endl; cout* 你可以选择以下几种操作： *endl; cout* 1.总分相同时按语文成绩排序 *endl; cout* 2.总分相同时按英语成绩排序 *endl; cout* 3.总分相同时按数学成绩排序 *endl; cout* 4.总分相同时按综合成绩排序 *endl; cout* 5.退出 *endl; cout*endl; coutx; switch(x) case 1: RadixSortChinese(l); RadixSortTotal(l); cout考生成绩已按您的选择排序成功endl; ShowRank(l); break; case 2: RadixSortMaths(l); RadixSortTotal(l); cout考生成绩已按您的选择排序成功endl; ShowRank(l); break; case 3: RadixSortEnglish(l); RadixSortTotal(l); cout考生成绩已按您的选择排序成功endl; ShowRank(l); break; case 4: RadixSortzonghe(l); RadixSortTotal(l); cout考生成绩已按您的选择排序成功endl; ShowRank(l); break; case 5: return ; break; system(pause); system(cls); int main()int x,flag=1;SLList * L=new SLList;while(flag!=0) cout*欢迎使用多关键字排序系统*n; cout*-手动输入考生成绩信息进行排序请选-1*n; cout*-显示考生成绩信息请选择-2*n; cout*-各种查询考生成绩信息请选择-3*n; cout*-各种排序请选择-4*n; cout*-输出排序后的考生高考信息请选择-5*n; cout*-退出请选择-6*n; cout*n;coutx;switch(x)case 1: L=Creat(); break; case 2: read(L); break; case 3: search(L); break; case 4:RadixSort(L); break; case 5: ShowRank(L); break; case 6: return 0 ; break; system(pause); system(cls);cout按任意键继续操作endl; system(cls);return 0;4.课程设计心得本次课程设计我做的是多关键字LSD排序，在上数据结构课时，我对链式基数排序的过程和功能实现有了一定的认识，但是对“分配”和“收集”的方法算法程序没怎么弄懂。在做这次实验时，我又重新把书上的算法看了一下，知道LSD(最低位优先）法是从最次位关键字起进行排序，然后再对高一位的关键字进行排序，依次重复，直至对最高位关键字进行排序后便成为一个有序序列。“分配”和“收集”方法是在一趟排序中，将结点