《数据结构课程设计报告排序设计998.pdf》由会员分享，可在线阅读，更多相关《数据结构课程设计报告排序设计998.pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计科 021：潘伟丰 第 1 页 共 9 页 数据结构课程设计报告 一前沿：排序是数据结构中的一块难点，也是重点。熟练的掌握各种各样的排序算法是对每个编程人员的基本的要求。历年的考研还是期末考中，排序都占了比较大的比重。二程序实现的功能：本程序采用了各种不同的方法对同一个输入进行排序，且每一个元素其本身亦是一个结构体，又可以进行扩充，使其可以存储其他的相关的信息。在此我仅仅举了结构体本身只有一个元素的情况。a)采用的数据类型：为了讨论的方便，本程序采用了复合型的结构体类型，且才用了静态线性表的形式，不能进行扩充，一旦空间开辟，就不能在扩充（注意）。具体如下：typedef struct /每个
2、元素的类型定义，为了讨论的方便本程序采用了单关键字；int key;/但可以根据需要扩充，每个关键字令其为整型的；redtype;typedef struct /开辟的数组，以上述类型的元素组成；redtype*r;/存入要输入的元素的数组；int length;/数组的长度，shellsort 中要用到；sqlist;四对部分头文件和函数的说明：改头文件主要用来实现清屏，使得出的结果更清晰明白。“shellsort(sqlist l,int d)”：该函数主要实现希尔排序，使无序的数据排列成有序的序列“quicksort(sqlist l,int low,int high)”：该函数实现的功
3、能同上，只是原理不同“heapadjust(sqlist l,int s,int m)”：该函数实现调整无序的数据序列使其成为 大顶堆，即树型结构的最上面是值最大的，这样进过一次的调整便得到了值 最大的元素，即可进过多次的排序使一个无序的序列又序。“heapsort(sqlist l)”：该函数实现建立堆的过程。在其中间调用 heapadjust 实现 最终建立大顶的任务。“oesort(sqlist l,int n)”：该函数进行奇偶排序将无序的数据排成有序的。五核心程序算法：void shellsort(sqlist&l,int d)/采用希尔排序，本程序中的 l.r0.key 使暂存单元
4、，非哨兵。d=l.length/2;while(d0)for(i=d+1;i=l.length;+i)if(l.ri.key0&l.r0.keyl.rj.key;j-=d)l.rj+d=l.rj;计科 021：潘伟丰 第 2 页 共 9 页 l.rj+d=l.r0;d=d/2;基本思想：先取一个小于 n 的整数 d1 作为第一个增量，把文件的全部记录分成 d1 个组。所有距离为 dl 的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量 d2d1 重复上述的分组和排序，直至所取的增量dt=1(dtdt-ld2d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上
5、是一种分组插入方法 void quicksort(sqlist&l,int low,int high)/快速排序 if(lowhigh);/对 rlow.high进行一次快速排序 i=low;j=high;l.r0=l.ri;do while(il.r0.key)-j;if(ij)l.ri=l.rj;+i;while(ij&l.ri.key=l.r0.key)+i;if(ij)l.rj=l.ri;-j;while(i!=j);l.ri=l.r0;quicksort(l,low,i-1);对 rlow.i-1进行快速排序 quicksort(l,i+1,high);对 rI+1.high进行快速
6、排序 基本思想 设当前待排序的无序区为 rlow.high，利用分治法可将快速排序的基本思想描述为：分解：在 rlow.high中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间 rlow.pivotpos-1和 rpivotpos+1.high，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为 pivot)的关键字 pivot.key，右边的子区间中所有记录的关键字均大于等于 pivot.key，而基准记录 pivot 则位于正确的位置(pivotpos)上，它无须参加后续的排序。注意：划分的关键是要求出基准记录所在的位置 pivotpos。划
7、分的结果可以简单地表示为(注pivot=rpivotpos)rlow.pivotpos-1.keysrpivotpos.keyrpivotpos+1.high.keys 其中 lowpivotposhigh。求解：通过递归调用快速排序对左、右子区间Rlow.pivotpos-1和 rpivotpos+1.high快速排序。组合：因为当求解步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，组合步骤无须做什么，可看作是空操作。void heapadjust(sqlist&l,int s,int m)/筛选法调整堆，使其成为大顶堆 rc=l.rs.key;计科 021：潘伟丰 第
8、 3 页 共 9 页 for(j=2*s;j=m;j*=2)if(jm&l.rj.keyl.rj.key)break;l.rs.key=l.rj.key;s=j;l.rs.key=rc;void heapsort(sqlist&l)/建堆的过程 for(i=l.length/2;i0;i-)heapadjust(l,i,l.length);for(i=l.length;i1;i-)t=l.r1.key,l.r1.key=l.ri.key,l.ri.key=t;heapadjust(l,1,i-1);基本思想：堆排序利用了大根堆堆顶记录的关键字最大这一特征，使得在当前无序区中选取最大关键字的记录
9、变得简单。先将初始文件 R1.n建成一个大根堆，此堆为初始的无序区。再将关键字最大的记录 R1(即堆顶)和无序区的最后一个记录 rn交换，由此得到新的无序区 r1.n-1和有序区 rn，且满足 r1.n-1.keysrn.key。由于交换后新的根 R1可能违反堆性质，故应将当前无序区 r1.n-1调整为堆。然后再次将 r1.n-1中关键字最大的记录 r1和该区间的最后一个记录 Rn-1交换，由 此 得 到 新 的 无 序 区 r1.n-2 和 有 序 区 rn-1.n，且 仍 满 足 关 系r1.n-2.keysrn-1.n.keys，同样要将 r1.n-2调整为堆。直到无序区只有一个元素为止
10、。void oesort(sqlist&l,int n)/奇偶交换排序 change=1;标志变量，若其为零，即两次更替的交换中都没有交换数据，即排序结束 while(change)change=0;for(i=1;il.ri+1.key)t=l.ri.key,l.ri.key=l.ri+1.key,l.ri+1.key=t;change=1;for(i=2;il.ri+1.key)t=l.ri.key,l.ri.key=l.ri+1.key,l.ri+1.key=t;change=1;计科 021：潘伟丰 第 4 页 共 9 页 算法过程：第一趟对序列中的所有奇数项i 扫描，第二趟对序列中的
11、所有偶数项i 扫描。若 ri ri+1，则交换它们。第三趟有对所有的奇数项，第四趟对所有的偶数项，如此反复，直到整个序列全部排好序为止。五源程序：#include stdio.h#include malloc.h#include conio.h#define maxsize 5 typedef struct int key;redtype;typedef struct redtype*r;int length;sqlist;void shellsort(sqlist l,int d)int i,j;d=l.length/2;while(d0)for(i=d+1;i=l.length;+i)if
12、(l.ri.key0&l.r0.keyl.rj.key;j-=d)l.rj+d=l.rj;l.rj+d=l.r0;d=d/2;void quicksort(sqlist l,int low,int high)int i,j;if(lowhigh)i=low;j=high;l.r0=l.ri;do while(il.r0.key)-j;if(ij)l.ri=l.rj;+i;while(ij&l.ri.key=l.r0.key)+i;计科 021：潘伟丰 第 5 页 共 9 页 if(ij)l.rj=l.ri;-j;while(i!=j);l.ri=l.r0;quicksort(l,low,i-1
13、);quicksort(l,i+1,high);void heapadjust(sqlist l,int s,int m)int rc,j;rc=l.rs.key;for(j=2*s;j=m;j*=2)if(jm&l.rj.keyl.rj.key)break;l.rs.key=l.rj.key;s=j;l.rs.key=rc;void heapsort(sqlist l)int i,t;for(i=l.length/2;i0;i-)heapadjust(l,i,l.length);for(i=l.length;i1;i-)t=l.r1.key,l.r1.key=l.ri.key,l.ri.ke
14、y=t;heapadjust(l,1,i-1);void oesort(sqlist l,int n)int t,i,change;change=1;while(change)change=0;for(i=1;il.ri+1.key)计科 021：潘伟丰 第 6 页 共 9 页 t=l.ri.key,l.ri.key=l.ri+1.key,l.ri+1.key=t;change=1;for(i=2;il.ri+1.key)t=l.ri.key,l.ri.key=l.ri+1.key,l.ri+1.key=t;change=1;main()int i,j,low,high,amaxsize+1;
15、char ch;sqlist l;clrscr();l.r=(redtype*)malloc(maxsize*sizeof(int);if(!l.r)printf(overflow);l.length=0;printf(nnplease input five elements:nn);for(i=1;imaxsize+1;i+)scanf(%d,&ai);l.length+;getchar();do for(j=1,i=1;jmaxsize+1;i+,j+)l.ri.key=aj;printf(nnWelcome to use PanWeiFengs KeChenSheJinn);printf
16、(s:shellsorttq:quicksortnn);printf(h:heapsortte:oesortnn);printf(o:quitnn);printf(please input the way:);ch=getchar();clrscr();printf(nnthe orignal array:);for(i=1;imaxsize+1;i+)printf(%d,l.ri.key);printf(nn);计科 021：潘伟丰 第 7 页 共 9 页/*printf(please input the way:);ch=getchar();*/getchar();switch(ch)ca
17、se s:shellsort(l,l.length);printf(nnthe odered arry:);for(i=1;imaxsize+1;i+)printf(%d,l.ri.key);printf(nn);break;case q:low=1;high=l.length;quicksort(l,low,high);printf(nnthe odered arry:);for(i=1;imaxsize+1;i+)printf(%d,l.ri.key);printf(nn);break;case h:heapsort(l);printf(nnthe odered arry:);for(i=
18、1;imaxsize+1;i+)printf(%d,l.ri.key);printf(nn);break;case e:oesort(l,l.length);printf(nnthe odered arry:);for(i=1;imaxsize+1;i+)printf(%d,l.ri.key);printf(nn);break;case o:exit(0);default:printf(nnerror!write again!n);while(1);六程序运行结果：当你编译连接通过后，运行。please input five elements:计科 021：潘伟丰 第 8 页 共 9 页 6
19、4 5 8 3 回车后出现大括号内的部分 Welcome to use PanWeiFengs KeChenSheJi s:shellsort q:quicksort h:heapsort e:oesort o:quit please input the way:s 输入 s 回车后出现大括号内的部分 the orignal array:6 4 5 8 3 the odered array:3 4 5 6 8 Welcome to use PanWeiFengs KeChenSheJi s:shellsort q:quicksort h:heapsort e:oesort o:quit ple
20、ase input the way:q 输入 q 回车后出现大括号内的部分 the orignal array:6 4 5 8 3 the odered array:3 4 5 6 8 Welcome to use PanWeiFengs KeChenSheJi s:shellsort q:quicksort h:heapsort e:oesort o:quit please input the way:h 输入 h 回车后出现大括号内的部分 the orignal array:6 4 5 8 3 the odered array:3 4 5 6 8 Welcome to use PanWei
21、Fengs KeChenSheJi s:shellsort q:quicksort h:heapsort e:oesort o:quit please input the way:e 输入 e 回车后出现大括号内的部分 the orignal array:6 4 5 8 3 the odered array:3 4 5 6 8 Welcome to use PanWeiFengs KeChenSheJi s:shellsort q:quicksort h:heapsort e:oesort o:quit please input the way:r 计科 021：潘伟丰 第 9 页 共 9 页 输入 r 回车后出现大括号内的部分 the orignal array:6 4 5 8 3 error!write again!Welcome to use PanWeiFengs KeChenSheJi s:shellsort q:quicksort h:heapsort e:oesort o:quit please input the way:o 输入 o 回车后，将返回编辑窗口。程序结束。七总结：通过本课程设计，我们对比较流行的几种算法定有了一个比较详细的认识，集中的编写也便于记忆。但我们不能死扣这几种算法，要有自己的创新。计科 021：潘伟丰(200232225134)