堆排序实验报告.doc

一、实验目的 （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、输入的形式和输入值的范围一维数组A2、输出的形式3、程序所能达到的功能4、测试数据： 五、概要设计 为了实现上述操作，应以为存储结构。 1基本操作：void Heapify(int s,int m) （2）void BuildHeap(int n) （3）void Heap_Sort(int n) 2、本程序包含个模块： （1）主程序模块； （2）（）模块调用图： 主程序模块 3、流程图 流程图见最后一页 六、详细设计 1int R[MAX]; 元素类型为整形。 2、每个模块的分析： （1）主程序模块：void main() { int i,n; printf(请输入数组A元素的个数:); scanf(%d,n); if(n=0||nMAX) { printf(请重新输入n); } printf(请输入数组A的元素值\n); for(i=1;i=n;i++) scanf(%d,R[i]); Heap_Sort(n); printf(输出排好序后的A中的元素); for(i=1;i=n;i++) printf(%3d,R[i]); printf(\n); } （2）void Heap_Sort(int n) 堆排序函数模块 void Heap_Sort(int n) { //对R[1……n]进行堆排序，用R[0]做暂存单元 int i; BuildHeap(n);//将R[1-n]简称初堆 for(i=n;i1;i--) { //对当前无序区R[1……n]进行堆排序，共做n-1趟 R[0]=R[1];//将堆顶和堆中最后一个元素交换 R[1]=R[i];//将R[1……n]重新调整为堆，仅有R[1]可能会违反堆性质 R[i]=R[0]; 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) { //对R[1……n]进行堆调整，用temp做暂存单元 int j,temp; temp=R[s]; j=2*s; while(j=m) { if(R[j]R[j+1]jm) j++; if(tempR[j]) break; R[s]=R[j]; s=j; j=j*2; } R[s]=temp; } 3）函数调用关系图main() void Heap_Sort(int n) void BuildHeap(int n) void Heapify(int s,int m) 3、完整的程序：#includestdio.h #define MAX 255 int R[MAX]; void Heapify(int s,int m) { //对R[1……n]进行堆调整，用temp做暂存单元 int j,temp; temp=R[s]; j=2*s; while(j=m) { if(R[j]R[j+1]jm) j++; if(tempR[j]) break; R[s]=R[j]; s=j; j=j*2; } R[s]=temp; } void BuildHeap(int n) { //由一个无序的序列简称一个堆 int i; for(i=n/2;i0;i--) Heapify(i,n); } void Heap_Sort(int n) { //对R[1……n]进行堆排序，用R[0]做暂存单元 int i; BuildHeap(n);//将R[1-n]简称初堆 for(i=n;i1;i--) { //对当前无序区R[1……n]进行堆排序，