数据结构课程设计-排序算法实现

数据结构与算法课程设计成果报告排序算法实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程 1341 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目排序算法实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1课程设计目标与任务11.1 课程设计目标11.2 课程设计任务11.3 课程设计基本要求12 分析与设计22.1 题目需求分析22.2 存储结构设计32.3 算法描述42.4 程序流程图72.5 程序测试说明73 程序清单84.测试134.1 测试数据134.2 测试结果分析135 总结14参考文献151 课程设计目标与任务1.1 课程设计目标数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学是软件设计的综合训练,包括问题分析，总体结构设计用户界面设计，程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工作方法学生通过数据结构课程设计各方面得到锻炼。1.2 课程设计任务设计排序相关函数库，以便在程序设计中调用，要求设计程序，产生20000个随机数，完成下面功能：（1）对这些数分别进行直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序、简单选择排序，堆排序，2路-归并排序等排序，并把排序结果进行保存。（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所写程序来实现相关问题的要求。1.3 课程设计基本要求严格按照题意要求，独立进行设计，不能随意更改。若确因条件所限，必须要改变课题要求时，应在征得指导教师同意的前提下进行。学生应制定实习工作计划，认真完成实习的各个环节，并在老师的指导下认真组织实习工作，撰写实习报告，做好实习总结。2 分析与设计2.1 题目需求分析1.直接插入排序思路：设有一组关键字K1,K2.Kn，排序开始便认为K1是一个有序的序列，让K2插入到表长为1的有序序列，使之成为一个表长为2的有序序列，让K3插入到表长为2的有序序列，使之成为表长为3的有序序列，依次类推，最后Kn插入到上述表长为n-1的有序序列，得到一个表长为n的有序序列。2.折半插入排序思路：在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为alow,末元素设置为ahigh，则轮比较时将待插入元素与am,其中m=(low+high)/2相比较,如果比参考元素小，则选择alow到am-1为新的插入区域(即high=m-1)，否则选择am+1到ahigh为新的插入区域（即low=m+1），如此直至low=high不成立，即将此位置之后所有元素后移一位，并将新元素插入ahigh+1。3.希尔排序思路：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2,d2d1,再将到d2作为增量继续分组，再进行直接插入排序，依次向下取值，直到完成排序。4.起泡排序思路：比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。5.快速排序思路：快速排序的实现基于分治法，具体分为三个步骤。假设待排序的序列为Lm.n。序列Lm . n被划分成两个可能为空的子序列Lm . pivot-1和Lpivot+1 . n，使Lm . pivot-1的每个元素均小于或等于Lpivot，同时Lpivot+1. n的每个元素均大于Lpivot。其中Lpivot称为这一趟分割中的主元（也称为枢轴、支点）。通过递归调用快速排序，对子序列Lm . pivot-1和Lpivot+1 . r排序。 由于两个子序列是就地排序的，所以对它们的合并不需要操作，整个序列Lm . n已排好序。6.简单选择排序思路：序序列的记录个数为。i取1,2,n-1,从所有n-i+1个记录（R,Ri+1,Rn中找出排序码最小的记录，与第个记录交换。执行n-1趟 后就完成了记录序列的排序。2.2 存储结构设计此程序采用的是线性表的动态顺序存储结构：#define LIST_INIT_SIZE 100/线性表存储空间的初始分配量#define LISTINCREMENT 10/线性表存储空间的分配增量Typedef structElemType *elem;/存储空间基址Int length;/当前长度Int listsize;/当前分配的存储容量（以sizeof(ElemType)为单位）SqList;上述定义中，数组指针elem指示存储空间基址，length表示线性表的当前长度，对线性表的初始化操作就是为顺序表预定义大小的数组空间，并将线性表的当前长度设为“0”，listsize指示当前分配的存储空间大小，一旦元素插入而空间不足，可进行再分配。1.3 算法描述1.直接插入排序 设置R0为哨兵，将剩下的数值逐个进行插入，直至完成一趟排序：void InsertSort ( elem R , int n) / 对记录序列R1.n作直接插入排序。 for ( i=2; i=n; +i ) R0 = Ri; / 复制为监视哨 for ( j=i-1; R0 Rj; -j ) Rj+1 = Rj; / 记录后移 Rj+1 = R0; / 插入到正确位置 / InsertSort2.折半插入排序因为R1.i-1是一个按关键字有序的序列，则可以利用折半查找实现“在R1.i-1中查找Ri的插入位置：void BInsertSort (elem R ， int n) / 对记录序列R1.n作折半插入排序。 for ( i=2; i=n; +i ) R0 = Ri; / 将Ri暂存到R0 low = 1; high = i-1; while ( low = high) /在Rlow.high中折半查找插入的位置 m = (low+high)/2; / 折半 if (R0 =high+1; -j ) Rj+1 = Rj; / 记录后移 Rhigh+1 = R0; / 插入 / BInsertSort3.希尔排序先取一个正整数d1n，把所有相隔d1的记录放一组，组内进行直接插入排序，然后取d2d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止：void ShellInsert ( elem R , int dk ) / 对待排序列R作一趟希尔插入排序 for ( i=dk+1; i=n; +i ) if ( Ri Ri-dk) void ShellSort (elem R , int d , int t) / 按增量序列d 0.t-1对顺序表L作希尔排序。 for ( k=0; k0 & R01) for ( j = 1; j i; j+ ) if (R j+1 R j ) Swap(R j , R j+1 ); /if / while / BubbleSort5.快速排序选定一个中间数作为参考，所有元素与之比较，小的调到其左边，大的调到其右边：int Partition (Elem R, int low, int high) / 交换记录子序列Rlow.high中的记录，使枢轴记录到位，并返回其所/ 在位置，此时，在它之前（后）的记录均不大（小）于它R0 = Rlow; / 用子表的第一个记录作枢轴记录pivotkey = Rlow; / 枢轴记录关键字while (lowhigh) / 从表的两端交替地向中间扫描while(low=pivotkey)-high;Rlow = Rhigh; / 将比枢轴记录小的记录移到低端while (lowhigh & Rlow=pivotkey) +low;Rhigh = Rlow; / 将比枢轴记录大的记录移到高端Rlow = R0; / 枢轴记录到位return low; / 返回枢轴位置 / Partitionvoid QSort (Elem R, int low, int high) / 对记录序列Rlow.high进行快速排序if (low high) / 长度大于1pivotloc = Partition(L, low, high); / 将L.rlow.high一分为二QSort(L, low, pivotloc-1); / 对低子表递归排序，pivotloc是枢轴位置QSort(L, pivotloc+1, high);/ 对高子表递归排序 / Qsort6.简单选择排序在待排序的数据中选出最大（小）的元素放在其最终的位置：Void SelectSort(SqList &L)/对顺序表做简单选择排序for(i=1;iL.length;+i)/选择第i小的记录，交换到位j=SelectMinKey(L,i);/在L.riL.length中选择key最小记录if(i!=j)Lri-L.rj;/与第i个记录交换/ SelectSort开始2.4 程序流程图显示菜单输入序号简单选择排序快速排序起泡排序希尔排序折半插入排序直接插入排序按输入序号输出结果结束图1-2程序执行流程图开始执行后，会出现提示语句，提示1-6分别代表6种排序方法，对于生成的数组，点击1-6任意数字，调用相应的排序方法进行排序。输出结果后，按任意键结束。2.5 程序测试说明主函数会调用rand()方法，随机产生指定数目数值。并将数值赋予指定数组，通过提示语句输入16数值，16分别代表不同的排序方式，当输入数字1时，通过switch语句，将执行直接插入排序函数，然后通过输出函数，输出所需结构。3 程序清单#include#include#include#define MAXE 20000typedef int KeyType;typedef struct /*记录类型*/KeyType key; /*关键字项*/ /InfoType data; /*其他数据项,类型为InfoType*/ RecType;void InsertSort(RecType R,int length);/直接插入排序void BInsertSort (RecType R,int low,int high,int length);/折半插入排序void ShellSort(RecType R,int n);/希尔排序void bubble_sort(RecType R,int length);/起泡排序int FindPos(RecType R,int low,int high);void QuickSort(RecType R,int low,int high);int SelectMinKey(RecType R,int i,int length);void SelectSort(RecType R,int length);/简单选择排序void showSort(RecType R);/快速排序void showSort_F(RecType R);int main(void) int val;int i;RecType RMAXE;srand(unsigned)time(NULL); for(i=0;i=10;i+) Ri.key=(rand()%100+1); printf(产生的随机数序列为：); for(i=0;i=10;i+) printf(%3d,Ri.key); printf(n); printf(随机输入1到6数字：); scanf(%d,&val); switch(val) case 1: InsertSort(R,10); printf(随机数经直接插入排序后：); showSort(R); break; case 2:BInsertSort(R,1,10,10); printf(随机数经折半插入排序后：); showSort(R); break; case 3:ShellSort(R,10); printf(随机数经希尔插入排序后：); showSort_F(R); break; case 4:bubble_sort(R,10); printf(随机数经起泡排序后：); showSort_F(R); break; case 5:QuickSort(R,0,9); printf(随机数经快速排序后：); showSort_F(R); case 6:SelectSort(R,10); printf(随机数经简单选择排序后：); showSort_F(R); return 0;void InsertSort(RecType R,int length) / 对数组a作直接插入排序 int i,j; for(i=2;i=length;+i) if(Ri.keyRi-1.key) / 需将ai插入有序子表 R0.key=Ri.key; / 复制为哨兵 Ri.key=Ri-1.key; for(j=i-2;R0.keyRj.key;-j) Rj+1.key=Rj.key; / 记录后移 Rj+1.key=R0.key; / 插入到正确位置 void BInsertSort (RecType R,int low,int high,int length) int m; for ( int i=2; i=length; +i ) R0.key = Ri.key; / 将Ri暂存到R0 low = 1; high = i-1; while ( low = high) /在Rlow.high中折半查找插入的位置 m = (low+high)/2; / 折半 if (R0.key =high+1; -j ) Rj+1.key = Rj.key; / 记录后移 Rhigh+1.key = R0.key; / 插入 / BInsertSortvoid ShellSort(RecType R,int n)/*希尔排序算法*/int i,j,d,k;RecType temp;d=n/2;/*d取初值n/2*/while (d0) for (i=d;i=0 & Rj.keyRj+d.key) temp=Rj; /*Rj与Rj+d交换*/Rj=Rj+d;Rj+d=temp;j=j-d;printf( d=%d: ,d);/*输出每一趟的排序结果*/for (k=0;kn;k+)printf(%3d,Rk.key);printf(n); d=d/2; /*递减增量d*/void bubble_sort(RecType R,int length) / 将a中整数序列重新排列成自小至大有序的整数序列(起泡排序) int i,j,t; for(i=0;ilength-1;i+) for(j=i+1;jRj.key) t=Ri.key; Ri.key=Rj.key; Rj.key=t; void QuickSort(RecType R,int low,int high)int pos;if(lowhigh)pos=FindPos(R,low,high); QuickSort(R,low,pos-1);QuickSort(R,pos+1,high);int FindPos(RecType R,int low,int high) int val=Rlow.key; while(lowhigh) while(low=val) -high; Rlow.key=Rhigh.key; while(lowhigh&Rlow.key=val) +low; Rhigh.key=Rlow.key; Rlow.key=val; return high; int SelectMinKey(RecType R,int i,int length) / 返回在ai.length中key最小的记录的序号 int min; int j,k; k=i; / 设第i个为最小 min=Ri.key; for(j=i+1;jlength;j+) if(Rj.keymin) / 找到更小的 k=j; min=Rj.key; return k; void SelectSort(RecType R,int length) / 对数组a作简单选择排序 int i,j; int t; for(i=0;ilength-1;+i) / 选择第i小的记录，并交换到位 j=SelectMinKey(R,i,length); / 在ai.length中选择最小的记录 if(i!=j) / 与第i个记录交换 t=Ri.key; Ri.key=Rj.key; Rj.key=t; void showSort(RecType R)int i;for(i=1;i=10;i+)printf(%d ,Ri.key);printf(n);void showSort_F(RecType R)int i;for(i=0;i10;i+)printf(%d ,Ri.key);printf(n);4 测试4.1 测试数据由函数rand()产生的随机数进行测试。4.2 测试结果分析图1-3直接插入排序当输入数字1时，主函数通过switch语句调用直接插入排序，对数组进行从小到大的排序。图1-4冒泡排序当输入数字4时，主函数通过switch语句调用冒泡排序，对数组进行从小到大的排序。5 总结通过这次课程设计的学习让我学会了许多，让我对专业知识有了初步的了解。在这次课程设计中，首先实现随机数的生成，将生成的指定数目的随机数一一对应的赋予定义的空数组，经选择语句分别执行直接插入排序，折半插入排序，希尔排序，起泡排序，快速排序，简单选择排序等6种排序对数组中的数值进行排序。这次课程设计还有许多不足，如部分排序方法编程代码过于复杂，此外，由于编程各种排序方法的区别较大，使用了不同的输出函数，增加了程序的复杂性。此外，由于能力有限，还有无法实现的2种排序。但我也学到了很多东西，如，掌握一些排序方法的实现，熟悉了编写代码的一般步骤：思考问题，写出解决方案，写出伪代码，完成代码，调试程序。我从编写过程中，发现自己更多的不足，如对C语言的掌握不够牢靠，对于C语言各种函数的调用也不够灵活等。希望在以后的编程过程中，能更加耐心和细心，不熟悉也不要慌张，不慌不忙的进行程序编写和调试。参考文献1数据结构（C语言版）严蔚敏 清华大学出版社 20022数据结构-C语言描述 王路群 中国水利水电出版社 20073数据结构实验教程（C语言版） 王国钧 清华大学出版社 20094数据结构题集严蔚敏,吴伟民编 清华大学出版社 20025C语言程序设计谭浩强 清华大学出版社6C语言入门经典霍顿（美）清华大学出版社#include#include#include#define MAXE 20000typedef int KeyType;typedef struct /*记录类型*/KeyType key; /*关键字项*/ /InfoType data; /*其他数据项,类型为InfoType*/ RecType;void InsertSort(RecType R,int length);/直接插入排序void BInsertSort (RecType R,int low,int high,int length);/折半插入排序void ShellSort(RecType R,int n);/希尔排序void bubble_sort(RecType R,int length);/起泡排序int FindPos(RecType R,int low,int high);void QuickSort(RecType R,int low,int high);int SelectMinKey(RecType R,int i,int length);void SelectSort(RecType R,int length);/简单选择排序void showSort(RecType R);/快速排序void showSort_F(RecType R);int main(void) int val;int i;RecType RMAXE;srand(unsigned)time(NULL); for(i=0;i=10;i+) Ri.key=(rand()%100+1); printf(产生的随机数序列为：); for(i=0;i=10;i+) printf(%3d,Ri.key); printf(n); printf(随机输入1到6数字：); scanf(%d,&val); switch(val) case 1: InsertSort(R,10); printf(随机数经直接插入排序后：); showSort(R); break; case 2:BInsertSort(R,1,10,10); printf(随机数经折半插入排序后：); showSort(R); break; case 3:ShellSort(R,10); printf(随机数经希尔插入排序后：); showSort_F(R); break; case 4:bubble_sort(R,10); printf(随机数经起泡排序后：); showSort_F(R); break; case 5:QuickSort(R,0,9); printf(随机数经快速排序后：); showSort_F(R); case 6:SelectSort(R,10); printf(随机数经简单选择排序后：); showSort_F(R); return 0;void InsertSort(RecType R,int length) / 对数组a作直接插入排序 int i,j; for(i=2;i=length;+i) if(Ri.keyRi-1.key) / 需将ai插入有序子表 R0.key=Ri.key; / 复制为哨兵 Ri.key=Ri-1.key; for(j=i-2;R0.keyRj.key;-j) Rj+1.key=Rj.key; / 记录后移 Rj+1.key=R0.key; / 插入到正确位置 void BInsertSort (RecType R,int low,int high,int length) int m; for ( int i=2; i=length; +i ) R0.key = Ri.key; / 将Ri暂存到R0 low = 1; high = i-1; while ( low = high) /在Rlow.high中折半查找插入的位置 m = (low+high)/2; / 折半 if (R0.key =high+1; -j ) Rj+1.key = Rj.key; / 记录后移 Rhigh+1.key = R0.key; / 插入 / BInsertSortvoid ShellSort(RecType R,int n)/*希尔排序算法*/int i,j,d,k;RecType temp;d=n/2;/*d取初值n/2*/while (d0) for (i=d;i=0 & Rj.keyRj+d.key) temp=Rj; /*Rj与Rj+d交换*/Rj=Rj+d;Rj+d=temp;j=j-d;printf( d=%d: ,d);/*输出每一趟