欢迎来到天天文库
浏览记录
ID:9397349
大小:171.44 KB
页数:10页
时间:2018-04-30
《数据结构课程设计基数排序算法演示》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
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>=0j4、学沈阳理工大学课程设计专用纸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个记录分配到具有不同k15、值的相应队列。然后按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;j8、赋予kif(f[k]==-1)//队列为空队列头指向当前数据f[k]=p;elseR[e[k]].next=p;//队列不为空链接当前数据到队列尾e[k]=p;//修改队列尾指向当前值p=R[p].next;//数据指示变量后移为分配下一数据做准备}intj=0
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;j8、赋予kif(f[k]==-1)//队列为空队列头指向当前数据f[k]=p;elseR[e[k]].next=p;//队列不为空链接当前数据到队列尾e[k]=p;//修改队列尾指向当前值p=R[p].next;//数据指示变量后移为分配下一数据做准备}intj=0
8、赋予kif(f[k]==-1)//队列为空队列头指向当前数据f[k]=p;elseR[e[k]].next=p;//队列不为空链接当前数据到队列尾e[k]=p;//修改队列尾指向当前值p=R[p].next;//数据指示变量后移为分配下一数据做准备}intj=0
此文档下载收益归作者所有