数据结构实验报告.docx
《数据结构实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告.docx（27页珍藏版）》请在冰点文库上搜索。
数据结构实验报告
数据结构实验报告
武汉理工大学《应用数据结构》课程设计说明书
学号:
内部排序算法的比较题目
学院
专业
班级
姓名
指导教师
20100712年月日
武汉理工大学《应用数据结构》课程设计说明书
课程设计任务书
学生姓名:
专业班级:
指导教师:
工作单位:
题目:
内部排序算法的比较
初始条件:
在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。
试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。
要求完成的主要任务:
（包括课程设计工作量及其技术要求、说明书撰写等具体要求）
（l）对以下6种常用的内部排序算法进行比较:
起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。
（2）待排序表的表长不小于100000;其中的数据要用伪随机数程序产生;至少要用5组不同的输入数据作比较;比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。
（3）最后要对结果作简单分析，包括对各组数据得出结果波动大小的解释。
时间安排:
序号设计内容所用时间
1问题分析和任务定义0.5天
2数据类型和系统设计0.5天
3编码实现和静态检查3天
4上机准备和上机调试2天
5总结和整理设计报告1天
合计7天
指导教师签名:
2010年07月05日
系主任（或责任教师）签名:
2010年07月05日
武汉理工大学《应用数据结构》课程设计说明书
内部排序算法的比较1.需求分析
1.1相关原理:
（1）直接插入排序（StraightInsertionSort）是一种最简单的排序方法，它的基本操作是将一个纪录插入到已排好序的有序表中，从而得到一个新的、纪录数增1的有序表;
（2）希尔排序（Shell’ssort）又称“缩小增量排序”，它也是一种属插入排序类的方法，但在时间效率上较前述排序方法有较大改进。
它的基本思想是:
先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
希尔排序的一个特点是:
子序列的构成不是简单的“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列;
（3）冒泡排序（Bubblesort）的过程很简单。
首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。
依次类推，直至第n-1个记录和第n个记录的关键字进行比较为止。
上述过程称做第一趟冒泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上。
然后进行第二趟冒泡排序，对前n-1个记录进行同样操作，其结果是使关键字次大的记录被安置到第n-1个记录的位置上;
（4）快速排序（Quicksort）是对冒泡排序的一种改进。
它的基本思想是，通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
一趟快速排序的具体做法是:
附设两个指针low和high，它们的初值分别为low和high，设枢轴记录的关键字为pivotkey，则首先从high所指位置起向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录交换，重复这两步直至low=high为止;
（5）选择排序（Selectionsort）的基本思想是:
每一趟在n-i+1（i=1,2,…,n-1）个记录中选取关键字最小的记录作为有序序列中的第i个记录。
其中最简单的是简单选择排序。
一趟简单选择排序的操作为:
通过n-i次的关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换之;
（6）堆排序（HeapSort）堆排序是一种树形选择排序，是对直接选择排序的有效改进。
堆顶为根，其它为左子树、右子树。
初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储顺序，使之成为一个堆，这时堆的根节点的数最大。
然后将根节点与堆的最后一个节点交换。
然后对前面（n-1）个数重新调整使之成为堆。
依此类推，直到只
武汉理工大学《应用数据结构》课程设计说明书
有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。
从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。
所以堆排序有两个函数组成。
一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。
1.2基本要求:
通过课程设计，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。
由于程序中所需的数据都是有函数随机生成的整形数，不需要用户自己输入，用户只需要对演示程序中的一些提示做一些必要的选择以便于程序的执行。
程序输出的是对六种排序做的一些比较，即输出六种排序各排序过程中所比较的数据的个数，交换的数据的次数，和排序完成所用的时间。
六种排序依次在计算机终端上显示，便于用户观察。
输入值的范围等价于程序中随机生成的数据的个数，即待排序表的表长不小于100，至少要用5组不同的输入数据体比较，比较的指标为:
有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次的移动），在该程序中，随机生成的数据个数被初始化为了10000，数据越大就越容易比较。
1.3任务功能:
亲自动手结合数据机构相关知识，利用C语言设计、实现内部排序算法的性能分析系统:
通过用户在自己键入的n的数目，用伪随机数产生n个随机整数，对这些数进行如下六种方法进行排序:
起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序，并对这些排序做比较，在屏幕上输出每种排序方法所比较的次数，交换的次数，和用掉的时间。
并规定此程序具有如下功能和特性:
规范性:
规定用户输入的数据是任意的正整数n，程序输出的比较次数、移动次数和所用时间都是以正整数的形式表达;
任意性:
系统通过伪随机程序产生的任意随机整数，分别用不同的排序方法对其进行升序排序，给出每种方法的比较次数、移动次数或所用时间;
友好性:
界面要友好，输入有提示，尽量展示人性化;
可读性:
源程序代码清晰、有层次;
健壮性:
用户输入非法数据时，系统要及时给出警告信息;
按要求画出程序流程图、编写程序代码、运行测试。
武汉理工大学《应用数据结构》课程设计说明书
2.概要设计
2.1程序所需的抽象数据类型的定义:
typedefintBOOL;//说明BOOL是int的别名
typedefstructStudentData
{
intnum;//存放关键字
}Data;
typedefstructLinkList
{
intLength;//数组长度
DataRecord[MAXSIZE];//用数组存放所有的随机数
}LinkList
intRandArray[MAXSIZE];//定义长度为MAXSIZE的随机数组
voidRandomNum（）//随机生成函数
voidInitLinkList（LinkList*L）//初始化链表
BOOLLT（inti,intj,int*CmpNum）//比较i和j的大小
voidDisplay（LinkList*L）//显示输出函数
voidShellSort（LinkList*L,intdlta[],intt,int*CmpNum,int*ChgNum）
//希尔排序
voidQuickSort（LinkList*L,int*CmpNum,int*ChgNum）
//快速排序
voidHeapSort（LinkList*L,int*CmpNum,int*ChgNum）
//堆排序
voidBubbleSort（LinkList*L,int*CmpNum,int*ChgNum）
//冒泡排序
voidSelSort（LinkList*L,int*CmpNum,int*ChgNum）
//选择排序
voidCompare（LinkList*L,int*CmpNum,int*ChgNum）
//比较所有排序
武汉理工大学《应用数据结构》课程设计说明书
2.2主程序的流程图为:
开始界面
随机函数产生随机数
Compare比较各类排序
直希冒快选接堆尔泡速择插排排排排排入序序序序序排序
比较各排序
输出数据
结束
图2-2程序流程图
武汉理工大学《应用数据结构》课程设计说明书
2.3各程序模块之间的层次（调用）关系:
主函数main（）
setInitLinkShowCompa-Display
List（Linthere定义或显示kList*L）menu初始化比较六输出
变量初始化显示种排序
链表主界面
图2-3-1主程序功能模块图
内部排序算法的比较
rand-Setli-ShellQuickHeapBubb-SelCom-
omnunklistsortSortSortleSortSortpare
mbers
初始化希尔快速堆冒泡选择比较
排序排序随机生链表排序排排序所有
排序成数据序
图2-3-2外部功能模块调用关系图
武汉理工大学《应用数据结构》课程设计说明书3.详细设计
3.1主程序的伪码算法:
begin//算法开始
{
intselect等于0;
intdlta为数组元素为3的一维数组;
intIndata为数组元素为1的一维数组;
intCmpNum[6],ChgNum[6];//CnpNum数组时比较次数，ChgNum是交换次数
intSpendTime等于0;
//intTempTime;
定义线性链表L;
初始化线性链表L;
memset（CmpNum,0,sizeof（CmpNum））;
memset（ChgNum,0,sizeof（ChgNum））;
输出“******************************************”
另起一行输出“数据结构课程设计”
另起一行输出“——内部排序算法的比较”
另起一行输出“Madeby刘雅囡2010.07.08”
另起一行输出“Plesepressentertocontinue...”
另起一行输出“******************************************”
getchar（）;
system（"cls.exe"）;
另起一行输出“正在计算，请稍等”
Compare（从线性链表取值,比较次数,交换次数）;//比较所有排序
输出所有排列
另起一行输出“比较结束,请按回车键!
”
getchar（）;
}//程序结束
武汉理工大学《应用数据结构》课程设计说明书3.2其他模块部分伪代码:
typedefintBOOL;//定义标识符关键字BOOL别名为inttypedefstructStudentData//记录数据类型{
intnum;//定义关键字类型}Data;//排序的记录数据类型定义typedefstructLinkList//记录线性表{
intLength;//定义表长
DataRecord[MAXSIZE];//表长记录最大值}LinkList;//排序的记录线性表类型定义intRandArray[MAXSIZE];//定义随机数组类型及最大值/******************随机生成函数********************/voidRandomNum（）
{
inti;
srand（（int）time（NULL））;//用伪随机数程序产生伪随机数
for（i=0;i小于MAXSIZE;i++）
RandArray[i]<=（int）rand（）;
返回;
}
/*****************初始化链表**********************/voidInitLinkList（LinkList*L）//初始化链表
{
inti;
memset（L,0,sizeof（LinkList））;
RandomNum（）;
for（i=0;i小于L->Record[i].num<=RandArray[i];
L->Length<=i;
}
BOOLLT（inti,intj,int*CmpNum）{
（*CmpNum）++;
若i否则返回FALSE;
}
武汉理工大学《应用数据结构》课程设计说明书voidDisplay（LinkList*L）{
FILE*f;//定义一个文件指针f
inti;
若打开文件的指令不为空则//通过文件指针f打开文件为条件判断
{//是否应该打开文件
输出“can'topenfile”;
exit（0）;
}
for（i=0;i小于L->Length;i++）
fprintf（f,"%d\n",L->Record[i].num）;
通过文件指针f关闭文件;
}
3.3函数的调用关系图:
主函数main（）
生成随机数srand（）
InsertShellQuickHeapBubb-Sel
SortSortSortSortleSortSort
插入希尔快速堆冒泡选择
排序排序排序排序排排序
序
InitLinkListRandomNumLTDisplay
初始化链表产生随机数比较大小显示结果
ChushihualiaChushihualiaChushihualiaChushihualia
nbiaonbiaonbiaonbiao图3-3函数的调用关系图
武汉理工大学《应用数据结构》课程设计说明书
4.调试分析
4.1调试过程中遇到的问题及经验体会:
在本次程序的编写和调试过程中，我曾多次修改代码，并根据调试显示的界面一次次调整代码。
在调试成功之前，我的程序因为3个错误而无法运行，在经过完整并且仔细的检查后，发现3处错误分别是没有定义变量就直接套用、忘记加指针符号、忘记在嵌套语句后加大括号，这些看似不显眼的小问题却导致整个程序无法运行，所以我认为在编程过程中要及其严谨，尽量少犯或避免犯语法错误，保证代码的完整性。
4.2算法的时空分析:
1.稳定性比较:
插入排序、冒泡排序、简单选择排序及其他线形排序是稳定的;
希尔排序、快速排序、堆排序是不稳定的。
2.时间复杂性比较:
2插入排序、冒泡排序、选择排序的时间复杂性为O（n）;
其它非线形排序的时间复杂性为O（nlogn）;2
线形排序的时间复杂性为O（n）。
3.辅助空间的比较:
线形排序的辅助空间为O（n），其它排序的辅助空间为O
（1）。
4.其它比较:
插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。
反而在这种情况下，快速排序反而慢了:
当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序;
当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。
当n较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下，宜用归并排序。
当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。
5.用户使用说明
（1）用VC6.0打开D:
\VC6\下的“内部排序算法的比较.c”程序运行代码，或者打开
武汉理工大学《应用数据结构》课程设计说明书
D:
\VC6\Debug文件夹下的“内部排序算法的比较.exe”可执行文件，进入如下界面;
（2）按照打开主界面的要求按回车键继续，进入如下界面;
（3）等待计算结果，出现如下界面;
武汉理工大学《应用数据结构》课程设计说明书
（4）按回车键结束，关闭程序
6.测试结果
测试结果及其分析:
通过本次程序的运行，得到数据:
插入排序:
比较的次数为25114496，交换的次数为25094525，花费的时间为1203ms;希尔排序:
比较的次数为3834939，交换的次数为
武汉理工大学《应用数据结构》课程设计说明书
3782098，花费的时间为187ms;快速排序:
比较的次数为153398，交换的次数为62804，花费的时间为0ms;堆排序:
比较的次数为235273，交换的次数为124235，花费的时间为16ms;冒泡排序:
比较的次数为49995000，交换的次数为27537172，花费的时间为2969ms;选择排序:
比较的次数为50005000，交换的次数为9988，花费的时间为1656ms。
算法效率是依据算法执行的时间来看的，从上面的数据来看，虽然插入排序的算法简洁，容易实现，但是从它执行的时间1203ms来看它的效率并不是很高，而且比较次数和交换次数都比较多，在这六种排序中效率是很底的;希尔排序的时间复杂度较直接排序低，在六种内部排序中效率居中;分析冒泡排序的效率，容易看出，若初始序列为“正序”序列，则只进行一趟排序，在排序过程中进行n-1次关键字的比较，反之，则需进行n-1趟排序，
2总的时间复杂度为O（n），在该程序中，冒泡排序所花费的时间为4360，是所有排序中花费最多的，可见效率是很底的。
快速排序是对冒泡排序的一种改进，它所用的时间几乎为0，交换的比较的次数都比较少;堆排序仅次于快速排序，花费的时间只有16ms。
由以上讨论可知，从时间上看，快速排序的平均性能都优于其他5种排序。
算法时间复杂度分析如下:
1、直接插入排序:
当文件的初始状态不同时，直接插入排序所耗费的时间是有很大差异的。
最好情况是文件初态为正序，此时算法的时间复杂度为O（n），最坏情况是文件初
22态为反序，相应的时间复杂度为O（n），算法的平均时间复杂度是O（n）;
22、选择排序是不稳定的，算法复杂度为O（n）;
3、快速排序是不稳定的主体算法时间运算量约O（logn），划分子区函数运算量约2
2O（n），所以总的时间复杂度为O（nlogn），它显然优于冒泡排序O（n）;2
1.251.254、希尔排序是不稳定的，算法复杂度是n~1.6*n;
25、冒泡排序是稳定的，时间复杂度为O（n）;
6、堆排序是不稳定的。
对各种表长和测试组数进行了测试，程序运行正常。
分析实测得到的数值，6种排序算法的特点小结如下:
武汉理工大学《应用数据结构》课程设计说明书
测试插入排序希尔排序快速排序堆排序冒泡排序选择排序
最多
第三多少少稍多第二多越乱（逆）比较次越乱（逆）乱否差异乱否差异乱否差异与乱否无越多数越多小小很小关越乱（逆）
越多
第二多约为快速第二少稍多最多最少移动次越乱（逆）排序的两乱否差异乱否差异越乱（逆）正和逆序数越多倍较小很小越多少
（1）若n较小（如n?
50），可采用直接插入或直接选择排序。
当记录规模较小时，直接插入排序较好;否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜;
（2）若文件初始状态基本有序（指正序），则应选用直接插人、冒泡或随机的快速排序为宜;
（3）若n较大，则应采用时间复杂度为O（nlgn）的排序方法:
快速排序、堆排序或归并排序;
快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短;堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。
这两种排序都是不稳定的。
参考文献:
[1]谭浩强.C程序设计（第二版）.北京:
清华大学出版社，2000
武汉理工大学《应用数据结构》课程设计说明书
[2]谭浩强.C程序设计试题汇编.北京:
清华大学出版社，2000[3]谭浩强.C程序设计题解与上机指导（第二版）.北京:
清华大学出版社，2000[4]严蔚敏，陈文博.数据结构及应用算法教程.北京:
清华大学出版社，2001[5]严蔚敏，吴伟民.数据结构（C语言版）.北京:
清华大学出版社，2004[6]吴文虎.程序设计基础.北京:
清华大学出版社，2003
[7]顾元刚.数据结构简明教程.南京:
东南大学出版社等，2003[8]郭福顺，王晓芬，李莲治.数据结构（修订本）.大连:
大连理工大学出版社，1997
7.附录
带注释的源程序:
#include
#include
#include
#include
武汉理工大学《应用数据结构》课程设计说明书#include
#include
#defineMAXSIZE10000//线性表中最多元素个数#defineTRUE1
#defineFALSE0
typedefintBOOL;//定义标识符关键字BOOL别名为inttypedefstructStudentData//记录数据类型{
intnum;//定义关键字类型}Data;//排序的记录数据类型定义typedefstructLinkList//记录线性表
{
定义表长intLength;//
DataRecord[MAXSIZE];//表长记录最大值}LinkList;//排序的记录线性表类型定义intRandArray[MAXSIZE];//定义随机数组类型及最大值/******************随机生成函数********************/voidRandomNum（）//随机生成函数{
inti;
srand（（int）time（NULL））;//用伪随机数程序产生伪随机数
for（i=0;iRandArray[i]=（int）rand（）;
return;
}
/*****************初始化链表**********************/voidInitLinkList（LinkList*L）//初始化链表
{
inti;
memset（L,0,sizeof（LinkList））;
RandomNum（）;//调用随机函数
for（i=0;iL->Record[i]
升级会员 