数据结构课程设计--堆排序的算法的实现

《数据结构课程设计--堆排序的算法的实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构课程设计设计说明书堆排序的算法的实现学生姓名学号班级成绩指导教师计算机科学与技术系2011年3月4日数据结构课程设计评阅书题目堆排序原理的算法的实现学生姓名学号指导教师评语成绩：指导教师签名：年月日答辩教师评语成绩：答辩教师签名：年月日教研室意见成绩：室主任签名：年月日注：指导教师成绩60%，答辩成绩40%，总成绩合成后按五级制记入。课程设计任务书2010—2011学年第二学期专业：学号：姓名：课程设计名称：数据结构课程设计设计题目：堆排序算法的实现完成期限：自2011年2月19日至2011年3月4日共2周设计依据、要求及主要内容（可另加附页）：堆实质上是

2、满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。如关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，故它们均是堆。大根堆和小根堆：根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆，又称最小堆。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆。注意：①堆中任一子树亦是堆。②以上讨论的堆实际上是二叉堆(BinaryHeap)，大根堆排序的基本思想：　　①先将初始文件R[1..n]建成一个大根堆

3、,此堆为初始的无序区。　　②再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key。　　③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。要求

4、：（1）给出一个符合堆序列的一组数，能够建立大根堆和小根堆。（2）界面友好，可操作性强。（3）能够实现数据个数的变化输入，并建立相应的堆。指导教师（签字）：教研室主任（签字）：批准日期：年月日摘要设计了一个堆排序算法实现的程序，此程序具有排序的功能，能够对输入的任何数字进行处理之后，有序的输出。在设计之前，首先要明白什么是堆，以及堆排序的原理，明白了原理之后，结合之前所掌握的C++编程知识，分部分进行编译，最后再进行组合，完成此程序之后，可视化界面比较清晰，操作比较简单，易于为用户接受。关键词：堆排序；大顶堆；筛选目录1.课题描述12.问题分析和任务定义23.逻辑

5、设计34.程序编码65.结果分析86.总结10参考文献111.课题描述本课题是利用堆排序的算法原理对数据进行排序，使所输入的数据以递减或者递增的方式输出，主要是利用堆排序算法进行设计，设计筛选函数，和排序函数，以及对这些函数的综合运用。111.问题分析和任务定义本次程序设计，主要设计的问题是如何利用堆排序原理进行设计，应该结合书本所含有的理论，结合一些程序实例，进行完成，本次设计的任务是，编一个能够实现堆排序算法的程序，并设计一个可视化界面，此次程序设计过程中，有两大模块，一个是筛选函数，另一个是排序函数。111.逻辑设计运用数据结构中所学的函数进行流程图设计。堆

6、排序主函数结束3.1堆排序主函数流程图11大顶堆筛选函数结束3.2堆排序筛选函数11大顶堆排序函数3.3堆排序排序函数111.程序编码#include#includeusingnamespacestd;voidBigHeapAdjust(int*p,intr,intlen);voidBigHeapSort(int*p,intlen);intmain(){intarray[1000]={0};intn;printf("请输入排序元素的个数：");scanf("%d",&n);printf("请输入要排序的元素：");for(in

7、ti=0;i=p[j])++j;if(tmp>=p[j])break;p[r]

8、=p[j]