堆排序实验报告

《堆排序实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、堆排序实验一．需求和规格（10分）（将原题要解决的问题转换成用计算机要解决的问题）Eg:将用户输入的一组整型数据进行排序，构造成大顶堆（根据个人程序具体而定）；将已建立的大顶堆进行堆排序；在对话框中显示出已建成堆的具体结构；若操作错误能够给出用户相应的提示；通过MFC实现可视化界面的操作；（大家可以适当补充）二．设计思想（5分）1.将一组无序序列构造成一个堆：假设序列长度为n，以线性数组作为存储，那么从第i={n/2} ({},表示下界)个元素开始调整(因为叶子结点已经是堆无需调整)，分别和他的左右子树结点(第一次只有叶子结点)

2、比较大小，和较大的那个交换；然后i自减，对这个新的i元素进行调整，同样和他的左右子树(这时候左右子树已经是小根堆)根结点比较后进行调整，如果破坏了其中一个子树的堆平衡，那么需要继续对这个子树进行堆调整；这样调整到序列第一个元素后，这个序列就已经是大根堆2.对堆进行堆排序构造了堆之后，就可以对其进行堆排序堆的最大元素已经在堆顶，将其和序列最后一个元素交换这样得到两个序列，A=[1...n-1]  B=[n]，其中B是有序的，A失去了大顶堆的平衡，这时候继续对A进行调整，将其调整为大顶堆调整为大顶堆后，和上面过程类似，一直到A中只余

3、下一个元素为止设计表示（5分）给出具体存储结构，和关键函数操作功能说明，若没有存储结构，可以写宏定义等作为补充；实现注释（5分）能描述出涉及操作的参数含义，及操作实现的具体方案设计表示（5分）画出整体流程，及核心算法流程（本实验写出建堆过程和堆排序过程的流程图即可）用户手册（10分）描述具体，能够根据该手册进行程序的使用，并给出操作注意事项；（依个人程序情况而定）调试报告（10分）表达具体，能诊断出给定输入得不到正确输出的原因和解决方案**大家别忘了写总结，10分呢6．源程序关键代码和结果（示例）6.1源程序关键代码//func

4、tion.cpp#include"funcation.h"StatusJudgeInput(int&num,char*buffer,Int&IntTable)//编辑框一的判断{charJudgeNumberBuffer[11]={'0','1','2','3','4','5','6','7','8','9',''};//判断第一个编辑框是否为空if(num==0)returnERROR;//输入为空//判断第一个编辑框是否输入都是数字和空格for(inti=0;i

5、(*(buffer+i)==JudgeNumberBuffer[j])break;if(j==11)returnERROR;}//判断第一个编辑框的开头和结尾必须不是空格if((*buffer=='')

6、

7、(*(buffer+num-1)==''))returnERROR;intCount=1;//将字符转化为数字for(intn=0;n

8、//临时指针int*HeapSortpoint;//用于存放数据的指针p=buffer;HeapSortpoint=(int*)malloc((Count+1)*sizeof(int));IntTable=HeapSortpoint;intIkey=1;while(p

9、dHeapAdjust(int*Buffer,ints,intm)//用于堆调整{intrs=Buffer[s];//用于存放临时存放数字for(intj=2*s;j<=m;j*=2){if(j0;--i)HeapAdjust(Buffer,i,*B

10、uffer);for(intj=*Buffer;j>1;--j){intbuffer;buffer=Buffer[1];Buffer[1]=Buffer[j];Buffer[j]=buffer;HeapAdjust(Buffer,1,j-1);}}//HeapS