《数据结构与算法》课程设计报告-排序算法实现.doc

河南工程学院数据结构与算法课程设计成果报告排序算法实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1341班 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目排序算法实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1设计目标11.2设计任务11.3设计项目11.4所需工具12 分析与设计22.1 实验原理22.2 存储结构设计32.3 算法描述32.4 程序流程图62.5 测试程序说明63 程序清单74 测试104.1 测试数据104.2 测试结果分析105 总结11参考文献111 课程设计目标与任务1.1设计目标数据结构课程设计是在学完数据结构课程后的实践教学环节。该实践教学是软件设计的综合训练，包括问题分析、总体结构设计用户界面设计、程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力，培养科学的软件工作方法。通过数据结构课程设计，能力得到锻炼：（1）能根据实际问题具体情况结合数据结构课程中的基本理论和算法，正确分析出数据的逻辑结构，合理选择相应存储结构，设计出解决问题的有效算法；（2）通过上机实习，验证自己设计算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改，培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平；（3）尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来，获得算法的直观感受。1.2设计任务根据提供的实习题目，认真完成软件设计的全部过程，并以最终软件设计成果来证明其独立完成实际任务的能力。从而，反映出理解和运用数据结构与算法的水平和能力，最后完成软件设计和程序调试并提交课程设计报告书，报告书中包含设计的算法及部分程序代码。1.3设计项目设计排序相关函数库，以便在程序设计中调用，要求设计程序产生20000个随机数，完成下面功能：（1）对这些数分别进行直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、2-路归并排序，并把排序结果进行保存；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。1.4所需工具PC机、Win7、VC6.0语言编辑。2 分析与设计2.1 实验原理直接插入排序：在含有i-1个记录的有序子序列a1.i-1中插入一个记录ai后，变成含有i个记录的有序子序列r1.i；为了在查找插入位置的过程中避免数组下标出界，在r0处设置监视哨。在自i-1起往前搜索的过程中，可以同时后移记录。整个排序过程为进行n-1趟插入，时间复杂度为O(n2)。折半插入排序：折半插入排序是在直接插入排序的基础上进行改进，操作上利用“折半查找”来实现。从时间上比较，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。因此，折半插入排序的时间复杂度仍为O（n2）。希尔排序：希尔排序又称“缩小增量排序”，也是一种插入排序类的方法。先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。子序列构成不是简单地“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列。时间复杂度为O（n3/2）。冒泡排序：第i趟冒泡排序是从a1到an-i+1依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i+1的位置上。若初始序列为“正序”序列，则只需进行一趟排序，在排序过程中进行n-1次关键字间的比较，且不移动记录；反之，若初始序列为“逆序”序列，则需进行n-1趟排序。时间复杂度为O(n2)。快速排序：在待排序的序列中，首先任取一个记录作为枢轴，然后将关键字较它小的记录都安置在它的位置之前，将所有关键字较它的小的记录都安置在它的位置之前，所有比它大的记录都安置在它的位置之后。附设两个指针low和high，初始值分别为low、high，设枢轴记录关键字为pivokey，先将枢轴记录暂存在a0的位置上，排序过程只作alow或ahigh的单向移动，直至一趟排序结束后再将枢轴记录移至正确位置上。时间复杂度为O(n2)。简单选择排序：每一趟选择排序从n-i+1个记录中选出关键字最小的记录，并和第i(1=i=n)个记录交换。令i从1至n-1，进行n-1趟选择操作。时间复杂度为O（n2）。2.2 存储结构设计顺序存储结构是一种随机存取的存储结构，线性表长度可变，且所需最大存储空间随问题不同而不同。在该程序中数组元素是调用rand()函数随机存取，因此选用顺序存储结构。在这种存储结构中，容易实现数组的某些操作。缺点是在移动元素上耗费时间。2.3 算法描述直接插入排序：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; / 插入到正确位置 / InsertSort折半插入排序：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; / 插入 / BInsertSort希尔排序：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 / BubbleSort快速排序：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);/ 对高子表递归排序 / Qsort简单选择排序：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 程序流程图程序开始。确定要输出数据的数量，即首先确定宏定义变量num值，再运行程序，程序会依次执行各个函数，最后输出排好的序列。程序结束。图2.4 程序流程图2.5 测试程序说明主函数调用rand()函数随机产生指定数目的数据，通过调用各个排序算法即可输出由小到大排好顺序的序列。因为主函数中要产生随机数据，调用rand();函数，所以要有文件头#include 。各排序算法函数声明：void InsertSort(long a,int length);/直接插入排序函数声明void BInsertSort(long a,long length);/折半插入排序函数声明void ShellSort(long a,int dlta,int t);/希尔排序函数声明void BubbleSort(long a,int length);/冒泡排序函数声明void QuickSort(long a,int low,int length);/快速排序函数声明void SelectSort(long a,int length);/简单选择排序函数声明程序中要用到输入函数printf();直接使用程序会显得冗长，因此声明void print(long a,int n);函数输出排好的序列。3 程序清单#include#include#define num 40#define TRUE 1#define FALSE 0void InsertSort(long a,int length);void BInsertSort(long a,long length);void ShellSort(long a,int dlta,int t);void BubbleSort(long a,int length);void QuickSort(long a,int low,int length);void SelectSort(long a,int length);void ShellInsert(long a,int length,int dk);int Partition(long a,int low,int high);int SelectMinKey(long a,int length,int i);void print(long a,int n);int main()int i=0;int dlta3=5,3,1;long anum;for(i=0;inum;i+)ai=rand()%100;printf(直接插入所排序列为：n);InsertSort(a,num);print(a,num);printf(n);printf(折半插入所排序列为：n);BInsertSort(a,num);print(a,num);printf(n);printf(希尔排序所排序列为：n);ShellSort(a,dlta,3);print(a,num);printf(n);printf(起泡排序所排序列为：n);BubbleSort(a,num); print(a,num);printf(n);printf(快速排序所排序列为：n);QuickSort(a,1,num);print(a,num);printf(n);printf(简单选择所排序列为：n);SelectSort(a,num);print(a,num);printf(n);return 0;/直接插入排序void InsertSort(long a,int length) /对顺序表做直接插入排序int i,j;for(i=2;ilength;+i)if(aiai-1)a0=ai; /复制为哨兵 ai=ai-1;for(j=i-2;a0aj;-j)aj+1=aj; /记录后移 aj+1=a0; /插入到正确位置/折半插入排序void BInsertSort(long a,long length)/对顺序表做折半插入排序int i,j,mid,low,high;for(i=2;ilength;+i)a0=ai; /复制为哨兵low=1;high=i-1;while(low=high) /折半查找有序插入位置mid=(low+high)/2; /折半if(a0=high+1;-j)aj+1=aj;ahigh+1=a0; /插入/希尔排序void ShellInsert(long a,int length,int dk)/对顺序表做一趟希尔插入排序int i,j;for(i=dk+1;ilength;+i)if(ai0&a0aj;j-=dk)aj+dk=aj; /记录后移，查找插入位置aj+dk=a0; /插入void ShellSort(long a,int dlta,int t) /对顺序表做希尔排序int k;for(k=0;k=1&change;-i)change=FALSE;for(j=0;jaj+1)n=aj;aj=aj+1;aj+1=n;change=TRUE;/快速排序int Partition(long a,int low,int high)int pivotkey;a0=alow; /用子表第一个记录作枢纽记录pivotkey=alow; /枢纽记录关键字while(lowhigh)while(low=pivotkey)-high;alow=ahigh; /将比枢纽记录小的记录移到低端while(lowhigh&alow=pivotkey)+low;ahigh=alow; /将比枢纽记录大的记录移到高端alow=a0; /枢纽记录到位return low; /返回枢纽位置void QuickSort(long a,int low,int length)int pivotloc,high;high=length;if(lowhigh)pivotloc=Partition(a,low,high);QuickSort(a,low,pivotloc-1); /对低子表递归排序QuickSort(a,pivotloc+1,high); /对高子表递归排序/简单选择排序int SelectMinKey(long a,int length,int i)/选择最小记录int n;for(n=i+1;nan)i=n;return i;void SelectSort(long a,int length)/对顺序表做简单选择排序int i,j,x;for(i=1;ilength;+i)j=SelectMinKey(a,length,i);if(i!=j) /与第i个记录交换x=ai;ai=aj;aj=x;void print(long a,int n)/输出由小到大排列好的序列int i;for(i=1;in;i+)/每行20个数字对齐printf(%2d ,ai);if(i%20=0)printf(n);4 测试4.1 测试数据程序调用rand()函数产生的随机数据。4.2 测试结果分析在程序编译运行前首先确定序列数量num值，主函数调用rand()函数产生随机数。依次调用各算法，运行结果如下图：图4.2 运行结果5 总结“熟能生巧”这句话在各行各业都很适用，尤其是软件工程这门课程中。“大牛”不是说出来的，只有多写多练多想才能成为人们口中说道称羡的“大牛”。在这次课程设计中，充分认识了自己并发现了自己的不足专业知识掌握不太牢固，想法单一，缺少动手能力。认识到自己的缺点，就要努力克服改正。“学而不思则罔，思而不学则殆”。想要学好本专业，就要把“心脑手”结合在一起。这次实践，也使我真正体会到了算法是程序设计的精髓，只有洞悉算法，才能编写好一个称之为WONDERFUL的程序。最后，要感谢老师和同学们的帮助。如果没有老师的指导和同学们的帮助，我就无法完成程序设计任务，可见团队的力量远大于个人力量。所以我们在单独完成任务的同时，也要有团结别人的精神。参考文献(1)数据结构（C语言版）严蔚敏 清华大学出版社 2002(2)数据结构-C语言描述 王路群 中国水利水电出版社 2007(3)数据结构实验教程（C语言版） 王国钧 清华大学出版社 2009(4)数据结构题集严蔚敏,吴伟民编 清华大学出版社 2002#include#include#define num 40#define TRUE 1#define FALSE 0void InsertSort(long a,int length);void BInsertSort(long a,long length);void ShellSort(long a,int dlta,int t);void BubbleSort(long a,int length);void QuickSort(long a,int low,int length);void SelectSort(long a,int length);void ShellInsert(long a,int length,int dk);int Partition(long a,int low,int high);int SelectMinKey(long a,int length,int i);void print(long a,int n);int main()int i=0;int dlta3=5,3,1;long anum;for(i=0;inum;i+)ai=rand()%100;printf(直接插入所排序列为：n);InsertSort(a,num);print(a,num);printf(n);printf(折半插入所排序列为：n);BInsertSort(a,num);print(a,num);printf(n);printf(希尔排序所排序列为：n);ShellSort(a,dlta,3);print(a,num);printf(n);printf(起泡排序所排序列为：n);BubbleSort(a,num); print(a,num);printf(n);printf(快速排序所排序列为：n);QuickSort(a,1,num);print(a,num);printf(n);printf(简单选择所排序列为：n);SelectSort(a,num);print(a,num);printf(n);return 0;/直接插入排序void InsertSort(long a,int length) /对顺序表做直接插入排序int i,j;for(i=2;ilength;+i)if(aiai-1)a0=ai; /复制为哨兵 ai=ai-1;for(j=i-2;a0aj;-j)aj+1=aj; /记录后移 aj+1=a0; /插入到正确位置/折半插入排序void BInsertSort(long a,long length)/对顺序表做折半插入排序int i,j,mid,low,high;for(i=2;ilength;+i)a0=ai; /复制为哨兵low=1;high=i-1;while(low=high) /折半查找有序插入位置mid=(low+high)/2; /折半if(a0=high+1;-j)aj+1=aj;ahigh+1=a0; /插入/希尔排序void ShellInsert(long a,int length,int dk)/对顺序表做一趟希尔插入排序int i,j;for(i=dk+1;ilength;+i)if(ai0&a0aj;j-=dk)aj+dk=aj;