数据结构课程设计--基数排序.docVIP

前 言 通过这次数据结构课程设计，我更加了解了数据结构这门课程！我认为要学好数据结构这门课程，不仅要认真阅读课本知识，更重要的是要通过上机实践才能增强和巩固我的知识。可见数据结构的课程设计对我们来说是受益匪浅，我们一定要认真对待，希望我们打好扎实的专业基础。数据结构的课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程.随着科学技术发展的日新日异，算法日益增加，并且不断改进，所以我们要将它学好，作为以后工作的一个工具。“数据结构”是计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，而且已成为其他理工专业的热门选修课。 排序是计算机程序设计中的一种重要操作，他的功能是对一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。由于待排序的记录数量不同，似的排序工程中设计的存储器不用，可将排序方法分两大类：一类是内部排序，一类是外部排序。其中基数排序的内部排序。 2．概要设计 数据结构设计 本程序是用C语言来实现。 以下为数组的定义的结构体： #defing MAX_NUM_OF_KEY 8 #define RADIX 10 #define MAX_SPACE 10000 Typedf struct{ KeysType keys[MAX_NUM_OF_KEY]; InfoType otheritems; Int next; }SLCell; Typedef struct{ SLCell r[MAX_SPACE]; Int keynum; Int recnum; }SLList; 2.2 算法设计 Typedef int ArrType[RADIX]; Void Distribute(SLCell r, int i,ArrType f, ArrType e) for(j=0;jRadix;++j) f[j]=0; for(p=r[0].next;p;p=r[p].next){ j=ord(r[p].keys[i]); if(!f[j]) f[j]=p; else r[e[j]].next=p; e[j]=p; } }//Distribute void Collect(SLCell r, int i, ArrType f, ArrType e){ for(j=0; !f[j]; j=succ(j)); r[0].next = f[j]; t=e[j]; while(jRADIX){ for(j = succ(j); jRADIX-1 !f[j]; j=succ(j)) if(f[j]) {r[t].next = f[j]; t =e[j];} } r[t].next = 0; }//Collect void RadixSort(SLList L){ for(i=0; iL.keynum; ++i) L.r[i].next =i +1; L.r[L.recnum].next = 0; for(i=0;iL.keynum;++i){ Distribute(L.r,I,f,e); Collect(L.r,i,f,e); } }//RadixSort } （1）算法描述 输入无序序列，进行最低优先法的基数排序。 （2）时间复杂度分析 O（n）= O（d(n+rd)） 2.3 ADT描述 ADT Array { 数据对象： ji =0,…,bi -1,i=1,…,n, D={ai | ai∈ElemSet, i=1,2,…,n, n=0} 数据关系：R={R1,R2,…Rn} {Riai-1, ai | ai-1, ai∈D,i=2,…,n} 基本操作： Status Init Array (S)； 操作结果：构造一个数组S。 Value（A，e,index1,…indexn）; 初始条件：A是n维数组，e是元素变量，随后是n个下标值。 操作结果：若各个下标不超界，则将e的值赋给所指定的A的元素，并返回OK。 }ADT Array 2.4 功能模块分析 1.构建3个数组 int data[10]; int temp[10][10]; int order[10]={0,0,0,0,0,0,0,0,0,0}; 2.最低位优先法基数排序 while(n=10) { for(i=0