堆排序实验报告.docx
- 文档编号:16878620
- 上传时间:2023-07-19
- 格式:DOCX
- 页数:9
- 大小:116.95KB
堆排序实验报告.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中的元素: 八、实验小结: 排序算法有很多,堆排序是其中之一,比如有冒泡排序,快速排序,插入排序等,每个算法都自己的优缺点,学习完堆排序和编写完堆排序的程序后,对堆排序有了更深层次的理解,此次编程还是遇到了些许问题,但是通过查阅图书馆相关的参考书目,能够顺利的完成本次作业。 签名: 日期: 实验成绩: 批阅日期:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 排序 实验 报告