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

《c基数排序-课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、学号16082202032016-2017学年第2学期《基数排序》课程设计报告题目:基数排序专业：网络工程班级：16(3)姓名：代应豪指导教师：代美丽成绩:计算机学院2017年4月25日目录1设计内容及要求31.1题目1.2内容及要求2概要设计32.1存储结构设计说明2.2主要算法流程图设计过程及程序代码3.1算法设计3.2程序代码4设计结果与分析1315165课设总结6参考文献1•设计内容及要求1.1、题目:基数排序算法1.2、说明：基数排序：通过LSD（最低为优先）法：按最低关键字位kl对待排序数据中的n个值进行排序按kl值把待排序文件中的n个记录分配到具有不同kl值的

2、若干个堆，然后按kl值从小到大的次序收集在一起，下次再按高一位关键子位k2的值进行分配和收集，如此不断地按更高一位关键字位进行分配和收集，直到用kn分配和收集之后，整个数据按多关键字位有序。2.概要设计2.1存储结构设计说明typedefstruct//定义数据在存储类型{intkey;}datal;//类型标识符typedefstruct//定义数据在存储类型{intkey[d];//用数组存放数据个位数、十位数、百位数……intnext;//指针域指向下一个数据形成链表结构}data2;〃类型标识符datalR[max];data2R1[max];//新类型数据主要算法流

3、程data2R[];intf[rd],e[rd];intp=O;intk,t；inti=d;i>=()intj=O;j

4、921H485IMlH215H530]79O

5、H3O6re[l]re[2[re[4]吭5「re[6]图3-1第一趟演示re[3]r

6、e[1第1趟分配(按最低位t=3)re[Q]的“分配”与“收集”过程基数排序第二趟fr[O]fr[i]fr[3]frli."⑸fr[6]fr[l]"⑻frW第2趟收集基数排序的“分配”与“收集”过程第三趟:帀厂—

7、306H614円215T呢FT530一

8、637H738H485H790第3趟分配（按次低位z.=l）re[0]re[1]re⑵⑶re⑷re⑸re[6]re[7]re⑻re⑼637790101215306485530614738921「JJ・riIIJrJJlJrfr[0Jfr[]"⑵"⑶fr[4]fr[5]"⑹fr[1]"⑻fr[S]第3趙收集

9、101TIT和一门

10、06I—I485I—用0[—I614

11、—

12、637}~f丽一冷90]—

13、921

14、图3-3收集分配图示（2）基数排序过程阐述：设有n个记录，d个关键字，rd为基数，通过LSD（最低为优先）法：初始化一系列的空队列，先按最低关键字位k1对待排序数据中的n个值进行排序，按k1值把待排序文件中的n个记录分配到具有不同k1值的相应队列。然后按k1值从小到大的次序收集在一起,下次再按高一位关键子位k2的值进行分配和收集，如此不断地按更高一位关键字位进行分配和收集，每一趟按一个关键值的位置记录分配到rd个队列中，同一链队列中的记录都是用链域指针链接起来的，所有的队头和队尾指针分别放在两个数组

15、中，每一趟分配后通过修改指针将这个链队列中的记录收集起来；直到用kn分配和收集之后，重复分配和收集d趟，便得到了最终排序好的有序序列。整个数据按多关键字位有序。3.2程序代码#incIude"stdio.h"#definemax100#definerd10#defined3intjishusort(data2REDtypedefstruet//定义数据在存储类型intkey;}datal;//类型标识符typedefstruct[//定义数据在存储类型tintkey[d];〃用数组存放数据个位数、十位数、百位intnext://指针域指向下一个数据形成链表结构}data2;/

16、/类型标识符/**********************************基数排序函数intf[rd],e[rd];//定义队列指示变量，分别指向队列头和队列尾intp二0,k,t;//定义指示变量P，和存放数据各位关键值(个位，十位，百位……)的厶临时队尾存放用于收集数据的for(inti二d;i>二0;i--)//外层循环控制数的关键值(个位，十位，百位){for(intj=0;j