c基数排序-课程设计报告.doc

计算机学院 基数排序课程设计报告学号2016-2017学年 第2学期1608220203基数排序课程设计报告题目：基数排序专业：网络工程班级：16（3）姓名：代应豪指导教师：代美丽成绩：计算机学院2017年4月25日目录1 设计内容及要求3 1.1题目 1.2内容及要求2 概要设计3 2.1 存储结构设计说明 2.2 主要算法流程图3 设计过程及程序代码6 3.1 算法设计 3.2 程序代码4 设计结果与分析135 课设总结156 参考文献161.设计内容及要求 1.1、题目：基数排序算法 1.2、说明：基数排序：通过LSD（最低为优先）法：按最低关键字位k1 对待排序数据中的n个值进行排序按k1值把待排序文件中的n个记录分配到具有不同k1值的若干个堆，然后按k1值从小到大的次序收集在一起，下次再按高一位关键子位k2的值进行分配和收集，如此不断地按更高一位关键字位进行分配和收集，直到用kn分配和收集之后，整个数据按多关键字位有序。2.概要设计 2.1存储结构设计说明 typedefstruct/定义数据在存储类型 intkey; data1;/类型标识符 typedefstruct /定义数据在存储类型 intkeyd;/用数组存放数据个位数、十位数、百位数 intnext;/指针域指向下一个数据形成链表结构 data2;/类型标识符data1Rmax; data2R1max;/新类型数据主要算法流程i=0jrd-1fj=-1p!=-1j=0;i-) /外层循环控制数的关键值(个位，十位，百位)for(int j=0;jrd;j+) /*内层循环一 初始化队列为空*/fj=-1;ej=-1;while(p!=-1) /*内层循环二 数据按关键值分配至相应队列*/k=Rp.keyi; /关键值赋予kif(fk=-1) /队列为空队列头指向当前数据fk=p;elseRek.next=p; /队列不为空链接当前数据到队列尾ek=p; /修改队列尾指向当前值p=Rp.next; /数据指示变量后移为分配下一数据做准备int j=0; /刷新队列指示器，为数据收集做准备while(fj=-1) /*内层循环三 数据收集*/ j+; /扫描到非空队列作为收集数据的p=fj; /当前指示器指向队列首t=ej; /临时存放保护队列尾便于下一队列链接上while(jrd-1) /*内层循环四 收据数据链接成链表*/j+; /扫描下一队列if(fj!=-1) /队列非空则链接至数据收集链表Rt.next=fj; /数据收集链表尾指针指向索扫描到队列的队列首t=ej; /更改链表尾指针Rt.next=-1; /收集数据完成，链表尾置空return p;void choices(data1 R,int i) /选择开关(主界面)data2 R1max; /新类型数据int gw,sw,bw; /定义关键值，个位数，十位数，百位数int p; /定义p存放最终返回值，链表头for(int m=0;mi;m+)gw=Rm.key%10; /个位数关键值由除10取整得sw=(Rm.key%100)/10;/十位数由除百求余再除10取整得bw=Rm.key/100; /百位数关键值由除100取余得R1m.key2=gw; /以下分别将关键值赋予相应位置R1m.key1=sw;R1m.key0=bw;R1m.next=m+1; /各数据指针域初始化int m;R1m.next=-1; /数据链表尾置空p=jishusort(R1); /调用基数排序函数while(p!=-1) /循环控制逐一打印排序后数列printf(%d%d%d ,R1p.key0,R1p.key1,R1p.key2);p=R1p.next;printf(n);int main() /*主函数*/int i=0; /局部变量用作结束输入data1 Rmax;printf(请输入数据以-1结束:);scanf(%d,&Ri.key);while(Ri.key!=-1) /待排序数据输入i+; printf(请输入数据以-1结束:); scanf(%d,&Ri.key);choices(R,i); /调用主界面函数进行开关(操作)选择return 0;设计结果与分析 按照提示输入任意一组整数，以-1结束，如图所示，程序成功运行，实现将一组数字进行基数排序。由于能力和时间的关系，程序部分没有包含处理不同类型的数据，只进行处理整形的数字排序，今后如果时间条件允许的话一定再进行详细的研究。课程设计总结： 通过这次课程设计，使我对C语言程程序设计这门课程有了更深一步的了解。它是计算机程序设计的重要理论技术基础，在我们计算机专业的学习中占据着十分重要的地位。同时也使我们知道，要学好这门课程，仅学习书本上的知识是不够的，还要有较强的实践能力。因为我们学习知识就是为了实践。而只有多实践，多编写程序，才能更好的理解与掌握书本上的东西。我们要知道，真本领只有在实战中才能提高，光说不练是假把戏，我们要通过自己不断追求完善，不断学习新的能力，在一次次编程中成长，才能在真正的意思上成为一个会写程序的人。课程设计是检验能力的重要环节，这能我们知识掌握更加牢固，能让我们知道不仅仅要写好写出代码，更要懂得去分析代码，去让别人看懂自己的代码，要将自己的代码达到最优化。在最开始接到课设题目时，由于没有具体的内容和要求，我就把它当做心里想的那样简单的编辑，结果只表现了一个不完全符合要求的简单排序，不能用特例来表示，在经过同学的帮助探讨下又重新完成了一份，因为时间和能