数据结构课程设计多关键字排序.docx

《数据结构课程设计多关键字排序.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计多关键字排序.docx（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -工 学 院 运算机工程学院课程设计报告设计名称：数据结构课程设计选题名称：多关键字排序姓名：学号： 专业班级：网络工程081系 （ 院）：运算机工程学院设计时间：设计的点：软件工程试验室、教室指导老师评语：成果：签名：年月日可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 1 页，共 23 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - -

2、- -1课程设计目的1、训练同学敏捷应用所学数据结构学问，独立完成问题分析，结合数据结构理论学问，编写程序求解指定问题。2. 初步把握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。3. 提高综合运用所学的理论学问和方法独立分析和解决问题的才能。4. 训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化同学的理论学问，提高编程水平，并在此过程中培育他们严谨的科学态度和良好的工作作风。2课程设计任务与要求：任务题目： 多关键字的排序【问题描述】多关键字的排序有其肯定的有用范畴。例如：在进行高考分数处理时，除了需对总分进行排序外，不同的专业对单科分数的要求不同，因此尚需在总

3、分相同的情形下，按用户提出的单科分数的次序要求排出考生录用的次序。【基本要求】（1）假设待排序的记录不超过10000，表中记录的关键字数不超过5，各个学科关键字的范畴均为 0 至 100，总分关键字的范畴是0-300 。按用户给定的进行排序的关键字的优先关系，输出排序结果。（2）商定按LSD 法进行多关键字的排序。在对各个关键字进行排序时采纳两种策略：其一是利用稳固的内部排序法，其二是利用“安排”和“收集”的方法。并综合比较这两种策略。【测试数据】由随机数产生器生成。【实现提示】由于是按LSD 方法进行排序， 就对每个关键字均可进行整个序列的排序，但在利用通常的内部排序方法进行排序时，必需选用

4、稳固的排序方法要求：1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等如干步骤完成题目，最终写出完整的分析报告。前期预备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。2、. 设计的题目要求达到肯定工作量（300 行以上代码） ，并具有肯定的深度和难度。3、程序设计语言举荐使用C/C+，程序书写规范，源程序需加必要的注释;4、每位同学需提交可独立运行的程序。5 、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于10 页（代码不算

5、） 。6、课程设计实践作为培育同学动手才能的一种手段，单独考核。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 2 页，共 23 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -3课程设计说明书一 需求分析1）选题功能分析【题目的意义】1、对高考分数依据总分和不同学科的分数依据优先级次序排出考生录用的次序，以满意不同专业对单科分数的要求。2、对不同排序策略进行综合比较。【实现的功能】1、 用 C 语言设计实现一个高考成

6、果排序系统。2、 创建模拟的高考考生成果表，存放到txt 文档中。考生考号为1，2， 3用伪随机数生成器生成各考号同学的各个学科成果，并运算总分成果。3、 由于实际中高考考生成果表是已知的（模拟创建的txt 文档），程序能从文件中读取数据。从创建的考生成果表中读取数据，并对数据处理4、 依据学科的优先级次序，对同学的成果排序。既可以以某一学科的单科成果优先级最高排序，也可以先按总分优先级最高来排序。5、 在对各个关键字即单科成果进行排序的时候，分别用稳固的内部排序法（冒泡法） 以及“安排和搜集 ”的方法进行排序。6、 能够对冒泡法排序策略和“安排和搜集 ”方法排序策略进行的执行时间进行比较。7

7、、 输入数据： 1 各科英文首字母的代号，字符型，如smce2 整型数， 0-100001 输出程序用两种方法进行排序的进程和执行时间2 输出前 n 名同学的信息二 概要设计1、 伪随机生成的数据包含语文、数学、英语三科成果。总成果为语文、数学、英语三科成果的和。学号按成果数组的下标赋值，生成同学成果记录，将该记录储存到txt 文档中2、 从上面的txt 文档中读取数据到一个二维数组中，以便对同学信息进行处理3、 给出排序的优先关系，依据优先关系由低位向高位逐个关键字进行排序。4、对单科成果进行排序的时候，单科成果虽然是0-100 ，但总成果是0-300 ，所以要建301 个队列进行排序，先按

8、“安排”和“搜集”的方法进行一趟“基数排序”。然后再依据稳固的内部排序法（冒泡法）进行排序。将搜集好的或排序好的序列储备，以进行对次优先级的关键字进行再排序。5、将排序好的同学成果依据用户提出的提取人数的要求，储存到另一个txt 文档中，并输出到屏幕6、系统用到的抽象数据类型定义double BubTime1,/按第一个关键字代表的学科成果用冒泡法排序执行的时间 BubTime2,BubTime3, BubTime4,BubTimeSum,/冒泡法排序的总时间DCTime1,/ 按第一个关键字代表的学科成果用安排和收集的方法执行的时间DCTime2, DCTime3, DCTime4,可编辑资

9、料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 3 页，共 23 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -DCTimeSum;/安排和收集法排序的总时间 int score100005,/随机创建的模拟同学记录源数组bubble100005,/进行冒泡法排序时用来存放同学记录源数组，并且随排序进行数组中的记录发生交换copy100005;/从模拟的同学记录源txt 文件中读取同学记录到该数组 struct LSD d3

10、01;/安排数组， 该处考虑到把总分 （0-300）也列入优先级序列中，因此建立了301 个队列int *c10000;/用来存放收集到的同学记录char x5;/存放有优先关系的学科代号序列7、系统中的各个函数模块1：void CreatScoreint score100005;/随机创建同学记录表score。正常高考中该表是已知的，不必创建2： void Collectstruct LSD d301,int *c10000;/LSD法排序中的收集函数，即将安排好的记录收集到c 指针数组储存3： void InitDividestruct LSD d301;/用于初始化暂时安排数组，在每一次

11、收集后必需做的工作4： double DCSortstruct LSD d301,int *c10000,int n;/安排（ Divide ）和收集（ Collect ）可编辑资料 - - - 欢迎下载精品名师归纳总结排序的方法出到屏幕上5： double BubbleSortint score100005,int n;/冒泡法排序6： void Print;/将排序结果文件中的记录数据输7： void savesourcesint score100005,int n;/将模拟创建的高考同学信息记录可编辑资料 - - - 欢迎下载精品名师归纳总结存放到文件中8： void saveresul

12、tsint score100005,int n;/ 依据用户的要求 （总成果在前多少名的同学记录） ，将这 n 条同学的记录存放到新的文件中9:void loadint score100005;/ 从同学高考记录源文件中读取记录到该二维数组中8、 各函数之间的调用关系1:主函数可以调用除子函数2 之外的全部函数2：子函数4 可以调用子函数2 和 3【功能模块图】可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 4 页，共 23 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心

13、总结归纳 - - - - - - - - - - - -InitDividedCreateScorescoreMSavesourcesscore.10000AILodecopyN返回执行时间Collectd,cDcSortd,c,0InitDivided可编辑资料 - - - 欢迎下载精品名师归纳总结Print返回执行时BubbleSortbubble,0可编辑资料 - - - 欢迎下载精品名师归纳总结Saveresultsbubble,n三 具体设计1.抽象数据类型：该数据类型是在安排和收集的时候存放安排成果数组1 抽象数据类型 struct LSDstruct LSD/ 队列的结构类型，链

14、表储备结构类型int *cur;/ 当前位置struct LSD *next;/ 队列中下一个位置;2 CreatScoreint scoreRecordNumberKeyNumber 函数/* 创建一个含有RecordNumber 名同学成果记录的score,包含语文、数学、英语、总分和学号,随机生成语文、数学、英语的成果。* 传递的参数是成果数组score，无返回值*/void CreatScoreint scoreRecordNumberKeyNumber/* 伪随机生成语文、数学、英语的成果*/ fori=0;i RecordNumber;i+forj=0;j3;j+scoreij=r

15、and%101;/ 成果的范畴是0-100/* 总分成果初始化*/ fori=0;i RecordNumber;i+可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 5 页，共 23 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -scorei3=scorei0+scorei1+scorei2;/ 总成果为各科成果之和/* 学号的初始化 */fori=0;i=0; i-ifdi.cur.=NULL/当前队列不空，即有同学

16、的成果安排到该队列p=&di;whilep-cur.=NULL/ 当前位置有同学的成果cj=p-cur;/收集到 c 指针数组中j+;p=p-next;/ 指针 p 指向该队列的下一个位置当前位置有学生的成绩可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 6 页，共 23 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -开头初始化指针数组建立 300 个队列Y队列为空N当前位置同学的成果收集到指针数组中指针 p 指向该

17、队列的下一个位置终止4初始化安排数组InitDividestruct LSD dQueueNumber可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 7 页，共 23 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -/* 初始化 d 数组即置空，在每一次收集后必需做的工作* 传递的参数是struct LSD dQueueNumber ，无返回值*/void InitDividestruct LSD dQueueNumb

18、erforint i=0;iQueueNumber;i+di.cur=NULL; di.next=NULL;5 分 配 和 收 集 方 法 排 序doubleDCSortstructLSD dQueueNumber,int*cRecordNumber,int n/* 安排 和 收集 方法排序* 安排数组为d，收集数组为c* 进行排序的关键字所代表的学科成果n 在安排数组中的位置就是n* 传递的参数是安排数组struct LSD dQueueNumber，用来收集的指针数组int *cRecordNumber，关键字代表的学科在数组中的下标*/double DCSortstruct LSD dQ

19、ueueNumber,int *cRecordNumber,int n/* 按关键字代表的学科成果将成果安排到d 中*/ forj=0;jcur=NULL;p1-next=NULL;p-next=p1;/初始化刚刚添加了同学记录的队列else/ 当前队列不为空p=&dtemp;/* 循环，始终到队列的结尾*/ whilep-cur.=NULLp=p-next;p-cur=cj;/ 将 cj 代表的同学的成果添加到该队列中p1=struct LSD *mallocLENGTH;/ 新申请一个空间来存放同学成果 p1-cur=NULL;p1-next=NULL;p-next=p1;/安排完毕Col

20、lectd,c;/ 将安排好的成果序列收集到c 中InitDivided;return time;/ 初始化安排数组/ 返回执行时间6冒泡法排序 double BubbleSortint bubbleRecordNumberQueueNumber可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 8 页，共 23 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -/* 冒泡法排序* 传递的参数是同学成果记录int bubbl

21、eRecordNumberKeyNumber，关键字所代表学科成果在数组中的下标*/double BubbleSortint bubbleRecordNumberKeyNumber,int nforint i=0;iRecordNumber;i+forint j=0;jRecordNumber-1-i;j+ifbubblejnbubblej+1n/* 交换同学的各科成果*/forint m=0;mKeyNumber;m+temp=bubblejm; bubblejm=bubblej+1m; bubblej+1m=temp;return time;/返回排序执行的时间 返回执行的时间7 Prin

22、t函数/* 从排序结果存放的文件recordresults.txt 中读取记录输出到屏幕上*/void PrintFILE *fp;iffp=fopenD:recordresults.txt,rb=NULLprintf 文件打开失败 .n;elseprintf 文件打开胜利 .n;char t;whilefscanffp,%c,&t&.feoffpift.=EOFprintf%c,t;/ 假如读到终止符，循环终止，输出终止fclosefp;/ 关闭文件8 savesourcesint scoreRecordNumberKeyNumber,int n/* 储存同学记录的函数* 参数为要储存的同学

23、记录和记录条数* 无返回值*/void savesourcesint scoreRecordNumberKeyNumber,int nFILE *fp;/指向文件的指针可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 9 页，共 23 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -iffp=fopenD:recordsources.txt,wb=NULL/ 只写printf 文件打开失败 .n;exit1;fprint

24、ffp,%d,n;/将记录条数写入文件fprintffp,rn;/将换行符号写入文件fori=0;in;i+fprintffp,%-10d%-10d%-10d%-10d%-10d, scorei4,scorei0,scorei1,scorei2,scorei3;/格式写入记录fprintffp,rn;/ 将换行符号写入文件fclosefp;9 saveresultsint scoRreec ordNumberKeyNumber,int n/* 储存同学记录的函数* 参数为要储存的同学记录和记录条数* 无返回值*/void saveresultsint scoreRecordNumberKeyN

25、umber,int nFILE *fp;/ 指向文件的指针iffp=fopenD:recordresults.txt,wb=NULL/只写 ,打开或建立一个二进制文件，只答应写数据printf 文件打开失败 .n; exit1;fprintffp,%d,n;/ 将记录条数写入文件fprintffp,rn;/ 将换行符号写入文件fori=0;in;i+fprintffp,%-10d%-10d%-10d%-10d%-10d,scorei4,scorei0,scorei1,scorei2,scorei3;/格式写入记录fprintffp,rn;/ 将换行符号写入文件fclosefp;10 loadi

26、nt scorReecordNumberKeyNumber/* 读入函数，把文件中的记录度入到二维数组中* 参数为结构体数组*/void loadint scoreRecordNumberKeyNumberFILE *fp;iffp=fopenD:recordsources.txt,rt=NULL/ 打开文件可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 10 页，共 23 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - -

27、 -printf 文件打开失败 .n; exit1;fscanffp,%d,&n;/ 读入记录数fori=0;in;i+fscanffp,%d %d %d %d %d, &scorei4,&scorei0,&scorei1,&scorei2,&scorei3;/按格式读入记录fclosefp;11算法分析1） L SD 算法：这是一种“低位优先”的排序方法，借助一趟基数排序的方法，先按最低位的值对记录进行初步排序，在此基础上再按次低位的值进行进一步排序。以此类推，有低位到高位，每一趟都是在前一趟的基础上，依据关键字的某一位对全部的记录进行排序，直至最高位，这样就完成了基数排序的全过程。从算法中

28、可以看出，对于n 个记录 每个记录含d 个子关键字，每个子关键字的取值范畴为 RADIX个值 进行链式排序的时间复杂度为Odn+RADIX, 其中每一趟安排算法的时间复杂度为On ，每一趟收集的算法的时间复杂度为ORADIX，整个排序进行 d 趟安排和收集，所需帮助空间为2*RADIX 个队列指针。由于需要链表作为储备结构，就相对于 其他以次序结构储备记录的排序方法而言，仍增加了n 个指针域的空间。2） 冒泡法排序：该排序是比较简洁的交换类排序方法，通过相邻数据元素的交换，逐步将带排序列变成有序序列的过程。最坏情形下，待排序的记录按关键字的逆序进行排列，此时，每一趟冒泡排序需要进行 i次比较，

29、3i 次移动。经过 n-1 趟冒泡排序后，总的比较次数为N=i=nn-1/2,n=1， 2，n-1. 总的移动次数为3nn-1/2次，因此该算法的时间复杂度为On*n ，空间复杂度为 O1 。另外，冒泡排序法是一种稳固的每部排序法。四 测试成果可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 11 页，共 23 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师

30、精选 - - - - - - - - - -第 12 页，共 23 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -五 附录（源程序清单）#include#include#include#includestruct LSD/抽象类型定义，队列的结构类型，由于是按LSD 法进行的排序，所以命名为 LSDint *cur;/ 当前位置 struct LSD *next;#define LENGTH sizeofstruct LSDvoid CreatScoreint score100

31、005;/ 随机创建同学记录表score。正常高考中该表是已知的，不必创建void savesourcesint score100005,int n;/将模拟创建的高考同学信息记录存放到文件中 void loadint score100005;/ 从同学高考记录源文件中读取记录到该二维数组中void Collectstruct LSD d301,int *c10000;/LSD法排序中的收集函数，即将安排好的记录收集到 c 指针数组储存void InitDividestruct LSD d301;/用于初始化暂时安排数组，在每一次收集后必需做的工作double DCSortstruct LSD

32、 d301,int *c10000,int n;/安排（ Divide ）和收集（ Collect ）排序的方法 double BubbleSortint score100005,int n;/ 冒泡法排序void saveresultsint score100005,int n;/依据用户的要求（总成果在前多少名的同学记录）， 将这 n 条同学的记录存放到新的文件中void Print;/ 将排序结果文件中的记录数据输出到屏幕上int main可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 13 页，共 23 页 - - - -

33、- - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -double BubTime1,/ 按第一个关键字代表的学科成果用冒泡法排序执行的时间 BubTime2,BubTime3, BubTime4,BubTimeSum,/冒泡法排序的总时间DCTime1,/按第一个关键字代表的学科成果用安排和收集的方法执行的时间 DCTime2,DCTime3, DCTime4,DCTimeSum;/安排和收集法排序的总时间int score100005,/ 随机创建的模拟同学记录源数组bubble100005,/ 进行

34、冒泡法排序时用来存放同学记录源数组，并且随排序进行数组中的记录可编辑资料 - - - 欢迎下载精品名师归纳总结发生交换copy100005;/从模拟的同学记录源txt 文件中读取同学记录到该数组可编辑资料 - - - 欢迎下载精品名师归纳总结struct LSD d301;/ 安排数组，该处考虑到把总分（0-300）也列入优先级序列中，因此建立了301 个队列int *c10000;/ 用来存放收集到的同学记录char x5;/ 存放有优先关系的学科代号序列/* 初始化 c，使其与score 函数 同步 */ forint i=0;i10000;i+ci=scorei;InitDivided;

35、/初始化队列/* 在实际中全部同学的高考记录是存放在一个文件中的，程序运行时是从该文件中读取的源记录数据。*本程序要求随机模拟创建该文件，所以下面要创建每个同学的记录（CreatScore）并储存到一个文件中（ save）*调用这两个函数后就生成了全部同学的记录*/CreatScorescore;/伪随机生成各科成果，并将考号和总成果一并生成在score 数组中savesourcesscore,10000;/将随机生成的记录信息储存在record.txt 中，该文件在程序运行的时候是不变的loadcopy;/ 从源记录文件record.txt 中读取同学记录到数组copy 中/* 为了防止转变源记录，在进行冒泡法排序的时候用bubble 这个数组 */ fori=0;i10000;i+forint j=0;j=0;i-printfnn现在程序正在按%c 代表的学科进行成果安排，请稍后,xi; switchxicase c:/ChineseDCTime1=DCSortd,c,0;/ 按语文这个关键字用安排和收集法排序，并返回时间BubTime1=BubbleSortbubble,0;/按语文这个关键字用冒泡法排序 break;case m:/Math