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

淮海工学院计算机工程学院课程设计报告设计名称：数据结构课程设计选题名称：多关键字排姓名：学号：专业班级：系（院）：计算机工程学院设计时间：2013.12.23~2013.1.5设计地点：软件工程实验室、教室指导教师评语：签名：年月日成绩：数据结构课程设计报告第1页，共页1．课程设计目的1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。2．课程设计任务与要求：任务多关键字的排序是根据多个不同的要求来进行的，在某些方面，有其一定的实用范围。例如:在对高考学生的成绩进行分析和处理的时候，各个学校录取学生除了需要考虑总分的情况，不同的专业对单科的分数的要求也有所不同。因此在总分相同的情况下，还需要根据学校定的单科分数的高低来考虑考生录取的优先次序。总体要求：1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。2、.设计的题目要求达到一定工作量（300行以上代码），并具有一定的深度和难度。3、程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释;4、每位同学需提交可独立运行的程序；5、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于10页（代码不算）；6、课程设计实践作为培养学生动手能力的一种手段，单独考核。题目要求：(1)假设待排序的记录数不超过10000，表中记录的关键字数不超过5，各个关键字的范围均为0至100。按用户给定的进行排序的关键字的优先关系，输出排序结果。(2)约定按LSD法进行多关键字的排序。在对各个关键字进行排序时采用两种策略:其一是利用稳定的内部排序法，其二是利用分配和收集的方法。并综合比较这两种策略。数据结构课程设计报告第2页，共页3．课程设计说明书一需求分析在进行高考分数的处理时，除了需对总分进行排序外，不同的专业对单科的分数的要求不同，因此尚需在总分相同的情况下，按用户提出的单科分数的次序要求排出考生录取的次序。针对这一问题，设计一个用C语言描述的高考成绩排名系统。按学科关键字高考总分进行排序的情况下，各科程序排序。本程序规定如下：1.创建高考成绩表包含语文、数学、英语、综合四门成绩，以及考号姓名等考生信息存放到名为高考成绩.txt文本中。2.对考生成绩可以实现查找、显示等功能。3.可以输入成绩进行排序也可以从文件中读取数据进行排序。4.对学生的成绩排序，在总分不同的时候按照各自的排序，在总分相同的情况下。5.对单科成绩进行排序时分别用稳定的冒泡排序和“分配”和“收集”的方法进行排序。二概要设计1.规定成绩个数、成绩记录的最大记录数、和存储每个成绩的数组队列#defineMAX_NUM_OF_KEY5#defineRADIX101#defineMAX_SPACE10002.定义结构体存储考生成绩信息structSLCell{intkeys[MAX_NUM_OF_KEY];charname[20];intnumber;intnext;};3.定义静态链表structSLList{SLCellr[MAX_SPACE];intkeynum;intrecnum;};ADTSLList{数据对象：D：D={a|a属于SLList}数据关系：R：数据元素同属一个集合。基本操作：P：SLList*Creat()操作结果：用SLList存储输入的考生的信息，但是不存入文件中。数据结构课程设计报告第3页，共页voidread(SLList*l)操作结果：从文件中读取考生的各科成绩进行操作。voidsearch(SLList*l)操作结果：可以按考号或姓名查找考生的各科成绩。voidDistribute(RecordTypel*r,inti,int*f,int*e)初始条件：存在以i为下标的关键字。操作结果：以下标为i的关键字为准做一趟分配。voidCollect(RecordTypel*r,inti,int*f,int*e)初始条件：存在以i为下标的关键字。操作结果：以下标为i的关键字为准做一趟收集。voidRadixSortMaths(SLList*l)操作结果：对*l中的成绩做链式基数排序，以数学成绩为关键字排序。voidRadixSortChinese(SLList*l)操作结果：对*l中的成绩做链式基数排序，以语文成绩为关键字排序。voidRadixSortEnglish(SLList*l)操作结果：对*l中的成绩做链式基数排序，以英语成绩为关键字排序。voidRadixSortzonghe(SLList*l)操作结果：对*l中的成绩做链式基数排序，以理综成绩为关键字排序。voidRadixSort(SLList*l)操作结果：按用户选择的关键字排序并输出排序结果voidRadixSortTotal(SLList*l)操作结果：对总分排序voidShowRank(SLList*l)操作结果：按名次顺序输出考生名次考号姓名总分数学英语语文理综分数}ADTSLList系统流程图如下：数据结构课程设计报告第4页，共页三详细设计1.存储文件的书写voidread(SLList*l)2.考生信息输入SLList*Creat()3.查找函数voidsearch(SLList*l)4.链式基数排序voidDistribute(SLCell*r,inti,int*f,int*e)/*以下标为i的关键字为准做一趟分配*/{intj,p;for(j=RADIX-1;j=0;--j)//将RADIX个队列初始化为空队列f[j]=0;for(p=r[0].next;p;p=r[p].next){j=r[p].keys[i];if(!f[j])//将下标p所指的节点插入第j个队列中f[j]=p;elser[e[j]].next=p;e[j]=p;}}多关键字排序系统取得考生信息的方式查询按考号查询按姓名查询各种排序总分相同按语文成绩排序总分相同按英语成绩排序总分相同按数学成绩排序总分相同按综合成绩排序手动输入从文件读取考号姓名各科成绩数据结构课程设计报告第5页，共页voidCollect(SLCell*r,inti,int*f,int*e)/*收集*/{intj,t;for(j=RADIX-1;!f[j];j--);//找第一个非空队列r[0].next=f[j];t=e[j];while(j=0){for(j--;j0&&!f[j];j--);//找下一个非空队列if(f[j]&&j=0){r[t].next=f[j];t=e[j];}//链接两个非空队列}r[t].next=0;//t指向最后一个非空队列中的最后节点}/*对*l中的成绩做链式基数排序,链表的记录按从小到大的顺序连接*/voidRadixSortChinese(SLList*l)//语文{intf[101],e[101];inti;for(i=0;il-recnum;i++)l-r[i].next=i+1;l-r[l-recnum].next=0;for(i=3;i0;--i){Distribute(l-r,i,f,e);Collect(l-r,i,f,e);}}voidRadixSortMaths(SLList*l)//数学{intf[101],e[101];inti;for(i=0;il-recnum;i++)l-r[i].next=i+1;l-r[l-recnum].next=0;for(i=1;i3;++i){Distribute(l-r,i,f,e);Collect(l-r,i,f,e);}}voidRadixSortEnglish(SLList*l)//英语数据结构课程设计报告第6页，共页{intf[101],e[101];inti;for(i=0;il-recnum;i++)l-r[i].next=i+1;l-r[l-recnum].next=0;for(i=1;i4;++i){Distribute(l-r,i,f,e);Collect(l-r,i,f,e);}}voidRadixSortzonghe(SLList*l)//综合{intf[101],e[101];inti;for(i=0;il-recnum;i++)l-r[i].next=i+1;l-r[l-recnum].next=0;for(i=1;i5;++i){Distribute(l-r,i,f,e);Collect(l-r,i,f,e);}}voidRadixSortTotal(SLList*l)//对总分排序{SLCell*r;r=l-r;intf[401],e[401];intj,p,t;for(j=400;j=0;--j)f[j]=0;for(p=r[0].next;p;p=r[p].next){j=r[p].keys[0];if(!f[j])f[j]=p;elser[e[j]].next=p;e[j]=p;}for(j=400;!f[j];j--);r[0].next=f[j];t=e[j];while(j=0)数据结构课程设计报告第7页，共页{for(j--;j0&&!f[j];j--);if(f[j]&&j=0){r[t].next=f[j];t=e[j];}}r[t].next=0;}voidShowRank(SLList*l)//按名次顺序输出考生名次学号姓名总分语文数学英语综合分数{intrank=1,i;cout名次考号名字总分语文数学英语综合endl;for(i=l-r[0].next;rank=l-recnum;rank++){cousetw(2)rank;coutsetw(10)l-r[i].numbersetw(10)l-r[i].name;coutsetw(10)l-r[i].keys[0];coutsetw(10)l-r[i].keys[1]setw(10)l-r[i].keys[2];coutsetw(10)l-r[i].keys[3]setw(10)l-r[i].keys[4]endl;i=l-r[i].next;}}四设计与调试分析刚开始的时候我设计了文件的插入、删除、修改、查询等功能，后来我用了静态链表存储，同时在文件读取的时候我设置了每次读取的最大值为10所以在插入、删除之后就出现了乱码的情况，所以我就放弃了插入、删除的功能，只写了查询的功能。在写查询的时候我本来想用两个子函数和一个查找主函数的，可是后来在主函数中用switch语句调用两个子函数出错。后来我把函数写在switch语句中就对了。在选择功能界面和排序界面时也出错了，一开始我用的是switch语句套在switch语句中，总是出现错误，而且检查不出来。后来我把套在里面的switch语句写在另外一个函数里，然后再调用这样就没有错误了。写文件的时候把值直接赋给指针了，所以导致我一直出错，后来进过看书弄懂了。链式基数排序的程序是按照书上的写的，所以没什么大问题。五用户手册一．主界面：1手动输入考生成绩进行排序2显示文件中已经存储的考生成绩信息3各种查询考生成绩信息4各种排序5输出排序后的考生成绩信息6.退出二．选择1，进入手动输入考生成绩信息界面：依次分别输入考生考号、姓名、语文、数学、英语、综合，输入完成按回