数据结构课程设计(内部排序之堆排序)

数据结构课程设计设计说明书内部排序之堆排序的实现学生姓名罗通学号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.总结---------------------------------------------------------参考文献-------------------------------------------------------11课题描述在现在带生活的各个领域里，人们为了查找方便，通常希望计算机中的表是按关键字有序的。因此排序就成了计算机程序设计中的一种重要操作。本课题利用简单选择排序中的堆排序方法，通过对用户输入的可以组成堆的数据元素建立大、小根堆，并将其进行排序输出，使其成为一个按关键字排序的有序序列，从而有效地提高了查找的效率。开发工具：vc++6.022问题分析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={ki,k2i,k2i+1|Ki=k2i;ki=k2i+1或ki=k2i;ki=k2i+1}；基本操作：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);操作结果：输出最终升序或者降序排序结果}ADTHeapSort32.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个元素的最大值。4建立大顶堆函数的程序流程图如图2.2。图2.2建立大顶堆函数的程序流程图输出堆形函数PRINTF1:在堆排序的函数中，结果用堆型的动态变化来反映无疑是最好的。因此，就要设计良好的流程控制来反映出程序运行结果中的堆型。输出大顶堆函数的程序流程图如图2.3。5图2.3输出大顶堆函数的程序流程图63各函数功能的实现3.1各函数的功能实现//大顶堆的建立voidHeapAdjustbig(Heap*list,ints,intm){intj;Heaprc;rc=list[s];for(j=2*s;j=m;j*=2){if(jm&&(list[j].keylist[j+1].key))++j;if(!(rc.keylist[j].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(jm&&(list[j].keylist[j+1].key))++j;if(!(rc.keylist[j].key))break;list[s]=list[j];s=j;}list[s]=rc;7//输出堆函数(输出堆型)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;ih;i++){for(intj=0;jh-i;j++)printf();for(j=0;jtmp;j++){if(cntlist[0].key)gotoend;printf(%5d,list[cnt++]);}printf(\n);tmp*=2;}}end:printf(\n);}//输出已排序数组函数voidPRINTF2(Heap*list){printf(INTHEEND最终经过堆排序后的序列为：);8for(inti=1;i=list[0].key;i++){printf(%d,list[i].key);}printf(\n);}3.2各函数之间的调用关系箭头指向主调函数，箭尾为被调函数94.主代码#includestdio.h#includestdlib.htypedefstructNODE{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].key15){10printf(对不起，现在暂时只分配了表长为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);}elseprintf(\t);}printf(\n);}//调整堆为大顶堆voidHeapAdjustbig(Heap*list,ints,intm){intj;Heaprc;rc=list[s];for(j=2*s;j=m;j*=2){if(jm&