数据结构课程设计设计说明书-内部堆排序算法的实现.doc

数据结构课程设计设计说明书内部堆排序算法的实现学生姓名学号班级计本092成绩指导教师计算机科学与技术系2011年9月9日 数据结构 课程设计评阅书题目内部堆排序算法的实现学生姓名学号指导教师评语及成绩指导教师签名： 年 月 日答辩评语及成绩 答辩教师签名： 年 月 日教研室意见总成绩： 室主任签名： 年 月 日课程设计任务书20112012学年第一学期专业： 计算机科学与技术 学号： 0918014051 姓名： 金强胜 课程设计名称： 数据结构课程设计 设计题目： 内部堆排序算法的实现 完成期限：自 2011 年 8 月 29 日至 2011 年 9 月 9 日共 2 周设计依据、要求及主要内容：堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。如关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，故它们均是堆。 大根堆和小根堆：根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆，又称最小堆。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆。注意：堆中任一子树亦是堆。以上讨论的堆实际上是二叉堆(binary heap)，大根堆排序的基本思想： 先将初始文件r1.n建成一个大根堆,此堆为初始的无序区。 再将关键字最大的记录r1(即堆顶)和无序区的最后一个记录rn交换，由此得到新的无序区r1.n-1和有序区rn，且满足r1.n-1.keysrn.key。由于交换后新的根r1可能违反堆性质，故应将当前无序区r1.n-1调整为堆。然后再次将r1.n-1中关键字最大的记录r1和该区间的最后一个记录rn-1交换，由此得到新的无序区r1.n-2和有序区rn-1.n，且仍满足关系r1.n-2.keysrn-1.n.keys，同样要将r1.n-2调整为堆。要求 ：（1）给出一个符合堆序列的一组数，能够建立大根堆和小根堆。 （2）界面友好，可操作性强。（3）能够实现数据个数的变化输入，并建立相应的堆。指导教师（签字）： 教研室主任（签字）： 批准日期： 年 月 日摘 要随着计算机技术的发展，为了查找方便，通常希望通过排序使表是按关键字有序的。本课题利用简单选择排序中的堆排序方法，通过建立大、小根堆，并对数据元素进行排序输出，实现对用户输入的一组可以组成堆的数据元素进行处理，使其按关键字排成为一个有序的序列，从而有效地提高了查找效率。关键词：堆；排序；查找 目 录1 课题描述12 设计过程22.1 流程图22.1.1函数设计思想流程图22.1.2程序流程图22.2分步程序设计72.2.1 建立堆函数72.2.2输出堆函数72.2.3输出已排序数组函数92.2.4主函数93 测试123.1第一组测试数据测试结果123.2第二组测试数据测试结果13总 结16参考资料17附 录18程序源代码181 课题描述随着计算机技术的发展，为了查找方便，通常希望计算机中的表是按关键字有序的。因为有序的顺序表可采用查找效率较高的折半查找法，而无序的表只能进行顺序查找。排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。因此，学习和研究各种排序方法是计算机工作者的重要课题之一。本课题利用简单选择排序中的堆排序方法，通过对用户输入的可以组成堆的数据元素建立大、小根堆，并将其进行排序输出，使其成为一个按关键字排序的有序序列，从而有效地提高了查找的效率。开发工具：tc 2.02 设计过程2.1 流程图2.1.1函数设计思想流程图：函数设计思想流程图如图2.1。图2.1 函数设计思想流程图2.1.2程序流程图建立大根堆函数的程序流程图如图2.2。图2.2 建立大根堆函数的程序流程图建立小根堆函数的程序流程图如图2.3。图2.3 建立小根堆函数的程序流程图输出大根堆函数的程序流程图如图2.4。图2.4 输出大根堆函数的程序流程图输出小根堆函数的程序流程图如图2.5。图2.5 输出小根堆函数的程序流程图2.2分步程序设计2.2.1 建立堆函数当运行程序，用户按照提示输入正确的信息并敲击回车键时，程序就会相应地建立出大、小根堆函数，为后续的运行做准备。程序源代码如下：/建立大根堆函数void buildbig(int *a,int i,int n) int tmp; k=i; j=2*k+1; while(j=n) if(jn & aj=aj)break; tmp=ak; ak=aj; aj=tmp; k=j; j=2*j+1; /建立小根堆函数void buildlittle(int *a,int i,int n) int tmp; k=i; j=2*k+1; while(j=n) if(jaj+1) j+; if(ak=aj)break; tmp=ak; ak=aj; aj=tmp; k=j; j=2*j+1; 2.2.2输出堆函数当计算机已经生成了相应的堆函数之后，就会自动运行此模块，将其输出。程序源代码如下：/输出大根堆函数void prnthpbig(int *a,int b1,int b2) int size; int h=0,sum=0,item=1; int i,j,cnt,start,tmp; size=b2-b1+1; while(sum=size) sum+=item; h+; item*=2; item=1; cnt=0; start=b1; tmp=1; printf(n); printf(大根堆排序如下:n); while(1) for(i=0;ih;i+) for(j=0;jh-i;j+) printf( ); for(j=0;ji+1;j+)printf( ); for(j=0;jsize-1)goto end; printf(%4d,acnt+); printf(n); tmp*=2; end: printf(n); return; /输出小根堆函数void prnthplittle(int *a,int b1,int b2) int size; int h=0,sum=0,item=1; int i,j,cnt,start,tmp; size=b2-b1+1; while(sum=size) sum+=item; h+; item*=2; item=1; cnt=0; start=b1; tmp=1; printf(n); printf(小根堆排序如下:n); while(1) for(i=0;ih;i+) for(j=0;jh-i;j+) printf( ); for(j=0;ji+1;j+)printf( ); for(j=0;jsize-1)goto end; printf(%4d,acnt+); printf(n); tmp*=2; end: printf(n); return; 2.2.3输出已排序数组函数输出已经排好的序列数据，显示每一步排序出的结果。源代码如下：/输出已排序数组函数void prntar(int *a,int b2,int len) int i; printf(已排序序列数如下:n); for(i=0;ib2;i+) printf( ); for(i=b2;i=len;i+) printf(%3d,ai); printf(n); 2.2.4主函数运行程序时，在用户数据输入正确之后，主函数运行并调用相应的函数，完成全部任务。源代码如下：main() int a50; int i; int tmp; int sum; int len; printf(n); printf( 计本092 金强胜 0918014051 n);printf( n);printf(（数据结构课程设计）n); printf( 内部堆排序算法的实现 n); printf(n); printf(请您输入欲排序数的个数,并以回车键结束:); scanf(%3d,&len); printf(n); printf(请输入能组建堆的无序序列数的值,并以回车键结束:n ); for(i=0;ilen;i+) scanf(%3d,&ai); tmp=1;sum=0; while(sum+tmp=0;i-) buildbig(a,i,len-1); prnthpbig(a,0,len-1); /改建堆 for(i=0;i=0;i-) buildlittle(a,i,len-1); prnthplittle(a,0,len-1);/改建堆 for(i=0;ilen-1;i+) tmp=a0; a0=alen-1-i; alen-1-i=tmp; buildlittle(a,0,len-2-i); prnthplittle(a,0,len-2-i); prntar(a,len-1-i,len-1); printf(nn); printf(小根堆排序的最后结果如下:n); prnt(a,len); printf(n谢谢您的使用，请按任意键结束!n); return 0;3 测试3.1第一组测试数据测试结果测试数据：96 83 27 38 11 9主界面和大根堆排序的部分过程如图3.1。图3.1 主界面和大根堆排序的部分过程大根堆排序的最后结果如图3.2。图3.2 大根堆排序的最后结果大根堆排序结束，小根堆排序的开始及部分过程如图3.3。图3.3 大根堆排序结束，小根堆排序的开始及部分过程小根堆排序的最后结果及程序运行结束如图3.4。图3.4 小根堆排序的最后结果及程序运行结束3.2第二组测试数据测试结果测试数据：12 36 24 85 47 30 53 91主界面和大根堆排序的部分过程如图3.5。图3.5 主界面和大根堆排序的部分过程大根堆排序的最后结果如图3.6。图3.6 大根堆排序的最后结果大根堆排序结束，小根堆排序的开始及部分过程如图3.7。图3.7 大根堆排序结束，小根堆排序的开始及部分过程小根堆排序的最后结果及程序运行结束如图3.8。图3.8 小根堆排序的最后结果及程序运行结束总 结两周的课程设计结束了，过程是艰辛的，但是收获也是很大的。我主要是应用了所学习的c和c+编程语言和软件，以及数据结构的相关知识，并参考相关书籍以及请教老师和同学，综合起来才完成了这次课程设计。本次课程设计让我把以前学习到的知识得到巩固和进一步的提高认识，对已有知识有了更进一步的理解和认识。在课程设计中，我碰到了很多的问题，通过查阅相关书籍，资料，通过自己钻研，同时特别是得到了老师的谆谆教导，给予了我很大的帮助，不仅给了我思路上的开阔，还让我认识到了自己对以前所学知识的不足方面。随着社会发展，计算机的迅速普及以及飞速发展，掌握计算机方面相关的知识越来越迫切，掌握一定的计算机基础技术已经成为一大必备技能。排序是计算机程序设计中极其重要的一部分，是计算机程序设计中的一个重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。学习和研究各种排序方法是计算机工作者的重要课题之一。堆排序是选择排序中的一种，它只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。堆排序方法对记录较少的文件不值得提倡，但对于较大的文件是很有效的。堆排序在最坏的情况下，其时间复杂度也为o（nlogn）。相对于快速排序来说，这是最大的优点。这次课程设计我主要应用所学，通过在c和c+编程环境下，实现了对符合堆的无序序列进行排序。 当然，通过这次课程设计，我也发现了自身的很多不足之处，在以后的学习中，我会不断的完善自我，不断进取，使自己有一个大的发展。参考资料1 严蔚敏，吴伟民.数据结构（c语言版）.北京.清华大学出版社.2007.2 罗建军，朱丹君，顾刚，刘路放.c+程序设计教程（第二版）.北京.高等教育出版社.2007.3 谭浩强.c语言程序设计教程.高等教育出版社.2004.4何钦铭，颜晖c.语言程序设计.北京.高等教育出版社.2008.5al kelley,ira pohl.c语言教程m.4版.徐波，译.北京：机械工业出版社.2007.6kochan s g.c语言编程m.3版.张小潘,译.北京：电子工业出版社，2006.附 录程序源代码：#includeint k,j;/建立大根堆函数void buildbig(int *a,int i,int n) int tmp; k=i; j=2*k+1; while(j=n) if(jn & aj=aj)break; tmp=ak; ak=aj; aj=tmp; k=j; j=2*j+1; /建立小根堆函数void buildlittle(int *a,int i,int n) int tmp; k=i; j=2*k+1; while(j=n) if(jaj+1) j+; if(ak=aj)break; tmp=ak; ak=aj; aj=tmp; k=j; j=2*j+1; /输出数组函数void prnt(int *a,int n) int i; printf(n); for(i=0;in;i+) printf(%3d,ai); printf(n);/输出大根堆函数void prnthpbig(int *a,int b1,int b2) int size; int h=0,sum=0,item=1; int i,j,cnt,start,tmp; size=b2-b1+1; while(sum=size) sum+=item; h+; item*=2; item=1; cnt=0; start=b1; tmp=1; printf(n); printf(大根堆排序如下:n); while(1) for(i=0;ih;i+) for(j=0;jh-i;j+) printf( ); for(j=0;ji+1;j+)printf( ); for(j=0;jsize-1)goto end; printf(%4d,acnt+); printf(n); tmp*=2; end: printf(n); return; /输出小根堆函数void prnthplittle(int *a,int b1,int b2) int size; int h=0,sum=0,item=1; int i,j,cnt,start,tmp; size=b2-b1+1; while(sum=size) sum+=item; h+; item*=2; item=1; cnt=0; start=b1; tmp=1; printf(n); printf(小根堆排序如下:n); while(1) for(i=0;ih;i+) for(j=0;jh-i;j+) printf( ); for(j=0;ji+1;j+)printf( ); for(j=0;jsize-1)goto end; printf(%4d,acnt+); printf(n); tmp*=2; end: printf(n); return; /输出已排序数组函数void prntar(int *a,int b2,int len) int i; printf(已排序序列数如下:n); for(i=0;ib2;i+) print