数据结构课程设计基数排序算法演示

《数据结构课程设计基数排序算法演示》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、沈阳理工大学课程设计专用纸No-9-目录1需求分析32概要设计32.1存储结构设计说明32.2主要算法流程图43详细设计53.1算法设计53.2程序代码74调试分析95课设总结106参考文献10-9-沈阳理工大学沈阳理工大学课程设计专用纸No-9-1需求设计1、题目：基数排序算法演示2、说明：基数排序：通过LSD（最低为优先）法：先按最低关键字位k1对待排序数据中的n个值进行排序，按k1值把待排序文件中的n个记录分配到具有不同k1值的若干个堆，然后按k1值从小到大的次序收集在一起，下次再按高一位关键子位k2的值进行分配和收集，如

2、此不断地按更高一位关键字位进行分配和收集，直到用kn分配和收集之后，整个数据按多关键字位有序。2概要设计2.1存储结构设计说明typedefstruct//定义数据在存储类型{intkey;}data1;//类型标识符typedefstruct//定义数据在存储类型{intkey[d];//用数组存放数据个位数、十位数、百位数……intnext;//指针域指向下一个数据形成链表结构}data2;//类型标识符data1R[max];data2R1[max];//新类型数据-9-沈阳理工大学沈阳理工大学课程设计专用纸No-9-2.

3、2主要算法流程i>=0j

4、学沈阳理工大学课程设计专用纸No-9-2-2主要算法流程图3详细设计3.1算法设计（1）基数排序的“分配”与“收集”过程：第一趟：图3-1第一趟演示基数排序的“分配”与“收集”过程第二趟：图3-2第二趟演示-9-沈阳理工大学沈阳理工大学课程设计专用纸No-9-基数排序的“分配”与“收集”过程第三趟：图3-3收集分配图示（2）基数排序过程阐述：设有n个记录，d个关键字，rd为基数，通过LSD（最低为优先）法：初始化一系列的空队列，先按最低关键字位k1对待排序数据中的n个值进行排序，按k1值把待排序文件中的n个记录分配到具有不同k1

5、值的相应队列。然后按k1值从小到大的次序收集在一起，下次再按高一位关键子位k2的值进行分配和收集，如此不断地按更高一位关键字位进行分配和收集，每一趟按一个关键值的位置记录分配到rd个队列中，同一链队列中的记录都是用链域指针链接起来的，所有的队头和队尾指针分别放在两个数组中，每一趟分配后通过修改指针将这个链队列中的记录收集起来；直到用kn分配和收集之后，重复分配和收集d趟，便得到了最终排序好的有序序列。整个数据按多关键字位有序。-9-沈阳理工大学沈阳理工大学课程设计专用纸No-9-3.2程序代码#include"stdio.h"#

6、definemax100#definerd10#defined3typedefstruct//定义数据在存储类型{intkey;}data1;//类型标识符typedefstruct//定义数据在存储类型{intkey[d];//用数组存放数据个位数、十位数、百位数……intnext;//指针域指向下一个数据形成链表结构}data2;//类型标识符intjishusort(data2R[])/**********************************基数排序函数****************************/

7、{intf[rd],e[rd];//定义队列指示变量，分别指向队列头和队列尾intp=0,k,t;//定义指示变量p，和存放数据各位关键值(个位，十位，百位……)的k，临时队尾存放用于收集数据的tfor(inti=d;i>=0;i--)//外层循环控制数的关键值(个位，十位，百位……){for(intj=0;j

8、赋予kif(f[k]==-1)//队列为空队列头指向当前数据f[k]=p;elseR[e[k]].next=p;//队列不为空链接当前数据到队列尾e[k]=p;//修改队列尾指向当前值p=R[p].next;//数据指示变量后移为分配下一数据做准备}intj=0