快速排序和堆排序 数据结构实验报告

1、课程名称：数据结构班级：102012指导教师评定：签实验名称：实验十内部排序学生姓名：学号：名：题目：编程分别实现快速排序算法、堆排序算法。一、需求分析用户可以根据自己的需求输入一个顺序表。通过利用快速排序法按非递减排序已有的顺序表。通过利用堆排序按非递减排序已有的顺序表。程序执行的命令包括：(1)创建顺序表(2)输出顺序表(3快速排序算法排序(4)堆排序算法排序二、概要设计为实现上述算法，需要顺序表的抽象数据类型：ADTsqlist数据对彖D：D是具有相同特征的数据元素的集合。各数据元素均含有类型相同，可唯一标识数据元素的关键字。数据关系R：数据元素同属一个集合。基本操作P：Creatsql

2、ist(&1)操作结果：构造一个具有n个数据元素的顺序表loListLength(L)初始条件：线性表L已经存在操作结果：返回L中数据元素的个数。destroylist(&1)初始条件：顺序表1存在。操作结果：销毁顺序表1。displaylist(1)初始条件：顺序表1存在。操作结果：显示顺序表1。quicksort(&1)初始条件：顺序表1存在。操作结果：通过快速排序得到一个有序的顺序表loheapsort(&1)初始条件：顺序表1存在。操作结果：通过堆排序得到一个有序的顺序表loheapadjust(&1,sm)初始条件：顺序表1存在。操作结果：调整h-rs的关键字，使h-rs成为一个大顶

3、堆partion（&1,&1ow,high）初始条件：顺序表1存在。操作结果：交换顺序表中子表rlow.high的记录，使枢轴记录到位，并返回其所在的位置。ADTsqlist本程序有三个模块：（1）主程序模块mainO初始化：接受命令:显示结果;（2）创建顺序表的模块：主要建立一个顺序表;快速排序模块：得到一个有序的顺序表：（4）输出顺序表模块：显示已创建顺序表；（5）堆排序模块：得到一个有序的顺序表。三、详细设计1元素类型，结点类型typedefstructintkey;keytype;typedefstructkeytyper100:int2ngth;sqlist;对抽彖数据类型中的部分基

4、本操作的伪码算法如下:/*创建顺序表*/voidcreat(sqlist*1)intprintf(pleaseintputitslength:);scanf&1-length);printf(z，nnpleaseintput%ddatan，z,llength);for(i=l;ilength;i+)scanf(“%&key);l-rikey=key;/*交换顺序表中子表rlow.high的记录，使枢轴记录到位，并返回其所在的位置*/intpartion(sqlist*1,intlow,inthigh)intpivotkey;l-r0l-rlow;pivotkey=lrlowkey;while(

5、lowhigh)while(lowrhigh_key=pivotkey)high;l-rlow=l-rhigh;while(lowrlowkeyrhigh=l-rlow;l-rlowl-r0;returnlow;/*快速排序*/voidQsort(sqlist*1,intlow,inthigh)intpivotloc;if(lowlength);/*显示顺序表*/voiddisplay(sqlist*1)inti;for(i=l;ilength;i+)printf(，z%4.2d,i);printfCXn);for(i=l;ilength;i+)printfC3；printfCn)；for(i

6、=l;ilength;i+)printf2d,1-工ikey);/*调整h-rs的关键字，使h-rs成为一个人顶堆*/voidheapadjust(sqlist*h,ints,intm)keytyperc;intj；rc=h-rs;for(j=2*s;jrj+1key)+j;if(rckey=hrjkey)break:h-rs=h-rj;s二j；h-rs=rc;/*对顺序表h进行堆排序*/voidheapsort(sqlist*h)keytyperc;inti;for(i=h-length/2;i0;i)heapadjust(h,i,hlength);for(i=h-length;il;i)r

7、c=h-r1;h-rlh-ri;hrLi=rc;heapadjust(h,1,il);主函数和其他函数的伪码算法/*主函数*/voidmainOsqlisti;creat(&t);Qsort(&t,1,tlength);printfCnn，z);printf(quicksortmeans：n);display(&t);heapsort(&t);printfCnz，);printf(/znheapsortmeans:nz，);display(&t);g己tch();4函数调用关系mainheapsortdisplaycreatQsortheapadjustpartion四、调试分析1开始的时候在

8、编写快速排序算法的时候没有设置用子表的第一个记录作枢轴记录导致没有得到正确的结果。在l-rlow=l-rhigh;语句进行交换时,写成lrlow.key=lrhigh.key,一直没有找到错误的地方，在看了参考资料后才发现是这里错了。算法的时空分析各操作的算法时间复杂度比较合理creat,partion,display为0(n)Qsort,heapadjustheapsort为O(nlogn)注：n为哈希表的长度。本次实验采用数据抽彖的程序设计方法，将程序化为三层次结构，设计时思路清晰，使调试也较顺利，各模块有较好的可重用性。五、用户手册1-本程序的运行环境为windowsxp操作系统，并且在

9、TC2.0中运行，执行文件为ExplO.c；2.进入演示程序后，完成编译，再点击超级工具集里的中文DOS环境运行选项，进入DOS环境中，用户根据需求键入相应的数据，可以看到相应的结果。六、测试结果在dos下输入数据元素：98231056212301647434排序后的结果是：01102123233456647498则在dos界面输入如图所示：C:.DOCUME-1ADMINI-1面.paixu.exepleaseintputitslength=10pleaseintput10data&8231056212301647434o;uicksot*tmeans:pl02030405060?08091

10、00丄102123233456647498iea.psoitmeans:0102030405060708091001102123233456647498七、附录：源程序#includestdio.htypedefstructintkey;keytype;typedefstructkeytyper100;int2ngth;sqlist;/*创建顺序表*/voidcreat(sqlist*1)inti,“y;printf(pleaseintputitslength:);scanf&1-length);printf(z，nnpleaseintput%ddatan，z,llength);for(i=l

11、;ilength;i+)scanf(，z%d，z,&key);lrikey=key;/*交换顺序表中子表rlow.high的记录，使枢轴记录到位，并返回其所在的位置*/intpartion(sqlist*1,intlow,inthigh)intpivotkey;l-r0l-rlow;pivotkey=lrlowkey;while(lowhigh)while(lowrhigh_key=pivotkey)high;lrlow=lrhigh;while(lowrlowkeyrhigh=l-rlow;l-rlowl-r0;returnlow;/*快速排序*/voidQsort(sqlist*1,int

12、low,inthigh)intpivotloc;if(lowhigh)pivotloc二partion(l,low,high);Qsort(1,low,pivotloc-1);Qsort(1,pivotloc+1,high);/*显示顺序表*/voiddisplay(sqlist*1)inti;for(i=l;ilength;i+)printf2d,i);printfCnz，);for(i=l;ilength;i+)printfC3；printfCnz，);for(i=l;ilength;i+)printf2d,1-工ikey);/*调整h-rs的关键字，使h-rs成为一个人顶堆*/voidheapadjust(sqlist*h,ints,intm)keytyperc;intj；rc=h-rs;for(j=2*s;jrj+1key)+j;if(rckey=hrjkey)break:h-rs=h-rj;s二j；h-rs=rc;/*对顺序表h进行堆排序*/voidheapsort(sqlist*h)keytyperc;inti;for(i=h-length/2;i0;i)heapadjust(h,i,hlength);for(i=h-length;il;i)rc=h-r1;h-rl二h-ri;hri=rc;