数据结构课程设计设计说明书-内部堆排序算法的实现

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

1、数据结构课程设计设计说明书内部堆排序算法的实现学生姓名学号班级计本092成绩指导教师计算机科学与技术系2011年9月9日数据结构课程设计评阅书题目内部堆排序算法的实现学生姓名学号指导教师评语及成绩指导教师签名：年月日答辩评语及成绩答辩教师签名：年月日教研室意见总成绩：室主任签名：年月日课程设计任务书2011—2012学年第一学期专业：计算机科学与技术学号：姓名：金强胜课程设计名称：数据结构课程设计设计题目：内部堆排序算法的实现完成期限：自2011年8月29日至2011年9月9日共2周设计依据、要求及主要内容：堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不

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

3、顶)和无序区的最后一个记录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]调整为堆。要求：（1）给出一个符合堆序列的一组数，能够建立大根堆和小根堆。（2）界面

4、友好，可操作性强。（3）能够实现数据个数的变化输入，并建立相应的堆。指导教师（签字）：教研室主任（签字）：批准日期：年月日摘要随着计算机技术的发展，为了查找方便，通常希望通过排序使表是按关键字有序的。本课题利用简单选择排序中的堆排序方法，通过建立大、小根堆，并对数据元素进行排序输出，实现对用户输入的一组可以组成堆的数据元素进行处理，使其按关键字排成为一个有序的序列，从而有效地提高了查找效率。关键词：堆；排序；查找目录1课题描述12设计过程22.1流程图22.1.1函数设计思想流程图22.1.2程序流程图22.2分步程序设计72.2.1建立堆函数72.2.2输出堆函数72.

5、2.3输出已排序数组函数92.2.4主函数93测试123.1第一组测试数据测试结果123.2第二组测试数据测试结果13总结16参考资料17附录18程序源代码181课题描述随着计算机技术的发展，为了查找方便，通常希望计算机中的表是按关键字有序的。因为有序的顺序表可采用查找效率较高的折半查找法，而无序的表只能进行顺序查找。排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。因此，学习和研究各种排序方法是计算机工作者的重要课题之一。本课题利用简单选择排序中的堆排序方法，通过对用户输入的可以组成堆的数据元素建立大、

6、小根堆，并将其进行排序输出，使其成为一个按关键字排序的有序序列，从而有效地提高了查找的效率。开发工具：TC2.0212设计过程2.1流程图2.1.1函数设计思想流程图：函数设计思想流程图如图2.1。图2.1函数设计思想流程图2.1.2程序流程图建立大根堆函数的程序流程图如图2.2。21图2.2建立大根堆函数的程序流程图建立小根堆函数的程序流程图如图2.3。21图2.3建立小根堆函数的程序流程图21输出大根堆函数的程序流程图如图2.4。图2.4输出大根堆函数的程序流程图输出小根堆函数的程序流程图如图2.5。21图2.5输出小根堆函数的程序流程图212.2分步程序设计2.2.

7、1建立堆函数当运行程序，用户按照提示输入正确的信息并敲击回车键时，程序就会相应地建立出大、小根堆函数，为后续的运行做准备。程序源代码如下：//建立大根堆函数voidbuildbig(int*a,inti,intn){inttmp;k=i;j=2*k+1;while(j<=n){if(j=a[j])break;tmp=a[k];a[k]=a[j];a[j]=tmp;k=j;j=2*j+1;}}//建立小根堆函数voidbuildlittle(int*a,inti,intn)