数据结构实训报告

1、目录1课程设计目标与任务11.1 课程设计目标11.2 课程设计任务12分析与设计22.1题目需求分析22.2结构设计22.3算法描述32.4 算法比较分析72.5 程序流程图82.6 测试程序说明93程序.104测试164.1 测试数据164.2分析165总结18参考文献191 课程设计目标与任务1.1 课程设计目标通过本课程设计，使学生在数据结构的选择和应用、算法的设计与实现方面得到训练，加深对数据结构基本内容的理解和灵活应用，同时，在程序设计方法及上机操作方面受到比较系统严格的训练，培养工作所需要的动手能力。数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学是设计的综合训

2、练,包括问题分析，总体结构设计用户界面设计，程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的工作方法学生通过数据结构课程设计各方面得到锻炼：（1）能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的结构，并能设计出解决问题的有效算法；（2）通过上机实习,验证自己设计的算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改；（3）培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平；（4）尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行

3、过程以动态方式显示出来，获得算法的直观感受。1.2 课程设计任务设计排序相关函数库，以便在程序设计中调用，要求设计程序完成下面功能：（1）对这些数分别进行直接排序、折半排序、排序、起泡排序、快速排序、简单选择排序、堆排序、2-路归并排序，并把排序结果进行保存；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所写程序来实现相关问题的求解。2 分析与设计2.1 题目实现步骤为了实现题目要求：（1）先理解程序的功能，知道并会利用排序的算法。（2）首先设计数据的结构，构建程序框架，设计程序流程图如

4、图。（3）实现程序的功能模块，完成程序的调试。2.2结构设计在排序的过程中需要以下两种操作：（1）比较两个关键字的大小；（2）将从一个位置移动到另一个位置。前一个操作对大多数的算法都是必要的，而后一个操作可以通过改变的方式来实行。待排序的序列可有三种存储方式：（1）待排序的一组存放在地址连续的一组单元上。它类似于线性表的顺序结构，在序列中相邻的两个，他们的位置也相邻。在这种方式中，之间的次序关系由其位置决定，实现排序必须借助移动；（2）待排序的一组存放在静态链表中，之间的次序关系由指针指示，实现排序不需要移动，仅需修改指针即可；（3）待排序本身在一组地址连续的单元内，同时令设一个指示各个位置的

5、地址向量，在排序过程中不需要移动本身。，而移动地址向量中这些的“地址”，在排序结束之后在地址向量中的值来调整的位置。在以下设计的算法中，待排的数据类型为：#define MAXSIZE 20 / 一个用作示例的小顺序表的最大长度KeyType; / 定义关键字类型为整型InfoType; / 定义其它数据项的类型typedeftypedef类型struct RedType /KeyType key; / 关键字项InfoType otherinfo; / 其它数据项，具体类型在主程中定义;struct SqList / 顺序表类型RedType rMAXSIZE+1; / r0闲置或用作哨兵单

6、元length; / 顺序表长度;2.3 算法描述（1）直接排序这是一种最简单的排序方法，基本操作是将一个到已经排好序的有序表中，从而得到一个新的、数增一的有序表。第一趟比较前两个数，然后把第二个数按大小到有序表中； 第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。直接排序属于稳定的排序，时间复杂性为O(n2)，空间复杂度为 O(1)。【例】关键字为 49 38 65 97 76 13 27 49 则直接做法如图 2-1图 直接法示例直接排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比

7、较数值确定其最终位置。直接排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。值得注意的是，需用一个空间来保存当前待比较的数值，因为当一趟比较完成时，要将待比较数值置入比它小的数值的后一位排序类似玩牌时整理手中纸牌的过程。排序的基本初始关键字（49） 38 65 97 76 13 27 49I=2；（38） （3849）65 97 7613 27 49I=3；（65） （3849 65）97 7613 27 49I=4；（97） （3849 65 97）

8、7613 27 49I=5；（76） （3849 65 76 97） 13 27 49I=6；（13） （1338 49 65 76） 97 27 49I=7；（27） （1327 38 49 6576 97）49I=8；（49） （1327 38 49 4965 76 97 ）监视哨L.r0方法是：每步将一个待排序的按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部完毕为止。（2）折半它是对排序排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素前面已排好序的序列中。由于前半部分为已排好序的数列，这样不用按顺序依次寻找点，可以采用折半查找的方法来加快寻找点的速度。在将一个新

9、元素已排好序的数组的过程中，寻找点时，将待区域的首元素设置为 alow，末元素设置为 ahigh，则轮比较时将待元素与am，其中 m=(low+high)/2 相比较,如果比参考元素小，则选择 alow到 am-1为新的区域(即high=m-1)，否则选择 am+1到 ahigh为新的区域（即low=m+1），如此直至 low=high 不成立，即将此位置之后所有元素后移一位，并将新元素ahigh+1。（3）排序排序(SSort)是排序的一种。是针对直接排序算法的改进。该方法又称缩小增量排序，因DLS于 1959 年提出而得名。先取一个小于 n的整数d1 作为第一个增量，把文件的全部录放在同一

10、个组中。先在各组内进行直接分组。所有距离为 d1 的倍数的记排序；然后，取第二个增量 d2d1重复上述的分组和排序，直至所取的增量=1(d2d1)，即所有放在同一组中进行直接排序为止。（4）冒泡排序算法冒泡排序算法的如下：（从后往前）1比较相邻的元素。如果第一个比第二个大，就交换他们两个。2对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。3针对所有的元素重复以上的步骤，除了最后一个。4持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。（5）快速排序快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Ho

11、are 在 1962 年提出。它的基本是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。（6）归并排序归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并过程为：比较 ai和 aj的大小，若 aiaj，则将第一个有序表中的元素 ai到r

12、k中，并令i 和k 分别加上 1；否则将第二个有序表中的元素 aj到rk中，并令j 和k 分别加上 1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素到 r 中从下标k 到下标t 的单元。归并排序的算法通常用递归实现，先把待排序区间s,t以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间s,t。（7）堆排序堆排序(Heapsort)是指利用堆积树（堆）这种资料结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素。堆排序利用了大根堆(或小根堆)堆顶的关键字最大(或最小)这一特征，使得在当前无序区中选取最大

13、(或最小)关键字的变得简单。n 个关键字序列Kl，K2，Kn 称为（Heap），当且仅当该序列满足如下性质（简称为堆性质）：大根堆示例(1)ki=k(2i）且 ki=号。/k(i）相当于二叉树的非叶子结点，K(2i）则是节点，k(2i+1）是右子节点。将此序列所的向量R1.n看做是一棵完全二叉树的结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。【例】关键字序列（10，15，56，25，30，70）和（70，56，30，25，15，10）分别满足堆性质（1）和（2），故它们均是堆，其对应的完全二叉树分别如图 2-3 根堆

14、示例和大根堆示例所示。101556253070705630251510图 堆示例和大根堆示例大根堆和小根堆：根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者的堆称为小根堆，又称最小堆。根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆。注意：堆中任一亦是堆。以上的堆实际上是二叉堆（BinaryHeap），类似地可定义 k 叉堆。堆的高度：高度堆可以被看成是一棵树，结点在堆中的高度可以被定义为从本结点到叶子结点的最长简单下降路径上边的数目；定义堆的高度为树根的高度。将看到，堆结构上的一些基本操作的运行时间至多是与树的高度成正比，为 O（lgn）。（8）简单选

15、择排序设所排序序列的个数为。i 取 1,2,n-1,从所有 n-i+1 个记（R,Ri+1,Rn中找出排序码最小的，与第个交换。执行 n-1 趟 后就完成了序705630251510101556253070列的排序。在简单选择排序过程中，所需移动的次数比较少。最好情况下，即待排序初始状态就已经是正序排列了，则不需要移动。情况下，即待排序初始状态是按逆序排列的，则需要移动的次数最多为 3（n-1）。简单选择排序过程中需要进行的比较次数与初始状态下待排序的序列的排列情况无关。当i=1 时，需进行n-1 次比较；当i=2 时，需进行n-2 次比较；依次类推，共需要进行的比较次数是(n-1)+(n-2

16、)+2+1=n(n-1)/2，即进行比较操作的时间复杂度为 O(n2)。2.4 算法比较分析算法复杂度分为时间复杂度和空间复杂度。其作用： 时间复杂度是度量算法执行的时间长短；而空间复杂度是度量算法所需空间的大小。因此可以通过比较这几个算法的时间复杂度，来选择最适合的算法。这几种排序算法比较如图 2-4：图 2-4 算法比较分析2.5 程序流程图将所有的排序方法，打包成函数并设计实现相应的函数接口，方便在Main函数中调用。设计结构，实现排序算法，通过调用函数对测试数据进行排序，并输出结果。按照编程，实现相应的程序，程序流程图如图 2-5：开始调用直接排序算法调用折半排序算法调用希尔排序算法调

17、用起泡算法调用快速排序算法调用归并排序算法调用堆排序算法调用简单选择排序算法结束图 程序流程图调用pr 函数，输出结果调用排序函数构建表初始化2.6 测试程序说明程序测试：根据自己的程序，在主程序中设定相应的函数操作，通过函数接口调用相应的函数对自己建立的顺序表进行排序，并在屏幕显示相应的结果。#include#include / malloc()等#include / EOF(=Z 或 F6),NULL #define LQ(a,b) (a)=(b)void main()SqList l1,l2,l3,l4,l5,l7,l8,l9;/定义顺序表 i;for(i=0;iN;i+) / 给l1.

18、r 赋值l1.ri+1=di;l1.length=N;l9=l8=l7=l5=l4=l2=l3=l1;prf(排序前:n); prInsertSort(l1);(l1);prf(直接BInsertSort(l2);排序后:n); pr prf(折半排序:n);(l1);排序后:n);pr(l3);f(进行prdt3=5,3,1;Sort(l4,dt,3); prf(排序后:n );prS(l4);prf(简单选择排序后:n);SelectSort(l5);pr(l5);prf(归并排序后:n);prf(快速排序后:n);prf(冒泡排序后:n);MergeSort(l7);pr(l7);Qui

19、ckSort(l8);pr(l8);bubble_sort(l9);pr(l9);3 程序void InsertSort(SqList &L)/ 对顺序表L 作直接排序。i,j;for(i=2;i=L.length;+i)if LT(L.ri.key,L.ri-1.key) / ,需将L.ri有序子表为哨兵L.r0=L.ri; /for(j=i-1;LT(L.r0.key,L.rj.key);-j)后移L.rj+1=L.rj; /到正确位置L.rj+1=L.r0; /void BInsertSort(SqList &L) / 对顺序表 L 作折半排序。i,j,m,low,high;for(i=

20、2;i=L.length;+i)L.r0=L.ri; / 将L.ri暂存到 L.r0low=1;high=i-1;while(low=high+1;-j)后移L.rj+1=L.rj; /L.rhigh+1=L.r0; /void pr(SqList L)i;for(i=1;i=L.length;i+)prf(%d,%d),L.ri.key,L.ri.otherinfo);prf(n);void SInsert(SqList &L,dk) / 对顺序表 L 作一趟排序。i,j;for(i=dk+1;i0<(L.r0.key,L.rj.key);j-=dk)后移，查找位置L.rj+dk=L.r

21、j; /L.rj+dk=L.r0; /void SSort(SqList &L,dlta,t) / 按增量序列 dlta0.t-1对顺序表 L 作排序。k;for(k=0;kt;+k)Insert(L,dltak); / 一趟增量为 dltak的排序Sprf(第%d 趟排序结果: ,k+1);pr(L);SelectMinKey(SqList L,i) / 返回在 L.ri.L.length中 key 最小的的序号KeyType min;j,k;k=i; / 设第 i 个为最小min=L.ri.key;for(j=i+1;j=L.length;j+)if(L.rj.keymin) / 找到更小

22、的k=j;min=L.rj.key;return k;void SelectSort(SqList &L) / 对顺序表 L 作简单选择排序。i,j;RedType t;for(i=1;iL.length;+i) /选择第 i 小的，并交换到位j=SelectMinKey(L,i); / 在L.ri.L.length中选择 key 最小的if(i!=j) / 与第 i 个交换t=L.ri;L.ri=L.rj;L.rj=t;void Merge(RedType SR,RedType TR,i,m,n) / 将有序的 SRi.m和 SRm+1.n归并为有序的 TRi.nj,k,l;for(j=m+

23、1,k=i;i=m&j=n;+k) / 将 SR 中由小到大地并入 TRif LQ(SRi.key,SRj.key)TRk=SRi+;elseTRk=SRj+;if(i=m)for(l=0;l=m-i;l+)TRk+l=SRi+l; / 将剩余的 SRi.m到 TRif(j=n)for(l=0;l=n-j;l+)TRk+l=SRj+l; / 将剩余的 SRj.n到 TRvoid MSort(RedType SR,RedType TR1,s,t) / 将 SRs.t归并排序为 TR1s.t。m;RedType TR2MAXSIZE+1;if(s=t)TR1s=SRs;elsem=(s+t)/2;

24、 / 将 SRs.t平分为 SRs.m和 SRm+1.tMSort(SR,TR2,s,m); / 递归地将 SRs.m归并为有序的 TR2s.mMSort(SR,TR2,m+1,t); / 递归地将 SRm+1.t归并为有序的 TR2m+1.tMerge(TR2,TR1,s,m,t); / 将 TR2s.m和 TR2m+1.t归并到 TR1s.tvoid MergeSort(SqList &L) / 对顺序表 L 作归并排序。MSort(L.r,L.r,1,L.length);Partition(SqList &L,low,high) / 交换顺序表L 中子表 rlow.high的，枢轴到位，

25、并返回其/ 所在位置，此时在它之前（后）的均不大（小）于它。KeyTypvotkey;L.r0=L.rlow; / 用子表的第一个作枢轴pivotkey=L.rlow.key; / 枢轴关键字while(low high) / 从表的两端交替地向中间扫描while(low=pivotkey)-high;L.rlow=L.rhigh; / 将比枢轴小的移到while(lowhigh&L.rlow.key=pivotkey)+low;L.rhigh=L.rlow; / 将比枢轴大的移到高端L.rlow=L.r0; / 枢轴到位return low; / 返回枢轴位置void QSort(SqList &L,low,high) / 对顺序表 L 中的子序列 L.rlow.high作快速排序。算法 10.7pivotloc;if(lowhigh) / 长度大于 1pivotloc=Partition(L,low,high); / 将L.rlow.high一分为二QSort(L,low,pivotloc-1); / 对低子表递归排序，pivotloc 是枢轴位置QSort(L,pivotloc+1,high); / 对高子表递归排序void QuickSort