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

河南工程学院数据结构与算法课程设计成果报告排序算法的实现学生学号： 5 学生姓名： 学 院： 计算机学院 专业班级： 软件工程 1342 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目排序算法的实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务12 分析与设计22.1 题目需求分析22.2 存储结构设计32.3 算法描述32.4 程序流程图62.5 测试程序说明63 程序清单74 测试124.1 测试数据124.2 测试结果分析125 总结13参考文献141 课程设计目标与任务1.1 课程设计目标 数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学是软件设计的综合训练,包括问题分析，总体结构设计用户界面设计，程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工作方法学生通过数据结构课程设计各方面得到锻炼：1.能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法；2.通过上机实习,验证自己设计的算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改；3.培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平；4.尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来，获得算法的直观感受 。1.2 课程设计任务 设计排序相关函数库，以便在程序设计中调用，要求设计程序，产生20000个随机数，完成下面功能：1.对这些数分别进行直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、2-路归并排序，并把排序结果进行保存。2.最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；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.希尔排序思路：先取一个正整数d1(d1n)，把全部记录分成d1个组，所有距离为d1的倍数的记录看成一组，然后在各组内进行插入排序，然后去d2(d2=1)，即所有记录成为一个组，为此，一般选d1约为n/2，d2为d2/2,.,di=14.起泡排序思路：比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。5.快速排序思路：第一个关键字K1为控制字，将K1,K2,.Kn分成两个子区，使左区有的关键字小于等于K1,右区所有关键字大于等于K1,最后控制两个子区中间的适当位置。在子区内数据尚处于无序状态。将右区首、尾指针保存入栈，对左区进行与上一部相类似的处理，又得到他的左子区、右子区，控制字区中。重复以上两步6，直到左区处理完毕。然后退栈对一个个子区进行相似的处理，直到栈空。6.简单选择排序思路：简单选择排序过程中所需移动记录的次数比较少。最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录。最坏情况下，即待排序记录初始状态是按逆序排列的，则需要移动记录的次数最多为3（n-1）。过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时，需进行n-1次比较；当i=2时，需进行n-2次比较；依次类推，共需要进行的比较次数是(n-1)+(n-2)+2+1=n(n-1)/2。 2.2 存储结构设计 此程序采用的是线性表的动态顺序存储结构：#define LIST_INIT_SIZE 100/线性表存储空间的初始分配量#define LISTINCREMENT 10/线性表存储空间的分配增量Typedef structElemType *elem;/存储空间基址Int length;/当前长度Int listsize;/当前分配的存储容量（以sizeof(ElemType)为单位）SqList;上述定义中，数组指针elem指示存储空间基址，length表示线性表的当前长度，对线性表的初始化操作就是为顺序表预定义大小的数组空间，并将线性表的当前长度设为“0”，listsize指示当前分配的存储空间大小，一旦元素插入而空间不足，可进行再分配。2.3 算法描述1.直接插入排序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.折半插入排序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.希尔排序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 / 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个记录交换/ SelectSort2.4 程序流程图开始 如下图2-1所示是程序设计的流程图当开始测试程序时，将会显示出菜单页面，页面上将产生几个随机数，并提示输入相应的数字对随机数进行从大到小的排序，程序按照相应的输入数字进行操作输出结果，此时程序操作结束。 显示菜单输入序号5简单选择排序5快速排序4起泡排序3希尔排序2折半插入排序1直接插入排序 按输入序号选择输出结束图2-1 程序流程图2.5 测试程序说明主函数会调用srand()方法，随机产生指定数目数值。并将数值赋予指定数组，通过提示语句输入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 测试数据由srand()函数随机产生进行测试。4.2 测试结果分析图4-1为对程序进行测试的运行结果图图4-1 程序首页输入数字2，主函数调用switch语句，进行折半插入排序，运行结果见下图4-2图4-2 折半插入排序输入数字4，主函数调用switch语句，进行起泡排序，运行结果见下图4-3图4-3 起泡排序5 总结通过这次数据结构与算法课程设计的完成，从理论到实践，在整整一周的时间里 学到很多很多的的东西，不仅巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正提高自己的实际动手能力和独立思考的能力。我学会了设计排序相关函数库，且使用六种排序方法将产生的随机数进行排序，有直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序、简单选择排序。但算法还存在一些不足之处这次课程设计还有许多不足，如快速查找排序方法编程代码过于复杂，此外，由于编程的各种排序方法的区别较大，使用了不同的输出函数，增加了程序的复杂性。希望自己在以后的学习中可以认真学习举一反三，将学到的知识与实践相结合，活学活用，用认真的态度编好程序。参考文献1数据结构（C语言版）严蔚敏 清华大学出版社 20022数据结构-C语言描述 王路群 中国水利水电出版社 20073数据结构实验教程（C语言版） 王国钧 清华大学出版社 20094数据结构题集严蔚敏,吴伟民编 清华大学出版社 2002#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);/*输出每一趟的排序结果*/fo