(完整版)数据结构课程设计报告

数据结构课程设计报告

一．前沿：

排序是数据结构中的一块难点，也是重点。熟练的掌握各种各样的排序算法是对每个编程人员的基本的要求。历年的考研还是期末考中，排序都占了比较大的比重。

二．程序实现的功能：

本程序采用了各种不同的方法对同一个输入进行排序，且每一个元素其本身亦是一个结构体，又可以进行扩充，使其可以存储其他的相关的信息。在此我仅仅举了结构体本身只有一个元素的情况。

a)采用的数据类型：

为了讨论的方便，本程序采用了复合型的结构体类型，且才用了静态线性表的形式，不能进行扩充，一旦空间开辟，就不能在扩充（注意）。

具体如下：

typedef struct{ //每个元素的类型定义，为了讨论的方便本程序采用了单关键字；

int key; //但可以根据需要扩充，每个关键字令其为整型的；

}redtype;

typedef struct{ //开辟的数组，以上述类型的元素组成；

redtype *r; //存入要输入的元素的数组；

int length; //数组的长度，shellsort中要用到；

}sqlist;

四．对部分头文件和函数的说明：

：改头文件主要用来实现清屏，使得出的结果更清晰明白。

“shellsort(sqlist l,int d)”：该函数主要实现希尔排序，使无序的数据排列成有序的序列

“quicksort(sqlist l,int low,int high)”：该函数实现的功能同上，只是原理不同

“heapadjust(sqlist l,int s,int m)”：该函数实现调整无序的数据序列使其

成为

大顶堆，即树型结构的最上面是值最大的，这样进过一次的调整便得

到了值

最大的元素，即可进过多次的排序使一个无序的序列又序。

“heapsort(sqlist l)”：该函数实现建立堆的过程。在其中间调用

heapadjust实现

最终建立大顶的任务。

“oesort(sqlist l,int n)”：该函数进行奇偶排序将无序的数据排成有序的。五．核心程序算法：

void shellsort(sqlist& l,int d)

{//采用希尔排序，本程序中的l.r[0].key使暂存单元，非哨兵。

d=l.length/2;

while(d>0)

{

for(i=d+1;i<=l.length;++i)

if(l.r[i].key

{

l.r[0]=l.r[i];

for(j=i-d;j>0&&l.r[0].key

l.r[j+d]=l.r[j];

l.r[j+d]=l.r[0];}

d=d/2;}

基本思想：

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2

void quicksort(sqlist& l,int low,int high)

{//快速排序

if(low

{i=low;j=high;l.r[0]=l.r[i];

do{

while(il.r[0].key)

--j;

if(i

{l.r[i]=l.r[j];++i;}

while(i

++i;

if(i

l.r[j]=l.r[i];--j;

}

}while(i!=j);

l.r[i]=l.r[0];

quicksort(l,low,i-1); 对r[low..i-1]进行快速排序

quicksort(l,i+1,high); 对r[I+1.high]进行快速排序

基本思想

设当前待排序的无序区为r[low..high]，利用分治法可将快速排序的基本思想描述为：①分解：在r[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间r[low..pivotpos-1]和r[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。注意：划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注pivot=r[pivotpos])r[low..pivotpos-1].keys≤r[pivotpos].key≤r[pivotpos+1..hi gh].keys 其中low≤pivotpos≤high。②求解：通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和r[pivotpos+1..high]快速排序。③组合：因为当"求解"步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，"组合"步骤无须做什么，可看作是空操作。

void heapadjust(sqlist &l,int s,int m)

{// /筛选法调整堆，使其成为大顶堆

rc=l.r[s].key;

for(j=2*s;j<=m;j*=2)

{if(j

j++;

if(rc>l.r[j].key)break;

l.r[s].key=l.r[j].key;

s=j;}

l.r[s].key=rc;}