数据结构课程设计内部排序之堆排序.docx
- 文档编号:14838667
- 上传时间:2023-06-27
- 格式:DOCX
- 页数:26
- 大小:591.20KB
数据结构课程设计内部排序之堆排序.docx
《数据结构课程设计内部排序之堆排序.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计内部排序之堆排序.docx(26页珍藏版)》请在冰点文库上搜索。
数据结构课程设计内部排序之堆排序
数据结构课程设计
设计说明书
内部排序之堆排序的实现
学生姓名
罗通
学号
1118014124
班级
计本1104班
成绩
指导教师
林勇
数学与计算机科学学院
2013年9月9日
课程设计任务书
2013—2014学年第一学期
课程设计名称:
数据结构课程设计
课程设计题目:
内部堆排序算法的实现
完 成 期 限:
自 2013年 9月9日至 2013年 9月 21 日共 2 周
设计内容:
1.任务说明
堆排序是数据结构中内排序部分的重点知识。
堆分为大顶堆和小顶堆。
堆排序的过程主要解决两个问题:
(1)把无序序列建成一个堆;
(2)输出堆顶元素后,重新将剩余元素调整成新堆。
本课程设计主要完成的核心内容即为此。
按以下的要求运用C/C++结构体、指针、数据结构等基知识编程实现。
2.要求
1)问题分析和任务定义:
根据设计题目的要求,充分地分析和理解问题,明确问题要求做什么?
2)逻辑设计:
写出抽象数据类型的定义,各个主要模块的算法,并画出模块之间的调用关系图;
3)详细设计:
定义相应的存储结构并写出各函数的伪码算法。
4)程序编码:
把详细设计的结果进一步求精为程序设计语言程序。
5)程序调试与测试:
采用自底向上,分模块进行,即先调试低层函数。
6)结果分析:
程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。
算法的时间、空间复杂性分析;
7)编写课程设计报告;
3.参考资料
指导教师:
林勇教研室负责人:
曹阳
课程设计评阅
评语:
指导教师签名:
年月日
摘要
为了查找方便,通常希望通过排序使表成为按键字有序的。
本课题利用简单排序的堆排序方法,通过建立大根堆,并对元素进行输出,实现用户输入的一组可以组成堆的数据元素进行处理,使其按关键字排成一个有序的序列,从而有效的提高了查找效率。
再加上界面友好、操作简单,使其更加好用。
关键词:
堆排序查找流程控制
1.课题描述-----------------------------------------------------
2.需求分析-----------------------------------------------------
2.0算法分析-----------------------------------------------
2.1抽象数据类型定义---------------------------------------
2.2程序设计流程图-----------------------------------------
3.各函数功能实现及调用关系------------------------------------
3.1各函数功能实现------------------------------------------
3.2各函数之间的调用关系-----------------------------------
4.主代码------------------------------------------------------
5.程序运行测试与结果分析---------------------------------------
5.1函数功能检验与各步运行结果的说明(图)-----------------
5.2出错状况的解决(图)-----------------------------------
5.3时间复杂度与空间复杂度--------------------------------
6.总结---------------------------------------------------------
参考文献-------------------------------------------------------
1课题描述
在现在带生活的各个领域里,人们为了查找方便,通常希望计算机中的表是按关键字有序的。
因此排序就成了计算机程序设计中的一种重要操作。
本课题利用简单选择排序中的堆排序方法,通过对用户输入的可以组成堆的数据元素建立大、小根堆,并将其进行排序输出,使其成为一个按关键字排序的有序序列,从而有效地提高了查找的效率。
开发工具:
vc++6.0
2问题分析
2.0算法分析
堆的定义如下:
n个元素的序列{k1,k2,......,kn}当且仅当满足下关系时,称堆。
Ki<=k2i;ki<=k2i+1或者ki=>k2i;ki=>k2i+1
(i=1,2,3.....,[n/2])
若将和此序列对应的一维数组(即以一维数组作为数列的存储结构)看成是一个完全二叉树,则堆的含义表明,完全二叉树中所有的非终端节点的值均不小于(或不大于)其左右孩子节点的值,由此,若序列{k1,k2,......,kn}是堆,则堆顶元素必为序列中n个元素的最大值。
2.1抽象数据类型定义
ADTHeapSort{
数据对象:
D={ki|ki属于Elemset,i=1,2,3........,n,n=>0};
数据关系:
R1={
};
基本操作:
voidSCANF(Heap*list);
操作结果:
输入的一组数据存入顺序表中
voidHeapAdjustlittle(Heap*list,ints,intm);
初始条件:
list中存有一组无序数列
操作结果:
将list中的无序数列调整为一个小顶堆
voidHeapSortlittle(Heap*list);
操作结果:
把调整好的小顶堆进行排序并进行再调整
voidHeapAdjustbig(Heap*list,ints,intm);
初始条件:
list中存有一组无序数列
操作结果:
将list中的无序数列调整为一个大顶堆
voidHeapSortbig(Heap*list);
操作结果:
把调整好的小顶堆进行排序并进行再调整
voidPRINTF1(Heap*list);
操作结果:
将排好的或者正在排列的序列进行堆型输出
voidPRINTF2(Heap*list);
操作结果:
输出最终升序或者降序排序结果
}ADTHeapSort
2.2程序设计流程图(以大顶堆的设计为例)
2.2.1整体设计思想流程图:
图2.1整体设计思想流程图
2.2.2函数设计流程图
建堆函数HeapAdjust:
堆的定义如下:
n个元素的序列{k1,k2,......,kn}当且仅当满足下关系时,称堆。
Ki<=k2i;ki<=k2i+1或者ki=>k2i;ki=>k2i+1
(i=1,2,3.....,[n/2])
若将和此序列对应的一维数组(即以一维数组作为数列的存储结构)看成是一个完全二叉树,则堆的含义表明,完全二叉树中所有的非终端节点的值均不小于(或不大于)其左右孩子节点的值,由此,若序列{k1,k2,......,kn}是堆,则堆顶元素必为序列中n个元素的最大值。
建立大顶堆函数的程序流程图如图2.2。
图2.2建立大顶堆函数的程序流程图
输出堆形函数PRINTF1:
在堆排序的函数中,结果用堆型的动态变化来反映无疑是最好的。
因此,就要设计良好的流程控制来反映出程序运行结果中的堆型。
输出大顶堆函数的程序流程图如图2.3。
图2.3输出大顶堆函数的程序流程图
3各函数功能的实现
3.1各函数的功能实现
//大顶堆的建立
voidHeapAdjustbig(Heap*list,ints,intm)
{
intj;
Heaprc;
rc=list[s];
for(j=2*s;j<=m;j*=2)
{
if(j ++j; if(! (rc.key break; list[s]=list[j]; s=j; } list[s]=rc; } //小顶堆的建立 voidHeapAdjustlittle(Heap*list,ints,intm) { intj; Heaprc; rc=list[s]; for(j=2*s;j<=m;j*=2) { if(j ++j; if(! (rc.key>list[j].key)) break; list[s]=list[j]; s=j; } list[s]=rc; //输出堆函数(输出堆型) voidPRINTF1(Heap*list) { inth=0,sum=0,item=1; intcnt=1,tmp=1; while(sum<=list[0].key) { sum+=item; h++; item*=2; }//求出堆所对应的完全二叉树的高度h。 printf("-------------------------------------------------------------\n"); printf("堆排序堆型如下\n"); while (1) { for(inti=0;i { for(intj=0;j printf(""); for(j=0;j { if(cnt>list[0].key)gotoend; printf("%5d",list[cnt++]); } printf("\n"); tmp*=2; } } end: printf("\n"); } //输出已排序数组函数 voidPRINTF2(Heap*list) { printf("INTHEEND最终经过堆排序后的序列为: "); for(inti=1;i<=list[0].key;i++) { printf("%d",list[i].key); } printf("\n"); } 3.2各函数之间的调用关系 箭头指向主调函数,箭尾为被调函数 4.主代码 #include #include typedefstructNODE { intkey; }Heap; voidSCANF(Heap*list); voidHeapAdjustlittle(Heap*list,ints,intm); voidHeapAdjustbig(Heap*list,ints,intm); voidHeapSortlittle(Heap*list); voidHeapSortbig(Heap*list); voidPRINTF1(Heap*list); voidPRINTF2(Heap*list); //桌面显示个人信息 voiddesktop() { printf("\t\t\t2013-2014年计算机系课程设计"); printf("\n\n"); printf("\t\t@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\n\n"); printf("\t\t@@@@@@班级: 计本1104班@@@@@@@@\n\n"); printf("\t\t@@@@@@姓名: 罗通@@@@@@@@\n\n"); printf("\t\t@@@@@@学号: 1118014124@@@@@@@@\n\n"); printf("\t\t@@@@@@课题: 内部排序之堆排序@@@@@@@@\n\n"); printf("\t\t@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\n\n"); } //用顺序表来存储堆 voidSCANF(Heap*list) { printf("请输入你要排序的序列的个数: "); scanf("%d",&list[0].key); if(list[0].key>15) { printf("对不起,现在暂时只分配了表长为15的顺序表! \n\n"); printf("请输入小于15的值,或者手动将主函数里分配表长改为你想要的值! \n\n"); exit(0); } printf("\n"); printf("请输入你要排序的数列: "); for(inti=1;i<=list[0].key;i++) { scanf("%d",&list[i].key); if(sizeof(1==list[i].key)) { printf("请输入正确的数据(整形数字)。 \n\n"); exit(0); } else printf("\t"); } printf("\n"); } //调整堆为大顶堆 voidHeapAdjustbig(Heap*list,ints,intm) { intj; Heaprc; rc=list[s]; for(j=2*s;j<=m;j*=2) { if(j ++j; if(! (rc.key break; list[s]=list[j]; s=j; } list[s]=rc; } //输出堆顶元素开始进行堆排序 voidHeapSortbig(Heap*list) { Heapp; for(inti=list[0].key/2,m=1;i>0;--i,++m) { HeapAdjustbig(list,i,list[0].key); printf("经过%d次调整的堆序列为: ",m); for(intj=1;j<=list[0].key;j++) { printf("%d",list[j].key); } printf("相应的堆形为: \n"); PRINTF1(list); printf("\n\n"); } for(i=list[0].key;i>1;--i) { p=list[1]; list[1]=list[i]; list[i]=p; HeapAdjustbig(list,1,i-1); } } //调整堆为小顶堆 voidHeapAdjustlittle(Heap*list,ints,intm) { intj; Heaprc; rc=list[s]; for(j=2*s;j<=m;j*=2) { if(j ++j; if(! (rc.key>list[j].key)) break; list[s]=list[j]; s=j; } list[s]=rc; } //输出堆顶元素开始进行堆排序 voidHeapSortlittle(Heap*list) { Heapp; for(inti=list[0].key/2,m=1;i>0;--i,++m) { HeapAdjustlittle(list,i,list[0].key); printf("经过%d次调整的堆序列为: ",m); for(intj=1;j<=list[0].key;j++) { printf("%d",list[j].key); } printf("相应的堆形为: \n"); PRINTF1(list); printf("\n\n"); } for(i=list[0].key;i>1;--i) { p=list[1]; list[1]=list[i]; list[i]=p; HeapAdjustlittle(list,1,i-1); } } //输出堆 voidPRINTF1(Heap*list) { inth=0,sum=0,item=1; intcnt=1,tmp=1; while(sum<=list[0].key) { sum+=item; h++; item*=2; } printf("-----------------------------------------------------------------\n"); printf("堆排序堆型如下\n"); while (1) { for(inti=0;i { for(intj=0;j printf(""); for(j=0;j { if(cnt>list[0].key)gotoend; printf("%5d",list[cnt++]); } printf("\n"); tmp*=2; } } end: printf("\n"); } //输出最后排好的堆序列 voidPRINTF2(Heap*list) { printf("INTHEEND最终经过堆排序后的序列为: "); for(inti=1;i<=list[0].key;i++) { printf("%d",list[i].key); } printf("\n"); } //主函数 voidmain() { Heaptmp; desktop(); Heaplist[15]; SCANF(list); printf("--------------------------------------------\n"); printf("请注意! ! ! 现在是大顶堆的升序排序...........\n"); printf("--------------------------------------------\n\n\n"); HeapSortbig(list); printf("-----现在按照步骤来输出已经排好的序列-----\n\n\n"); for(inti=1;i<=list[0].key;i++) { printf("经过第%d步调整,现在的已排序列是: ",i); for(intj=1;j { printf("%d",list[j].key); } printf("\n\n"); } printf("\n\n"); PRINTF2(list); printf("--------------------------------------------\n"); printf("请注意! ! ! 现在是小顶堆的降序排序...........\n"); printf("--------------------------------------------\n\n\n"); HeapSortlittle(list); printf("-----现在按照步骤来输出已经排好的序列------\n\n\n"); for(i=1;i<=list[0].key;i++) { printf("经过第%d步调整,现在的已排序列是: ",i); for(intj=1;j printf("%d",list[j].key); printf("\n\n"); } printf("\n\n"); PRINTF2(list); } 5.程序运行测试与结果分析 5.1函数功能检验与各步运行结果说明(图) 5.1.1输入你要排列的数列 5.1.2输入数列的大顶堆建立与调整 5.1.3大顶堆的分布排序结果 5.1.4大顶堆的升序排序的最终结果 5.1.5输入序列堆排序与调整 5.1.6小顶堆的分布排序结果 5.1.7小顶堆的升序排序的最终结果 5.2出错情况的分析 情况一: 输入的数列中元素个数超过初始上限 解决方法: 情况二: 在输入数据时,不小心输入了不可排序的字符 解决方法: 5.3时间复杂度与空间复杂度分析 堆排序是选择排序中的一种,它只需要一个记录大小的辅助空间,每个待排序的记录仅占有一个存储空间。 堆排序方法对记录较少的文件不值得提倡,但对于较大的文件是很有效的。 堆排序在最坏的情况下,其时间复杂度也为O(nlogn)。 相对于快速排序来说,这是最大的优点。 6总结 学期初的课程设计实践让我把以前学习到的知识得到巩固和进一步的提高认识,对已有知识有了更进一步的理解和认识。 在课程设计中,我碰到了很多的问题,比如说: 在函数PRINTF1(LIST)中,进行输出大顶堆堆型时进行的流程控制。 while (1) { for(inti=0;i { for(intj=0;j printf(""); for(j=0;j { if(cnt>list[0].key)gotoend; printf("%5d",list[cnt++]); } printf("\n"); tmp*=2; } } end: printf("\n"); 这个流程控制函数在设计的过程中因为要得到一个理想的堆的形状并且在输出结果中呈现,所以要进行不断的进行调试。 过程比较枯燥。 还有在排好了一定顺序后,剩下的堆元素进行调整的函数HeapAdjust(list),也是要花一些时间来好好试数的。 最终,通过查阅相关书籍
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 内部 排序