《内部堆排序算法的实现课程设计说明书》由会员分享,可在线阅读,更多相关《内部堆排序算法的实现课程设计说明书(22页珍藏版)》请在金锄头文库上搜索。
1、. . .数据结构课程设计设计说明书内部堆排序算法的实现学生姓名 金少伟 学 号 1121024029 班 级 信管1101 成 绩 指导教师 曹阳 数学与计算机科学学院2013年3月15日 .专业资料.课程设计任务书20122013学年第二学期课程设计名称: 数据结构课程设计 课程设计题目: 内部堆排序算法的实现 完 成 期 限:自 2013年 3 月4日至 2013年 3 月 15 日共 2 周设计内容: 堆排序(heap sort)是直接选择排序法的改进,排序时,需要一个记录大小的辅助空间。n个关键字序列K1,K2,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质): kiK2i且k
2、iK2i+1 或(2)KiK2i且kiK2i+1(1i n) 若将此序列所存储的向量R1.n看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。 (即如果按照线性存储该树,可得到一个不下降序列或不上升序列)。 本课程设计中主要完成以下内容: 1.设计堆排序算法并实现该算法。 2.对堆排序的时间复杂度及空间复杂度进行计算与探讨。 3.寻找改进堆排序的方法。 基本要求如下: 1.程序设计界面友好;2.设计思想阐述清晰;3.算法流程图正确;4.软件测试方案合理、有效。指导教师:曹阳 教研室负责人:申静课程
3、设计评阅评语: 指导教师签名: 年 月 日摘 要堆排序是直接选择排序法的改进。本课设以VC+6.0作为开发环境,C语言作为编程语言,编程实现了堆排序算法。程序运行正确,操作简单,易于为用户接受。关键词:堆排序;C语言;时间复杂度.专业资料.目 录1课题描述12. 算法描述22.1 堆排序描述22.2 堆排序算法的图示22.3 堆排序算法53算法流程图64代码实现75. 算法分析106. 测试11总结12参考文献13.专业资料.1 课题描述查找是计算机的一项主要功能,为了查找方便,通常希望计算机中的表是按关键字是有序的。因为有序的顺序表可采用查找效率较高的折半查找法,而无序的表只能进行顺序查找。
4、因此排序也就是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列。因此,学习和研究各种排序方法是计算机工作者的重要课题之一。本课题利用简单选择排序中的堆排序方法,通过对用户输入的可以组成堆的数据元素建立大、小根堆,并将其进行排序输出,使其成为一个按关键字排序的有序序列,从而有效地提高了查找的效率。开发工具:vc+6.0.专业资料.2. 算法描述2.1 堆排序描述堆排序只需要一个记录大小的辅助空间,每个待排序的记录仅占有一个存储空间。堆的定义如下:n个元素的序列(k1,k2,kn)当且仅当满足下关系时,称之为堆。kiK2i且kiK2i+
5、1 或(2)KiK2i且kiK2i+1(1i n) 若将和此程序对应的一维数组看成是一个完全二叉树,则堆的含义表明,完全二叉树中所有非终端结点的值均不大于(或小不于)其左、右孩子结点的值。由此,若序列k1,k2,kn是堆,则堆顶元素必须为序列中n 的元素的最大值。例如,下列一个序列为堆,对应的完全二叉树如图2.1所示。96,83,27,38,11,9 98278338119图2.1序列96,83,27,38,11,9对应的堆若再输出堆顶的最大值之后,使得剩余n-1个元素的序列重又建成一个堆,则得到n元素中的最大值。如此反复执行,便能得到一个有序序列,这个过程称之为堆排序。2.2 堆排序算法的图
6、示 一组无序序列:49,38,65,97,76,13,27,49 堆排序算法的演示过程如图2.2.和图2.3所示: 499381376652797494938657613274997 (a) (b)49976576132749384997657613274938(c) (d)9776654913274938(e)图2.2 建初始堆过程示例 49766549132797387649654913279738 (a) (b)27496549137697386549274913769738 (c) (d)13492749657697384913274965769738(e) (f)4913274949
7、65769738381327494965769749(g) (h) 271338494965769749132738494965769749(l) (m)图2.3输出对元素并调整建新堆的过程2.3 堆排序算法堆排序算法代码如下:Typedef Sqlist HeapType;Void HeapAdjust( HeapType &H,int s,int m)/j建大顶堆函数 RC=H.rs; for(j=2*s;j=m;j*=2) if(j0;-i) HeapAdjust( H, i, H.length) for (i=H.length;i1;-i) t=H.r1; /交换堆顶元素与堆中最后一个
8、元素 H.r1 =H.ri; H.ri=t; HeapAdjust(H,1 ,i-1);3算法流程图建堆过程流程图如图3.1所示:图3.1建堆流程图堆排序流程图如图3.2所示: 图3.2堆排序流程图4代码实现程序源代码:#include#include#include#define MAX 50/数据输入子函数void InputData(int list) int i=1;printf(请输入要排序的数据(以-1结束):n);/用-1表示数据输入结束,-1不包括在排序数据中scanf(%d,&listi); while(listi!=-1)i+;scanf(%d,&listi); list0=i-1;/list0用来放list数组的长度/void panduan(int list,int n) int i=1; for(i=1;in;i+) if(isdigit(listi)=0) printf(序列为非完全数字序列,无法排序。n); exit(0); /数据输出子函数void OutputData(int list,int n) int i=1;printf(排序后的数列是:n);for(i=1;i=n;i+) if(i%4=0) printf(n);