数据结构课程设计

1、需求分析。

1.1、选题要求。

对各种排序算法进行定量的性能分析。

1.2、选题的意义及背景。

排序是计算机程序设计中的一种重要操作。它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。

内部排序的方法很多，但是就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合在不同的环境下使用。如果按排序过程中依据的不同原则对内部排序方法进行分类，则大致可分为插入排序，交换排序，选择排序，归并排序和记数排序等五类。

此实验通过对起泡排序、直插排序、选择排序、快速排序、归并排序这几种内部排序算法进行比较，能使我们更好的掌握这些排序的基本思想及排序算法。通过该题目的设计过程，可以加深理解各种数据结构的逻辑结构、存储结构及相应上运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养我们的动手能力。

1.3、课程设计目标。

本课程设计对以下内部排序算法进行比较：起泡排序、直插排序、选择排序、快速排序、归并排序。

待排序表的元素关键字为整数，用不同的测试数据做测试比较。比较的指标为关键字的比较次数和关键字的移动次数。最后用图、**数据汇总数据，以便对这些内部排序算法进行性能分析。

2、概要设计。

2.1、原始数据。

用户输入记录的个数，数据由随机数产生器生成。

2.2、输出数据。

产生的随机数分别用起泡排序、直插排序、选择排序、快速排序、归并排序这些排序方法进行排序，输出关键字的比较次数和移动次数。

2.3、数据处理。

2.4、逻辑结构及物理结构。

以顺序表为存储结构（物理结构）

typedef struct

int key; /关键字。

elemtype;

typedef struct

elemtype *elem;

int length;//数据元素个数。

sqlist;

2.5、系统的模块划分及模块功能。

系统分为两个模块。

2.5.1主程序模块。

void main（）

2.5.2可排序表单元模块。

a．选择排序。

void selectsort(sqlist &l)

b.起泡排序。

void bubblesort(sqlist &l)

c.直接插入排序。

void insertsort(sqlist &l)

void beforesort()

void display(int m,int n)

d．快速排序。

int partition(sqlist &l,int low,int high)

void qsort(sqlist &l,int low,int high)

void quicksort(sqlist &l)

e．归并排序

void mergesort(sqlist &l)

3、详细分析。

1）选择排序。

基本思想：在待排序的一组数据元素中，选出最小的一个数据元素与第一个位置的数据元素交换；然后在剩下的数据元素当中再找最小的与第二个位置的数据元素交换，循环到只剩下最后一个数据元素为止。

2）起泡排序。

基本思想：相邻的两个元素进行比较，将小的调到前面，大的调到后面。

3）直接插入排序。

待排序的记录放在数组r[0…n-1]中排序过程中某一时刻，r被划分成两个子区间r[0…i-1] (有序和)r[i…n-1](无序)。直接插入的基本操作是将当前无序区的一个记录r[i]插入到有序区r[0…i-1]中适当的位置。

4）快速排序

基本思想：在待排序的数组的n个元素中取一个元素(一般取第一个)，将其移动到这样的位置：在其之前的元素的值都小于它，在其之后的元素都大于它，这样是一趟快速排序；然后对数组的两个部分进行同样的操作，直到每部分只有一个记录为止；总之，每趟使表的第一个元素放在适当位置，将表两分，再对两子表进行同样的递归划分，直至划分的子表长度为1！

5）归并排序。

基本思想：将两个或两个以上的有序表组成一个新的有序表。

4、调试分析。

1）刚开始进行调试时，有些排序方法不能实现，我就对不能实现的排序进行分析，对产生的语法错误进行了及时的改正，以至所有的排序算法能够顺利的实现。

2）考虑不周全，每种排序算法所使用的随机数并不相同，这样便使得得到的关键字的比较次数和移动次数不具有可比性。改后的程序便解决了这个问题。

3）从上面的显示可以看出，直插排序的移动次数为1（只有数据是正序的时候，才是为1），经检查程序存在问题。随机数在经过选择排序后，已经变为正序的数据，后面的排序方法是对以上正序数的排序。为此专门设置一个数组，存取随机数。

但是改后的程序出现了下面的状况。编译正确，执行不了。

4）上网查询执行不了的原因，网上是这样讲的：

windows子系统设置错误，提示： )wa5fzplw

: error lnk2001: unresolved external symbol _main *+oj(e+

4f{'{1]\

windows项目要使用windows子系统，而不是console, 可以这样设置： *y#/d+g

z !df-%3|

project] -settings] -选择"link"属性页， qo!

在project options中将/subsystem:console改成/subsystem:windows t`"y{

xn?{t*{

但是自己的机子的设置却改不了。网上有人建议用codeblocks这个程序进行执行，安装这个程序，编译执行后，得到下面的结果。有效的解决了上面的问题。

5）在老师的指导下，找到了无法执行的原因。主函数定义错误。

将void addlist(sqlist &l)改为。

void main()

sqlist l;问题解决。

5、用户手册。

1）本程序的运行环境为dos操作系统。

2）进入演示程序后，即显示文本方式的用户界面。

3）演示程序以人机对话的形式进行。只要输入记录的个数，程序便产生50组随机数，显示通过选择排序、起泡排序、直插排序、快速排序、归并排序对随机数进行排序时，关键字的比较次数和移动次数的平均值，从而直观的比较各种内部排序算法的优劣。

6、测试结果。

6.1测试用例及选择原因。

记录数分别输入，之所以想用这三个记录数测试，是想测试用选择排序、起泡排序、直插排序、快速排序、归并排序这五种排序方法，在记录较小和较大时，关键字的比较次数和移动次数，用以直观的分析它们的性能。

6.2测试结果。

测试的结果如下表：（注：此数据为50组数据的平均值）

6.3结论。

由上表可以得出：

1）选择排序的比较次数较少且为定值，但由于它在排序过程中要先查询、再安置，所以性能上不够稳定。

2）起泡排序的比较次数和移动次数在这五种排序方式中最多，所以起泡排序的排序性能相对于其他排序要低好多。

3）直插排序的比较次数和移动次数相比较于其他几种排序次数要少，所以效率相比较而言较高，性能较高，且较稳定。从整体上来讲性能较其他几种排序较高。

4）快速排序在这几种排序当中从比较次数较少的，移动次数多于选择排序但低于其他三种排序，且其过程是先定一个基准，大小各放一边，再分别对两边多次操作，达到整体有序，所以性能上来看是最快最好的，但是不够稳定。

5）归并排序的比较次数和移动次数相当，且较小。在记录数较大时，关键字的比较次数和移动次数较少，在使用它对两个己有序的序列归并，将有无比的优势。

由此可见上述内部排序方法，每一种方法都有各自的优缺点，适合在不同的环境下使用。通过这个结论，我们可以找到一些内部排序方法选择的规则。

规则如下：1）当n较小时：可采用直接插入排序和直接选择排序。

2）当记录规模小时，可选择直接插入排序；当记录规模大时，可选择直接选择排序，因为直接插入排序所需的记录移动操作比直接选择排序多。

3）当记录基本有序时：可采用直接插入排序和冒泡排序。

4）当n较大时：可采用快速排序和归并排序。

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了