数据结构课程设计

《数据结构课程设计》由会员分享，可在线阅读，更多相关《数据结构课程设计（12页珍藏版）》请在金锄头文库上搜索。

1、“数据结构”课程设计报告（内部排序算法性能分析）学生姓名：指导教师：所在系：所学专业：年 级：目录1 、需求分析 - 1 -、选题要求 - 1 -、选题的意义及背景 - 1-、课程设计目标 - 1 -2、概要设计 - 2 -、原始数据 - 2 -、输出数据 - 2 -、数据处理 - 2 -、逻辑结构及物理结构 - 3 - 、系统的模块划分及模块功能 - 4 - 主程序模块 错误 !未定义书签。 可排序表单元模块 错误 !未定义书签。、模块的测试数据 - 5 -3、详细分析 - 5 -4 、调试分析 - 6 -5、用户手册 - 7 -6、测试结果 - 7 - 测试用例及选择原因 错误 !未定义书

2、签。 测试结果 错误 ! 未定义书签。7、总结- 9 -8、参考文献 - 10 -9 、小组人员分工 - 10 -致谢- 10 -1 、需求分析1.1 、选题要求对各种排序算法进行定量的性能分析。1.2 、选题的意义及背景排序是计算机程序设计中的一种重要操作。 它的功能是将一个数据元素的任 意序列，重新排列成一个按关键字有序的序列。内部排序的方法很多， 但是就其全面性能而言， 很难提出一种被认为是最好 的方法， 每一种方法都有各自的优缺点， 适合在不同的环境下使用。 如果按排序 过程中依据的不同原则对内部排序方法进行分类， 则大致可分为插入排序， 交换 排序，选择排序，归并排序和记数排序等五类

3、。此实验通过对起泡排序、直插排序、选择排序、快速排序、归并排序这几种 内部排序算法进行比较，能使我们更好的掌握这些排序的基本思想及排序算法。 通过该题目的设计过程， 可以加深理解各种数据结构的逻辑结构、 存储结构及相 应上运算的实现， 进一步理解和熟练掌握课本中所学的各种数据结构， 学会如何 把学到的知识用于解决实际问题，培养我们的动手能力。1.3 、课程设计目标本课程设计对以下内部排序算法进行比较： 起泡排序、 直插排序、选择排序、 快速排序、归并排序。待排序表的元素关键字为整数， 用不同的测试数据做测试比较。 比较的指标 为关键字的比较次数和关键字的移动次数。 最后用图、 表格数据汇总数据

4、， 以便 对这些内部排序算法进行性能分析。2、概要设计2.1 、原始数据 用户输入记录的个数，数据由随机数产生器生成。2.2 、输出数据产生的随机数分别用起泡排序、直插排序、选择排序、快速排序、归并排序 这些排序方法进行排序，输出关键字的比较次数和移动次数。2.3 、数据处理主程序循环50次产生1组随机数将随机数保存在数组中记录关键字的比较 次数和移动次数输出关键字的比较次 数、移动次数的平均值2.4、逻辑结构及物理结构以顺序表为存储结构（物理结构）typedef structint key; /关键字ElemType;typedef structElemType *elem;in t le

5、ngth;/ 数据元素个数SqList;void mai n()A 选择排序void SelectSort(SqList &L)void BubbleSort(SqList &L)void In sertSort(SqList &L)void BeforeSort()void display(i nt m,i nt n)D 快速排序int Partition(SqList &L,int low,int high) void QSort(SqList & L,i nt low,i nt high) void QuickSort(SqList &L)E.归并排序void MergeSort(SqL

6、ist &L) 2.6 、模块的测试数据以关键字的数目分别为 10 ，100，1000 为例,作为测试数据。3、详细分析（1）选择排序基本思想： 在待排序的一组数据元素中， 选出最小的一个数据元素与第一个 位置的数据元素交换； 然后在剩下的数据元素当中再找最小的与第二个位置的数 据元素交换，循环到只剩下最后一个数据元素为止。（2）起泡排序基本思想：相邻的两个元素进行比较，将小的调到前面，大的调到后面。（ 3）直接插入排序待排序的记录放在数组R0n-1中排序过程中某一时刻，R被划分成两个子 区间R0/（有序和）Ri n-1（无序）。直接插入的基本操作是将当前无序区的 一个记录Ri插入到有序区R0

7、/中适当的位置（ 4） 快速排序基本思想：在待排序的数组的n个元素中取一个元素（一般取第一个），将其移动到这样的位置：在其之前的元素的值都小于它，在其之后的元素都大于它， 这样是一趟快速排序； 然后对数组的两个部分进行同样的操作， 直到每部分只有 一个记录为止；总之，每趟使表的第一个元素放在适当位置，将表两分，再对两 子表进行同样的递归划分，直至划分的子表长度为 1！（5）归并排序基本思想：将两个或两个以上的有序表组成一个新的有序表4、调试分析（1）刚开始进行调试时，有些排序方法不能实现，我就对不能实现的排序 进行分析， 对产生的语法错误进行了及时的改正， 以至所有的排序算法能够顺利 的实现。

8、（2）考虑不周全，每种排序算法所使用的随机数并不相同，这样便使得得 到的关键字的比较次数和移动次数不具有可比性。改后的程序便解决了这个问 题。（3）从上面的显示可以看出，直插排序的移动次数为1 （只有数据是正序的时候，才是为 1 ），经检查程序存在问题。随机数在经过选择排序后， 已经变为 正序的数据，后面的排序方法是对以上正序数的排序。为此专门设置一个数组， 存取随机数。但是改后的程序出现了下面的状况。编译正确，执行不了。（4）上网查询执行不了的原因，网上是这样讲的：Windows 子系统设置错误 , 提示: ）WA5FzPLwlibcmtd.lib（crt0.obj） : error LNK

9、2001: unresolved external symbol_main *+oJ（e+4f1Windows 项目要使用 Windows 子系统 , 而不是 Console, 可以这样设置 :y#/D+gz !DF-%3|Project - Settings- 选择Link属性页,Qo!在 Project Opti ons 中将 /subsystems on sole 改成 /subsystems in dowsTH.kYXn ?t*但是自己的机子的设置却改不了。网上有人建议用CodeBlocks这个程序进行执行，安装这个程序，编译执行后，得到下面的结果。有效的解决了上面的问 题。（5 ）在

10、老师的指导下，找到了无法执行的原因。主函数定义错误。将 void addlist（SqList &L） 改为Void mai n（） SqList L;问题解决。5、用户手册（1）本程序的运行环境为DOS操作系统（2 ）进入演示程序后，即显示文本方式的用户界面。（3）演示程序以人机对话的形式进行。只要输入记录的个数，程序便产生 50组随机数，显示通过选择排序、起泡排序、直插排序、快速排序、归并排序 对随机数进行排序时，关键字的比较次数和移动次数的平均值，从而直观的比较各种内部排序算法的优劣。6、测试结果记录数分别输入10、100、1000 ,之所以想用这三个记录数测试，是想测 试用选择排序、起

11、泡排序、直插排序、快速排序、归并排序这五种排序方法，在 记录较小和较大时，关键字的比较次数和移动次数，用以直观的分析它们的性能。测试的结果如下表：（注：此数据为50组数据的平均值）记录数关键字选择排序起泡排序直插排序快速排序归并排序的个数10比较次数361894036移动次数1861218238100比较次数4851198099624688移动次数281739156432740941000比较次数498584899874移动次数297474959175354765432483关键字选择排序起泡排序直插排序快速排序归并排序记录数比较次数较少最多最少较少较少较小移动次数较少最多较少较少较少比较次数

12、较少最多最少较少较少较大移动次数最少最多较多较少较少由上表可以得出：(1) 选择排序的比较次数较少且为定值，但由于它在排序过程中要先查询、再安置，所以性能上不够稳定。(2) 起泡排序的比较次数和移动次数在这五种排序方式中最多，所以起泡排序的排序性能相对于其他排序要低好多 （3）直插排序的比较次数和移动次数相比较于其他几种排序次数要少，所以效 率相比较而言较高， 性能较高，且较稳定。 从整体上来讲性能较其他几种排序较 高。（4）快速排序在这几种排序当中从比较次数较少的，移动次数多于选择排序但 低于其他三种排序， 且其过程是先定一个基准， 大小各放一边， 再分别对两边多 次操作，达到整体有序，所以

13、性能上来看是最快最好的，但是不够稳定。（5）归并排序的比较次数和移动次数相当，且较小。在记录数较大时，关键字 的比较次数和移动次数较少， 在使用它对两个己有序的序列归并， 将有无比的优 势。由此可见上述内部排序方法， 每一种方法都有各自的优缺点， 适合在不同的环境 下使用。通过这个结论，我们可以找到一些内部排序方法选择的规则。 规则如下：（ 1）当 n 较小时：可采用直接插入排序和直接选择排序。（ 2）当记录规模小时，可选择直接插入排序；当记录规模大时，可选择直接选 择排序，因为直接插入排序所需的记录移动操作比直接选择排序多。（3）当记录基本有序时：可采用直接插入排序和冒泡排序。（ 4）当 n

14、 较大时：可采用快速排序和归并排序。7、总结 在这一周的数据结构课程设计中 ,我们的题目是 :内部排序算法性能分析 ,通 过该课程设计 ,我们加深了对内部排序算法的理解 ,对内部排序算法的基本运算的 实现有所掌握 ,对课本中所学的各种数据结构进一步理解和掌握 ,学会了如何把学到的知识用于解决实际问题 ,锻炼了自己动手的能力一个人的力量是渺小的， 在课程设计中我们学会了团结协作。 在课程设计时 遇到了很多的问题， 大家便一起讨论解决的方法， 锻炼了我们的协作能力。 为今 后在学习工作中能更好的发展打下了坚实的基础。一周的课程设计很短暂， 但其间的内容是很充实的， 在其中我们学习到了很 多平时书本中无法学到的东西， 积累了经验， 锻炼了自己分析问题、 解决问题的 能力，并学会了如何将所学的各课知识融会，组织，来配合学习，这一周让我们 受益匪浅。8 、参考文献1. 严蔚敏，吴伟民， 数据结构（ C 语言版），清华大学出版社 ,20092. 严蔚敏，吴伟民， 数据结构题集（ C 语言版），清华大学出版社 ,20099、小组人员分工组长：王乐组员：韩守飞、时良荣分工：王 乐：主程序、归并排序、报告撰