堆排序实验报告.docx

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、输入的形式和输入值的范围：根据题目要求与提示先输入一维数组A的个

2、数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 s,int m)

3、（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(nMAX) printf(请重新输入n); printf(请输入数组A的元素值n); for(i=1;i=n;i+) sca

4、nf(%d,&Ri); Heap_Sort(n); printf(输出排好序后的A中的元素); for(i=1;i1;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;i0;i-) Heapify(i,n);堆调整函数模块void Heapify(int s,int m) /对R1n进行堆调整，用temp做暂存单元 int

5、 j,temp; temp=Rs; j=2*s; while(j=m) if(RjRj+1&jRj) 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、完整的程序：#includestdio.h#define MAX 255int RMAX;void Heapify(int s,int m) /对R1n进行堆调整，用temp做暂存单元 int j,temp; temp=Rs; j=2*s; while(j=m)

6、 if(RjRj+1&jRj) break; Rs=Rj; s=j; j=j*2; Rs=temp;void BuildHeap(int n) /由一个无序的序列简称一个堆 int i; for(i=n/2;i0;i-) Heapify(i,n);void Heap_Sort(int n) /对R1n进行堆排序，用R0做暂存单元 int i; BuildHeap(n);/将R1-n简称初堆 for(i=n;i1;i-) /对当前无序区R1n进行堆排序，共做n-1趟 R0=R1;/将堆顶和堆中最后一个元素交换 R1=Ri;/将R1n重新调整为堆，仅有R1可能会违反堆性质 Ri=R0; Heapi

7、fy(1,i-1); void main() int i,n; printf(请输入数组A元素的个数:); scanf(%d,&n); if(nMAX) printf(请重新输入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);七、程序使用说明及测试结果1、程序使用说明（1）本程序的运行环境为VC6.0。（2）进入演示程序后即显示提示信息：请输入数组A元素的个数：回车；请输入数组

8、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、调试中的错误及解决办法。调试过程中，遇到了许多的问题,在建堆，堆调整和堆排序的过程中遇到了一些问题，通过查阅与数据结构相关联的的一些参考书目，能够将问题解决，比如堆排序有建大堆和小堆之分，然后排序结果有降序和升序的方法，开始是是按降序输出的结果，将Rj，Rj+1关系做了调整后，得到升序的结果运行界面先输入数组A元素的个数后，回车：再输入数组A的元素值:后回车：输出排好序后的A中的元素:八、实验小结：排序算法有很多，堆排序是其中之一，比如有冒泡排序，快速排序，插入排序等，每个算法都自己的优缺点，学习完堆排序和编写完堆排序的程序后，对堆排序有了更深层次的理解，此次编程还是遇到了些许问题，但是通过查阅图书馆相关的 参考书目，能够顺利的完成本次作业。签 名：日 期：实验成绩：批阅日期：