堆排序实验报告.docx
《堆排序实验报告.docx》由会员分享，可在线阅读，更多相关《堆排序实验报告.docx（9页珍藏版）》请在冰点文库上搜索。
堆排序实验报告
一、实验目的
（1）了解堆排序方法概念；
（2）理解堆排序方法的求解过程；
（3）掌握堆排序方法运算
二、实验内容
（1）建立包含10个数据序列的堆（数据元素的值由自己设定）；
（2）完成堆排序运算的程序；
（3）给出程序和堆排序前后的结果。
三、实验环境
1、硬件配置：
Pentium（R）Dual-Core9CUPE6500@2.93GHz，1.96的内存
2、软件环境：
MicrosoftWindowsXPProfessionalServicePack3，MicrosoftVisualC++6.0
四、需求分析
1、输入的形式和输入值的范围：
根据题目要求与提示先输入一维数组A的个数n，然后输入数组A中的元素，且数与数之间用空格隔开，回车。
2、输出的形式：
输出排好序后的数组A中的元素值。
3、程序所能达到的功能：
程序能将一个数据类型为整型的一维数组A，且数组A中的元素呈现无序状态，运行程序后能将A中的数据元素按从小到大的顺序输出。
4、测试数据：
输入数组A的元素个数n为6，数组A中的元素分别为8，512,9,23,66并用空格将数隔开，回车如：
851292366
589122366
输出排序好后的数组A为：
589122366.
五、概要设计
为了实现上述操作，应以数组为存储结构。
1、基本操作：
（1）voidHeapify（ints,intm）
（2）voidBuildHeap（intn）
（3）voidHeap_Sort（intn）
2、本程序包含二个模块：
（1）主程序模块；
（2）堆排序模块，建堆模块，堆调整模块
（3）模块调用图：
主程序模块
堆排序模块
建堆模块
堆调整模块
3、流程图
流程图见最后一页
六、详细设计
1、存储类型，
intR[MAX];
元素类型为整形。
2、每个模块的分析：
（1）主程序模块：
voidmain（）
{
inti,n;
printf（"请输入数组A元素的个数:
"）;
scanf（"%d",&n）;
if（n<=0||n>MAX）
{
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）voidHeap_Sort（intn）堆排序函数模块
voidHeap_Sort（intn）
{//对R[1……n]进行堆排序，用R[0]做暂存单元
inti;
BuildHeap（n）;//将R[1-n]简称初堆
for（i=n;i>1;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）;
}
}
建堆函数模块
voidBuildHeap（intn）
{//由一个无序的序列简称一个堆
inti;
for（i=n/2;i>0;i--）
Heapify（i,n）;
}
堆调整函数模块
voidHeapify（ints,intm）
{//对R[1……n]进行堆调整，用temp做暂存单元
intj,temp;
temp=R[s];
j=2*s;
while（j<=m）
{
if（R[j]if（temp>R[j]）break;
R[s]=R[j];
s=j;
j=j*2;
}
R[s]=temp;
}
3）函数调用关系图
main（）
voidHeap_Sort（intn）
voidBuildHeap（intn）
voidHeapify（ints,intm）
3、完整的程序：
#include"stdio.h"
#defineMAX255
intR[MAX];
voidHeapify（ints,intm）
{//对R[1……n]进行堆调整，用temp做暂存单元
intj,temp;
temp=R[s];
j=2*s;
while（j<=m）
{
if（R[j]if（temp>R[j]）break;
R[s]=R[j];
s=j;
j=j*2;
}
R[s]=temp;
}
voidBuildHeap（intn）
{//由一个无序的序列简称一个堆
inti;
for（i=n/2;i>0;i--）
Heapify（i,n）;
}
voidHeap_Sort（intn）
{//对R[1……n]进行堆排序，用R[0]做暂存单元
inti;
BuildHeap（n）;//将R[1-n]简称初堆
for（i=n;i>1;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）;
}
}
voidmain（）
{
inti,n;
printf（"请输入数组A元素的个数:
"）;
scanf（"%d",&n）;
if（n<=0||n>MAX）
{
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"）;
}
七、程序使用说明及测试结果
1、程序使用说明
（1）本程序的运行环境为VC6.0。
（2）进入演示程序后即显示提示信息：
请输入数组A元素的个数：
回车；
请输入数组A的元素值:
851292366
输出排好序后的A中的元素:
589122366
2、测试结果：
例如：
输入：
851292366
输出：
589122366
3、调试中的错误及解决办法。
调试过程中，遇到了许多的问题,在建堆，堆调整和堆排序的过程中遇到了一些问题，通过查阅与数据结构相关联的的一些参考书目，能够将问题解决，比如堆排序有建大堆和小堆之分，然后排序结果有降序和升序的方法，开始是是按降序输出的结果，将R[j]，R[j+1]关系做了调整后，得到升序的结果
运行界面
先输入数组A元素的个数后，回车：
再输入数组A的元素值:
后回车：
输出排好序后的A中的元素:
八、实验小结：
排序算法有很多，堆排序是其中之一，比如有冒泡排序，快速排序，插入排序等，每个算法都自己的优缺点，学习完堆排序和编写完堆排序的程序后，对堆排序有了更深层次的理解，此次编程还是遇到了些许问题，但是通过查阅图书馆相关的参考书目，能够顺利的完成本次作业。
签名：
日期：
实验成绩：
批阅日期：
升级会员 