课程设计数据结构.docx

课程设计数据结构.docx

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

课程设计数据结构

数据结构课程设计

题目：

排序综合

班级：

统计1201

姓名：

唐浩彭

学号：

201205505

完成日期：

2014/7/10

1、需求分析

1.1任务与分析

利用随机函数产生N个随机整数（20000以上），对这些数据使用多种方法进行排序。

基本要求：

1、至少采用五种方法（至少包括希尔排序、快速排序、堆排序）实现上述问题求解；

2、统计每一种方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法；

3、统计每种算法所用的比较次数和交换次数，最后列表显示。

根据所学内容，本程序列举了直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序六种排序方法。

1.2模块的划分

1.2.1输入模块

利用随机函数产生N个随机整数（20000以上），产生的数据个数由用户自己输入。

1.2.2输出模块

根据要求列表输出每一种算法所花费的时间、所用的比较次数和交换次数。

1.2.3程序功能

本程序是一个关于排序的综合系统，可以利用所写程序熟练掌握六种排序算法，找出时间性能最好的两种算法，输出每种算法所用的比较次数和交换次数，横向对比六种算法的优缺点。

1.2.4测试数据

2、概要设计

2.1抽象数据类型定义

SORTADT

{

数据对象：

N=随机产生的数据元素；

基本操作：

voidInsertSort（int*r,int&compare,int&exchange）；

voidShellSort（int*r,int&compare,int&exchange）；

voidBubbleSort（int*r,int&compare,int&exchange）；

intPartition（int*r,intfirst,intend,int&compare,int&exchange）；

voidQuickSort（int*r,int&compare,int&exchange）；

voidSelectSort（int*r,intfirst,intend,int&compare,int&exchange）；

voidSift（int*r,intk,intm,int&compare,int&exchange）；

voidHeapSort（int*r,int&compare,int&exchange）；

}

ADTSORT

2.2主程序流程

（1）先构造直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序六种排序方法的算法实现；

（2）再构造随机函数的算法，利用随机函数产生N个随机整数（20000以上）。

（3）最后调用插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序六种排序方法的算法，并依次输出每一种算法所花费的时间、所用的比较次数和交换次数。

2.3函数调用关系

3、详细设计

3.1模块的分工

根据程序的要求，我主要设计希尔排序、快速排序、堆排序的算法，并构造随机函数，利用随机函数产生N个随机整数（20000以上）。

3.1.1希尔排序

（1）基本思想

先将整个待排序记录序列分割成若干个子序列，在子序列内分别进行直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。

（2）具体步骤

取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。

所有距离为d1的倍数的记录放在同一个组中。

先在各组内进行直接插入排序；然后，取第二个增量d2

3.1.2快速排序

（1）基本思想

首先选一个轴值（即比较的基准），将待排序记录序列分割成独立的两部分，左侧记录的关键码均小于或等于轴值，右侧记录的关键码均大于或等于轴值，然后分别对这两部分重复上述过程，直到整个序列有序。

（2）一趟快速排序的算法

1）设置两个变量i、j，排序开始的时候：

i=0，j=N-1；

2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；

3）从j开始向前搜索，即由后开始向前搜索（j--），找到第一个小于key的值A[j]，将A[j]赋给A[i]；

4）从i开始向后搜索，即由前开始向后搜索（i++），找到第一个大于key的A[i]，将A[i]赋给A[j]；

5）重复第3、4步，直到i=j；（3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。

找到符合条件的值，进行交换的时候i，j指针位置不变。

另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

3.1.3堆排序

（1）基本思想

首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者即堆顶记录，然后将它从堆中移走（通常将堆顶记录和堆中最后一个记录交换），并将剩余的记录再调整成堆，这样又找出了次大的记录，以此类推，直到堆中只有一个记录为止。

（2）大根堆排序算法的具体步骤：

①初始化操作：

将R[1..n]构造为初始堆；

②每一趟排序的基本操作：

将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。

3.2算法的设计

3.2.1希尔排序

voidShellSort（intr[],intn）

{

for（d=n/2;d>=1;d=d/2）

{

for（i=d+1;i<=n;i++）

{

r[0]=r[i];

for（intj=i-d;j>0&&r[0]

r[j+d]=r[j];

r[j+d]=r[0];

}

}

}

3.2.2快速排序

（1）一次快速排序的伪代码

1、将i和j分别指向待排序区域的最左侧记录和最右侧记录的位置；

2、重复下述过程，直到i=j

2.1右侧扫描，直到记录j的关键码小于基准记录的关键码；

2.2如果i

2.3左侧扫描，直到记录i的关键码大于基准记录的关键码；

2.4如果i

3、退出循环，说明i和j指向了基准记录所在位置，返回该位置；

（2）快速排序算法

voidQuickSort（intr[],intfirst,intend）

{

if（first

{

pivot=Partition（r,first,end）;

QuickSort（r,first,pivot-1）;

QuickSort（r,pivot+1,end）;

}

}

3.2.3堆排序

（1）筛选法调整堆的算法伪代码

1.设置i和j，分别指向当前要筛选的结点和要筛选结点的左孩子；

2.若结点i已是叶子，则筛选完毕；否则，比较要筛选结点的左右孩子结点（如果有右孩子），并将j指向关键码较大的结点；

3.将要筛选结点i的关键码与j所指向的结点的关键码进行比较

3.1如果结点i的关键码大，则完全二叉树已经是堆，筛选完毕；

3.2否则将r[i]与r[j]交换；令i=j，转步骤2继续进行筛选；

（2）堆排序的程序

voidHeapSort（intr[],intn）

{

for（inti=n/2;i>=1;i--）

Sift（r,i,n）;

for（i=1;i

{

r[1]←→r[n-i+1];

Sift（r,1,n-i）;

}

}

4、调试分析

4.1遇到的问题

根据程序调试过程中出现的程序错误和警告，改正程序中的语法和语义错误，使程序能够正常地运行，再根据测试分析算法的正确与否调试程序中的各种排序算法，使得每种排序算法都能够正确地执行操作。

在刚开始编写程序的时候，本来我们打算用顺序表来构造一个结构体，后来在编写的时候发现有些难度，所以就决定写最直接、最简单的程序，依次写出了六种排序算法的源程序，再依次调用六种排序算法。

在调用的时候，有时候会出现某些变量没有定义的错误，我们会在相应的位置找到该错误，并添加一些必要的变量类型，最后得以解决。

4.2算法的分析以及改进设想

由于本程序没有选择顺序表或者链表来进行构造，所以程序所花费的时间要长一些，在最后调用的时候，也没有设计一个可以选择算法的一个界面，所以会复杂一些。

另外在设计的时候由于时间原因，我们并没有设计一个主界面，通过选择不同的排序方法，输出每种排序方法的花费时间、比较次数、交换次数。

所以在后期的设计中，我们会建立一个主界面，把六种排序方法依次通过数字键调用，真正做到智能化，让用户真正体会到各种排序方法的优缺点。

4.3经验和体会

在这次课程设计的学习中，我学到了很多知识，也对本专业的前景有了更加深入的体会。

在课程设计中，我几乎是独立完成了直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序六种排序方法的算法实现，同时我也实现了随机数的产生。

另外在算法完成的过程中，我们也在网上查了大量的资料，看了大量的书籍，请教了一些班上学得好的同学。

在程序设计的过程中，我们也遇到了很多问题，比如调试的时候出现各种各样的错误，我们就会重新改进程序；在设计的过程中，我们也互相讨论了好多次，虽然最后做出的程序仍有不足之处，但我们已经尽力了，只能说我们实力有限。

另外由于种种原因，程序没有实现智能化，不能大面积地推广，以后有时间我们会进一步地改进的。

通过几天的编程，我熟练地掌握了C语言的文件读写操作，掌握了每种排序算法的基本思想，学会了编程的一般步骤：

思考问题、写出解决方案、写出伪代码、调试程序。

另外我也深刻地认识到平时学过的东西要实践化，要不断地在实践中复习学过的知识，更让我认识到了知识的重要性。

5、用户使用说明

1、本程序可以在VC++6.0的环境下进行；

2、在VC中创建一个工程，将源程序复制到.cpp中，编译连接就可以运行程序；

3、由于本程序是随机产生N个正整数，所以不用输入数据；

4、选择编译、运行以后会出现运行结果，用户可以直接地进行观察并找出最好的两种排序方法。

6、测试结果

不需要人工输入任何测试数据，由系统随机产生数据，产生的个数由用户决定：

从运行结果可以很清楚的看出，快速排序和堆排序所用的时间最少，比较的次数和交换的次数依次为291604、130938和253273、249328。

7、参考文献

[1]王红梅，胡明，王涛.数据结构（C++版）.北京：

清华大学出版社，2005.7

[2]朱立华等.C语言程序设计.北京：

人民邮电出版社，2009

[3]严蔚敏等.数据结构（C语言版）.北京：

清华大学出版社，2009