数据结构课程设计基数排序.docx
《数据结构课程设计基数排序.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计基数排序.docx（9页珍藏版）》请在冰点文库上搜索。
数据结构课程设计基数排序
前言
通过这次数据结构课程设计，我更加了解了数据结构这门课程！
我认为要学好数据结构这门课程，不仅要认真阅读课本知识，更重要的是要通过上机实践才能增强和巩固我的知识。
可见数据结构的课程设计对我们来说是受益匪浅，我们一定要认真对待，希望我们打好扎实的专业基础。
数据结构的课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程.随着科学技术发展的日新日异，算法日益增加，并且不断改进，所以我们要将它学好，作为以后工作的一个工具。
“数据结构”是计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，而且已成为其他理工专业的热门选修课。
排序是计算机程序设计中的一种重要操作，他的功能是对一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。
由于待排序的记录数量不同，似的排序工程中设计的存储器不用，可将排序方法分两大类：
一类是内部排序，一类是外部排序。
其中基数排序的内部排序。
2．概要设计
2.1数据结构设计
本程序是用C语言来实现。
以下为数组的定义的结构体：
#defingMAX_NUM_OF_KEY8
#defineRADIX10
#defineMAX_SPACE10000
Typedfstruct{
KeysTypekeys[MAX_NUM_OF_KEY];
InfoTypeotheritems;
Intnext;
}SLCell;
Typedefstruct{
SLCellr[MAX_SPACE];
Intkeynum;
Intrecnum;
}SLList;
2.2算法设计
TypedefintArrType[RADIX];
VoidDistribute（SLCell&r,inti,ArrType&f,ArrType&e）
for（j=0;jfor（p=r[0].next;p;p=r[p].next）{
j=ord（r[p].keys[i]）;
if（!
f[j]）f[j]=p;
elser[e[j]].next=p;
e[j]=p;
}
}//Distribute
voidCollect（SLCell&r,inti,ArrTypef,ArrTypee）{
for（j=0;!
f[j];j=succ（j））;
r[0].next=f[j];t=e[j];
while（jfor（j=succ（j）;jf[j];j=succ（j））
if（f[j]）{r[t].next=f[j];t=e[j];}
}
r[t].next=0;
}//Collect
voidRadixSort（SLList&L）{
for（i=0;iL.r[L.recnum].next=0;
for（i=0;iDistribute（L.r,I,f,e）;
Collect（L.r,i,f,e）;
}
}//RadixSort
}
（1）算法描述
输入无序序列，进行最低优先法的基数排序。
（2）时间复杂度分析O（n）=O（d（n+rd））
2.3ADT描述
ADTArray{
数据对象：
ji=0,…,bi-1,i=1,…,n,
D={ai|ai∈ElemSet,i=1,2,…,n,n>=0}
数据关系：
R={R1,R2,…Rn}
{Ri|ai-1,ai∈D,i=2,…,n}
基本操作：
StatusInitArray（&S）；
操作结果：
构造一个数组S。
Value（A，&e,index1,…indexn）;
初始条件：
A是n维数组，e是元素变量，随后是n个下标值。
操作结果：
若各个下标不超界，则将e的值赋给所指定的A的元素，并返回OK。
}ADTArray
2.4功能模块分析
1.构建3个数组
intdata[10];
inttemp[10][10];
intorder[10]={0,0,0,0,0,0,0,0,0,0};
2.最低位优先法基数排序
while（n<=10）
{
for（i=0;i<10;i++）
{
lsd=（（data[i]/n）%10）;
temp[lsd][order[lsd]]=data[i];
order[lsd]++;
}
printf（"\naccess:
"）;
for（i=0;i<10;i++）
{
if（order[i]!
=0）
for（j=0;j{
data[k]=temp[i][j];
printf（"%d",data[k]）;
k++;
}
order[i]=0;
}
n*=10;
k=0;
}
3．详细设计
3.1主要算法流程图
3.2界面设计
4．软件测试
程序代码：
#include"stdio.h"
#include"conio.h"
voidmain（）
{
inta;
intdata[10];
inti,n=1,j,k=0,lsd,temp[10][10];
intorder[10]={0,0,0,0,0,0,0,0,0,0};
clrscr（）;
printf（"**********************************************************\n"）;
printf（"**********************************************************\n"）;
printf（"************Welcomtouseandhappytoyou!
************\n"）;
printf（"**********************************************************\n"）;
printf（"**********************************************************\n"）;
printf（"\n"）;
printf（"Pleaseinputtennumbers\n"）;
for（a=0;a<10;a++）{scanf（"%d,",&data[a]）;}
printf（"\nnumber:
"）;
for（i=0;i<10;i++）
printf（"%d",data[i]）;
puts（""）;
while（n<=10）
{
for（i=0;i<10;i++）
{
lsd=（（data[i]/n）%10）;
temp[lsd][order[lsd]]=data[i];
order[lsd]++;
}
printf（"\naccess:
"）;
for（i=0;i<10;i++）
{
if（order[i]!
=0）
for（j=0;j{
data[k]=temp[i][j];
printf（"%d",data[k]）;
k++;
}
order[i]=0;
}
n*=10;
k=0;
}
puts（""）;
for（i=0;i<60;i++）printf（"-"）;
printf（"\nsorting:
"）;
for（i=0;i<10;i++）
printf（"%d",data[i]）;
getchar（）;
getchar（）;
}
}
输入显示：
运算结果：
5．设计体会
通过这次课程设计，使我对《数据结构》这门课程有了更深一步的了解。
它是计算机程序设计的重要理论技术基础，在我们计算机专业的学习中占据着十分重要的地位。
同时也使我们知道，要学好这门课程，仅学习书本上的知识是不够的，还要有较强的实践能力。
因为我们学习知识就是为了实践。
而只有多实践，多编写程序，才能更好的理解与掌握书本上的东西。
致谢：
课程设计是检验能力的重要环节，这能我们知识掌握更加牢固。
为此我特别感谢此次设计对我有帮助的所有老师和同学。
参考文献
《数据结构》（Ｃ语言版）严蔚敏主编清华大学出版社
《数据结构题集》（Ｃ语言版）严蔚敏主编清华大学出版社
《数据结构实训教程》 孙巧萍 主编 科学出版社
课程设计成绩评定表
教师评语
1、课程设计表现：
2、程序、软件质量：
3、设计报告质量：
4、答辩表现：
5、独到的见解、方法与创新性：
6、总结：
成绩记录
平时成绩（10分）
程序检查（20+20分）
设计报告文档（20分）
课程设计答辩（20+10分）
最后（百分）成绩
成绩（等级）评定
升级会员 