堆排序实验报告.doc

堆排序实验一需求和规格（10分）（将原题要解决的问题转换成用计算机要解决的问题）Eg:将用户输入的一组整型数据进行排序，构造成大顶堆（根据个人程序具体而定）；将已建立的大顶堆进行堆排序；在对话框中显示出已建成堆的具体结构；若操作错误能够给出用户相应的提示；通过MFC实现可视化界面的操作；（大家可以适当补充）二设计思想（5分）1.将一组无序序列构造成一个堆：假设序列长度为n，以线性数组作为存储，那么从第i = n/2 (,表示下界)个元素开始调整(因为叶子结点已经是堆无需调整)，分别和他的左右子树结点(第一次只有叶子结点)比较大小，和较大的那个交换；然后i自减，对这个新的i元素进行调整，同样和他的左右子树(这时候左右子树已经是小根堆)根结点比较后进行调整，如果破坏了其中一个子树的堆平衡，那么需要继续对这个子树进行堆调整；这样调整到序列第一个元素后，这个序列就已经是大根堆2.对堆进行堆排序构造了堆之后，就可以对其进行堆排序堆的最大元素已经在堆顶，将其和序列最后一个元素交换这样得到两个序列， A=1 . n-1 B= n ，其中B是有序的，A失去了大顶堆的平衡，这时候继续对A进行调整，将其调整为大顶堆调整为大顶堆后，和上面过程类似，一直到A中只余下一个元素为止设计表示（5分）给出具体存储结构，和关键函数操作功能说明，若没有存储结构，可以写宏定义等作为补充；实现注释（5分）能描述出涉及操作的参数含义，及操作实现的具体方案设计表示（5分）画出整体流程，及核心算法流程（本实验写出建堆过程和堆排序过程的流程图即可）用户手册（10分）描述具体，能够根据该手册进行程序的使用，并给出操作注意事项；（依个人程序情况而定）调试报告（10分）表达具体，能诊断出给定输入得不到正确输出的原因和解决方案*大家别忘了写总结，10分呢6源程序关键代码和结果（示例） 6.1 源程序关键代码/function.cpp#include funcation.hStatus JudgeInput(int &num,char *buffer,Int &IntTable)/编辑框一的判断char JudgeNumberBuffer11=0,1,2,3,4,5,6,7,8,9, ;/判断第一个编辑框是否为空if(num=0)return ERROR;/输入为空/判断第一个编辑框是否输入都是数字和空格for(int i=0;inum;i+)for(int j=0;j11;j+)if(*(buffer+i)=JudgeNumberBufferj)break;if(j=11)return ERROR;/判断第一个编辑框的开头和结尾必须不是空格if(*buffer= )|(*(buffer+num-1)= )return ERROR;int Count=1;/将字符转化为数字for(int n=0;nnum;n+)if(*(buffer+n)= )*(buffer+n)=0;Count+;if(*(buffer+n+1)= )return ERROR;char *p;/临时指针int *HeapSortpoint;/用于存放数据的指针p=buffer; HeapSortpoint=(int *)malloc(Count+1)*sizeof(int);IntTable=HeapSortpoint;int Ikey=1;while(pbuffer+num) HeapSortpointIkey=atoi(p);/将数据存入数组中Ikey+;p=p+strlen(p)+1;num=Count;/将数组数目传给num*IntTable=num;/将个数放入里面return OK;void HeapAdjust(int *Buffer,int s,int m)/用于堆调整int rs=Buffers;/用于存放临时存放数字for(int j=2*s;j=m;j*=2) if(jm&BufferjBufferj+1) j+; if(!(rs0;-i) HeapAdjust(Buffer,i,*Buffer);for(int j=*Buffer;j1;-j)int buffer;buffer=Buffer1;Buffer1=Bufferj;Bufferj=buffer;HeapAdjust(Buffer,1,j-1);/HeapSortDlg.cppvoid CHeapSortDlg:OnBuildButton() / TODO: Add your control notification handler code hereUpdateData(TRUE);/更新编辑框里面的数据char *Buffer;/用于指向编辑框字符串的指针int num;/用于存放字符的个数num=m_input.GetLength();/字符个数Buffer=m_input.GetBuffer(num);/用于存放其指针if(!JudgeInput(num,Buffer,HeapSortBuffer)MessageBox(输入失败);return ;for(int i=*HeapSortBuffer/2;i0;-i) HeapAdjust(HeapSortBuffer,i,*HeapSortBuffer);ShowTheTree(hTREEITEM,m_showtree,HeapSortBuffer);MessageBox(大顶堆建立成功);void CHeapSortDlg:OnPaixunButton() / TODO: Add your control notification handler code here m_showtree.DeleteAllItems(); free(hTREEITEM); YZH