堆排序实验报告

1、一正文红色部分表示示例内容，供参考、实验目的（1）了解堆排序方法概念；（2）理解堆排序方法的求解过程；（3）掌握堆排序方法运算二、实验内容（1）建立包含10个数据序列的堆（数据元素的值由自己设定）；（2）完成堆排序运算的程序；（3）给出程序和堆排序前后的结果。三、实验环境1、硬件配置：Pentium（R） Dual-Core9 CUP E6500 2.93GHz，1.96的内存2、软件环境：Microsoft Windows XP Professional Service Pack 3，Microsoft Visual C+ 6.0四、需求分析1、输入的形式和输入值的范围：根据题目要求与提示先

2、输入一维数组A的个数n，然后输入数组A中的元素，且数与数之间用空格隔开，回车。 2、输出的形式：输出排好序后的数组A中的元素值。3、程序所能达到的功能：程序能将一个数据类型为整型的一维数组A，且数组A中的元素呈现无序状态，运行程序后能将A中的数据元素按从小到大的顺序输出。4、测试数据：输入数组A的元素个数n为6，数组A中的元素分别为8，5 12,9,23,66并用空格将数隔开，回车如：8 5 12 9 23 665 8 9 12 23 66输出排序好后的数组A为：5 8 9 12 23 66.五、概要设计为了实现上述操作，应以数组为存储结构。1、基本操作：（1）void Heapify(int

3、 s,int m)（2）void BuildHeap(int n)（3）void Heap_Sort(int n)2、本程序包含二个模块：（1）主程序模块；（2）堆排序模块，建堆模块，堆调整模块（3）模块调用图：主程序模块堆排序模块建堆模块堆调整模块3、流程图重点内容流程图见最后一页六、详细设计1、存储类型，int RMAX;元素类型为整形。2、每个模块的分析：（1）主程序模块：void main() int i,n;printf("请输入数组A元素的个数:");scanf("%d",&n);if(n<=0|n>MAX) printf

4、("请重新输入n");printf("请输入数组A的元素值n");for(i=1;i<=n;i+) scanf("%d",&Ri);Heap_Sort(n);printf("输出排好序后的A中的元素");for(i=1;i<=n;i+) printf("%3d",Ri);printf("n");（2）void Heap_Sort(int n) 堆排序函数模块 void Heap_Sort(int n) /对R1n进行堆排序，用R0做暂存单元 int i;

5、BuildHeap(n);/将R1-n简称初堆 for(i=n;i>1;i-) /对当前无序区R1n进行堆排序，共做n-1趟 R0=R1;/将堆顶和堆中最后一个元素交换R1=Ri;/将R1n重新调整为堆，仅有R1可能会违反堆性质Ri=R0; Heapify(1,i-1); 建堆函数模块void BuildHeap(int n) /由一个无序的序列简称一个堆 int i; for(i=n/2;i>0;i-) Heapify(i,n);堆调整函数模块void Heapify(int s,int m) /对R1n进行堆调整，用temp做暂存单元 int j,temp;temp=Rs;j=

6、2*s;while(j<=m) if(Rj<Rj+1&&j<m) j+; if(temp>Rj) break; Rs=Rj; s=j; j=j*2;Rs=temp;3）函数调用关系图main()void Heap_Sort(int n)void BuildHeap(int n)void Heapify(int s,int m)3、完整的程序：#include"stdio.h"#define MAX 255int RMAX;void Heapify(int s,int m) /对R1n进行堆调整，用temp做暂存单元 int j,tem

7、p;temp=Rs;j=2*s;while(j<=m) if(Rj<Rj+1&&j<m) j+; if(temp>Rj) break; Rs=Rj; s=j; j=j*2;Rs=temp;void BuildHeap(int n) /由一个无序的序列简称一个堆 int i; for(i=n/2;i>0;i-) Heapify(i,n);void Heap_Sort(int n) /对R1n进行堆排序，用R0做暂存单元 int i; BuildHeap(n);/将R1-n简称初堆 for(i=n;i>1;i-) /对当前无序区R1n进行堆排序，

8、共做n-1趟 R0=R1;/将堆顶和堆中最后一个元素交换R1=Ri;/将R1n重新调整为堆，仅有R1可能会违反堆性质Ri=R0; Heapify(1,i-1); void main() int i,n;printf("请输入数组A元素的个数:");scanf("%d",&n);if(n<=0|n>MAX) printf("请重新输入n");printf("请输入数组A的元素值n");for(i=1;i<=n;i+) scanf("%d",&Ri);Heap_So

9、rt(n);printf("输出排好序后的A中的元素");for(i=1;i<=n;i+) printf("%3d",Ri);printf("n");七、程序使用说明及测试结果1、程序使用说明（1）本程序的运行环境为VC6.0。（2）进入演示程序后即显示提示信息：请输入数组A元素的个数：回车；请输入数组A的元素值: 8 5 12 9 23 66输出排好序后的A中的元素:5 8 9 12 23 662、测试结果：例如：输入：8 5 12 9 23 66输出：5 8 9 12 23 663、调试中的错误及解决办法。调试过程中，遇到了

10、许多的问题,在建堆，堆调整和堆排序的过程中遇到了一些问题，通过查阅与数据结构相关联的的一些参考书目，能够将问题解决，比如堆排序有建大堆和小堆之分，然后排序结果有降序和升序的方法，开始是是按降序输出的结果，将Rj，Rj+1关系做了调整后，得到升序的结果运行界面先输入数组A元素的个数后，回车：再输入数组A的元素值:后回车：输出排好序后的A中的元素:八、实验小结重点内容：排序算法有很多，堆排序是其中之一，比如有冒泡排序，快速排序，插入排序等，每个算法都自己的优缺点，学习完堆排序和编写完堆排序的程序后，对堆排序有了更深层次的理解，此次编程还是遇到了些许问题，但是通过查阅图书馆相关的 参考书目，能够顺利的完成本次作业。签 名：日 期：实验成绩：批阅日期：开始i=n/2int i;int i,n;n<=0|n>MAXscanf("%d",&n);printf("请输入数组A元素的个数:");i>0调用Heapify(int s,int m)函数int j=2*s, temp=Rs;j<=mRj<Rj+1&&j<mprintf("请重新输入n");i<=ni=1printf("请输入数组A的元素值n