数据结构课程设计.

《数据结构课程设计.》由会员分享，可在线阅读，更多相关《数据结构课程设计.（25页珍藏版）》请在装配图网上搜索。

1、茨筋寒工摩整数据结构课程设计设计说明书内部排序之堆排序的实现学生姓名罗通学号-1118014124班级计本1104班成绩指导教师林勇数学与计算机科学学院课程设计任务书2013 2014学年第一学期课程设计名称：数据结构课程设计课程设计题目：内部堆排序算法的实现完成期限：自2013年9月9日至2013年9月21日共2周设计内容：1. 任务说明堆排序是数据结构中内排序部分的重点知识。堆分为大顶堆和小顶堆。堆排序的过程主要解决两个问题：（1）把无序序列建成一个堆；（2 ）输出堆顶元素后，重新将剩余元素调整成新堆。本课程设计主要完成的核心内容即为此。按以下的要求运用C/ C+结构体、指针、数据结构等基

2、知识编程实现。2. 要求1 ）问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？2）逻辑设计：写出抽象数据类型的定义，各个主要模块的算法，并画出模块之间的调用关系图；3）详细设计：定义相应的存储结构并写出各函数的伪码算法。4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。5）程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法 的时间、空间复杂性分析；7）编写课程设计报告；3参考资料指导教师：林勇教研室负责人：曹阳课程设计评阅评语:指导教师签名:摘要为了查找方

3、便，通常希望通过排序使表成为按键字有序的。本课题利用简单排序的堆 排序方法，通过建立大根堆，并对元素进行输出，实现用户输入的一组可以组成堆的数据 元素进行处理，使其按关键字排成一个有序的序列，从而有效的提高了查找效率。再加上 界面友好、操作简单，使其更加好用。关键词:堆 排序查找流程控制1. 课题描述 2. 需求分析 2.0 算法分析 2.1 抽象数据类型定义 2.2 程序设计流程图 3. 各函数功能实现及调用关系 3.1 各函数功能实现 3.2 各函数之间的调用关系 4. 主代码 5. 程序运行测试与结果分析 5.1 函数功能检验与各步运行结果的说明（图） 5.2 出错状况的解决（图） 5.

4、3 时间复杂度与空间复杂度 6. 总结 参考文献 1 课题描述在现在带生活的各个领域里， 人们为了查找方便， 通常希望计算机中的表是按关键字有 序的。因此排序就成了计算机程序设计中的一种重要操作。本课题利用简单选择排序中的堆排序方法， 通过对用户输入的可以组成堆的数据元素建 立大、小根堆，并将其进行排序输出，使其成为一个按关键字排序的有序序列，从而有效地 提高了查找的效率。开发工具： vc+6.02 问题分析2.0 算法分析堆的定义如下：n 个元素的序列 k1,k2,kn当且仅当满足下关系时，称堆。Ki=k2i ;kik2i; ki=k2i+1(i = 1,2,3,n/2)若将和此序列对应的一

5、维数组 (即以一维数组作为数列的存储结构) 看成是一个完全二叉树， 则堆的含义表明， 完全二叉树中所有的非终端节点的值均不小于 (或不大于) 其左右孩子节 点的值，由此，若序列k1,k2,kn是堆，则堆顶元素必为序列中n个元素的最大值。2.1 抽象数据类型定义ADT HeapSort数据对象 : D=ki|ki 属于 Elemset ， i = 1,2,3,n,n=0;数据关系： R1=|Ki=k2i;kik2i;ki=k2i+1；基本操作：void SCANF(Heap* list);操作结果：输入的一组数据存入顺序表中void HeapAdjustlittle(Heap* list,int

6、 s,int m);初始条件： list 中存有一组无序数列操作结果：将 list 中的无序数列调整为一个小顶堆void HeapSortlittle(Heap*list);操作结果：把调整好的小顶堆进行排序并进行再调整void HeapAdjustbig(Heap* list,int s,int m);初始条件： list 中存有一组无序数列操作结果：将 list 中的无序数列调整为一个大顶堆void HeapSortbig(Heap*list);操作结果：把调整好的小顶堆进行排序并进行再调整void PRINTF1(Heap*list);操作结果：将排好的或者正在排列的序列进行堆型输出vo

7、id PRINTF2(Heap*list);操作结果：输出最终升序或者降序排序结果ADT HeapSort2.2程序设计流程图（以大顶堆的设计为例）221整体设计思想流程图:图2.1整体设计思想流程图函数设计流程图建堆函数HeapAdjust :堆的定义如下：n个元素的序列k1,k2,.,kn当且仅当满足下关系时，称堆。Ki=k2i ;kik2i; ki=k2i+1（i = 1,2,3.,n/2）若将和此序列对应的一维数组（即以一维数组作为数列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有的非终端节点的值均不小于（或不大于）其左右孩子节点的值，由此，若序列k1,k2,.,k

8、n是堆,则堆顶元素必为序列中n个元素的最大值。建立大顶堆函数的程序流程图如图2.2。/ tc = lists j = 21 7/ j+ /图2.2建立大顶堆函数的程序流程图输出堆形函数PRINTF1:在堆排序的函数中， 结果用堆型的动态变化来反映无疑是最好的。因此，就要设计良好的流程控制来反映出程序运行结果中的堆型。输出大顶堆函数的程序流程图如图2.3。3 各函数功能的实现3.1 各函数的功能实现/ 大顶堆的建立void HeapAdjustbig(Heap* list,int s,int m)int j;Heap rc;rc = lists;for(j=2*s;j=m;j*=2)if(jm&

9、(listj.keylistj+1.key) +j;if(!(rc.keylistj.key)break;lists = listj; s = j;lists = rc;/ 小顶堆的建立void HeapAdjustlittle(Heap* list,int s,int m)int j;Heap rc;rc = lists;for(j=2*s;j=m;j*=2)if(jlistj+1.key) +j;if(!(rc.keylistj.key)break;lists = listj;s = j;lists = rc;/ 输出堆函数 ( 输出堆型 ) void PRINTF1(Heap* list

10、) int h=0,sum=0,item=1; int cnt=1,tmp=1; while(sum=list0.key) sum+=item; h+;item*=2; / 求出堆所对应的完全二叉树的高度 h 。printf(n);printf( 堆排序堆型如下 n);while(1)for(int i=0;ih;i+)for(int j=0;jh-i;j+)printf( );for(j=0;jlist0.key)goto end; printf(%5d,listcnt+);printf(n);tmp*=2;end:printf(n);/ 输出已排序数组函数void PRINTF2(Heap

11、* list)printf(IN THE END 最终经过堆排序后的序列为： );for(int i=1;i=list0.key;i+)prin tf(%d ,listi.key);prin tf(n);3.2各函数之间的调用关系4. 主代码#include#includetypedef struct NODE int key;Heap;void SCANF(Heap* list);void HeapAdjustlittle(Heap* list,int s,int m); void HeapAdjustbig(Heap* list,int s,int m); void HeapSortlit

12、tle(Heap*list);void HeapSortbig(Heap*list);void PRINTF1(Heap*list);void PRINTF2(Heap*list);/ 桌面显示个人信息void desktop()年计算机系课程设计 );printf(ttt2013-2014 printf(nn);printf(ttnn);printf(tt班级：计本 1104 班printf(tt姓名：罗通printf(tt学号：1118014124printf(tt课题：内部排序之堆排序nn);nn); nn); nn);printf(ttnn);/ 用顺序表来存储堆void SCANF(

13、Heap* list)printf( 请输入你要排序的序列的个数： );scanf(%d,&list0.key);if(list0.key 15)printf( 对不起，现在暂时只分配了表长为 15 的顺序表！ nn);printf( 请输入小于 15 的值，或者手动将主函数里分配表长改为你想要的 值!nn ”)；exit(0);printf(n)；printf( 请输入你要排序的数列： )； for(int i=1；i=list0.key；i+) scanf(%d,&listi.key)； if(sizeof(1 = listi.key) printf( 请输入正确的数据(整形数字)。 nn

14、)； exit(0)；else printf(t)； printf(n)；/ 调整堆为大顶堆void HeapAdjustbig(Heap* list,int s,int m)int j；Heap rc； rc = lists； for(j=2*s；j=m；j*=2) if(jm&(listj.keylistj+1.key)+j； if(!(rc.key0;-i,+m)HeapAdjustbig(list,i,list0.key);:,m);printf(经过 %d 次调整的堆序列为for(int j=1;j1;-i)p = list1;list1 = listi; listi = p;Hea

15、pAdjustbig(list,1,i-1);/ 调整堆为小顶堆void HeapAdjustlittle(Heap* list,int s,int m)int j;Heap rc;rc = lists;for(j=2*s;j=m;j*=2)if(jlistj+1.key)+j;if(!(rc.keylistj.key)break;lists = listj; s = j; lists = rc;/ 输出堆顶元素开始进行堆排序 void HeapSortlittle(Heap*list)Heap p;for(int i=list0.key/2,m=1;i0;-i,+m) :,m);HeapAd

16、justlittle(list,i,list0.key); printf( 经过 %d 次调整的堆序列为 for(int j=1;j1;-i)p = list1; list1 = listi; listi = p;HeapAdjustlittle(list,1,i-1);/ 输出堆void PRINTF1(Heap* list)int h=0,sum=0,item=1;int cnt=1,tmp=1;while(sum=list0.key)sum+=item; h+; item*=2;printf(n);printf( 堆排序堆型如下 n);while(1)for(int i=0;ih;i+)

17、for(int j=0;jh-i;j+)printf( );for(j=0;jlist0.key)goto end; printf(%5d,listcnt+);printf(n);tmp*=2;end:printf(n);/ 输出最后排好的堆序列void PRINTF2(Heap* list)printf(IN THE END最终经过堆排序后的序列为： );for(int i=1;i=list0.key;i+)printf(%d ,listi.key);printf(n);/ 主函数void main()Heap tmp;desktop();Heap list15;SCANF(list);pr

18、intf(n);printf( 请注意 ! ! ! 现在是大顶堆的升序排序 printf(nnn);HeapSortbig(list);printf( 现在按照步骤来输出已经排好的序列for(int i=1;i=list0.key ;i+)printf( 经过第 %d 步调整，现在的已排序列是： for(int j=1;ji+1;j+)printf(%d ,listj.key );printf(nn);printf(nn);PRINTF2(list);printf(n);printf( 请注意 ! ! ! 现在是小顶堆的降序排序 printf(nnn);HeapSortlittle(list)

19、;printf( 现在按照步骤来输出已经排好的序列for( i=1;i=list0.key ;i+)printf( 经过第 %d 步调整，现在的已排序列是： for(int j=1;ji+1;j+) printf(%d ,listj.key );printf(nn);printf(nn);PRINTF2(list);n);nnn);,i);n);nnn);,i);5.程序运行测试与结果分析5.1函数功能检验与各步运行结果说明(图)输入你要排列的数列2813亠吨年计U机系谯程设计pppppdpp ppp ppppppptipFpp e(?(?ppp(*pp woE褪住涎班级*计本丄询斗班昶輕解姓

20、名；罗il03盹蝕G啊 ppee 学号*ljL18H1412ppppppepeecoee课題=内部排存之堆排序 peewwepeeceu euu卩卩哄*(?叫叫* e hcpb 卩 b?r ee情谕人你要擀序的序列的个敕B洁输人你妥排隔的釈列* 1 3 5 0 1S 33输入数列的大顶堆建立与调整大顶堆的分布排序结果现在按照步理来辅出已经排好的序列经过第1步调整现在的己排佯列JS，3经过黑去步调整，现在的已排序列杲a 1经过第日步调整*现在的已推序列杲1 a 1 3经过第马步调鑿*现在的已排序列晶0 1 3 S轻过第吕步调整，现在的己排序列杲t a 1 3 s经过第吕步调整，现在的已排序列是;

21、a 1 3 s , 15轻过第啦调鉴现在酊已排序列是0 1 3 S15 21L经过第B步调8L现在的已排序?|杲：0 13 s 9152133大顶堆的升序排序的最终结果TH IHE END最终经过堆排序后的序列为* 0 1359152133输入序列堆排序与调整谕注意t T规在是小他举晒降序排序眸包（抿调空的堆序列为油135*152133相应的堆丹惓耕仔堆型如下5912133经过2次调堂的堆序列汨洱13?152133相应的堆形拘工堆排序堆型如Fa17S 3152133经过2次週整的堆序列为诲13 E 9 l S1 33 相用的堆形询01391&2113经过峙次谓整的堆序列为询11 S 15 K1

22、 33 相应的菇形为:滩排序堆型如下591521711小顶堆的分布排序结果一一现在按晚步球来輪出已经排好的仔列经过第直步调整.现在的己排序列是| 33经过第2步调整现在的己排序列是，33 21经过第3步调螫.现在的已排序列是|阳21 15经过執步调整.现在的已排序列晶33 21 15 9经过第石步调整.现在的已排序33 21 15 3 5经过第&步鞠4L现在的己排序列是33211595经过第丁步關整.现在的己排序是：3321 1S ?5经过第目步调整.现在的己排序5U是I 33 21 1S ? 5小顶堆的升序排序的最终结果严THE EHD最终经过堆排序启的序列为.32 21 IS 9 S 3

23、1 Pmss Any ke y la co nt dntie5.2出错情况的分析情况一：输入的数列中元素个数超过初始上限解决方法：精蓉黔勲証的顺序表！晴输入小于15的值.或者羊动将主函故里分配喪长改为你標蔓的值号情况二：在输入数据时，不小心输入了不可排序的字符 解决方法：请输入你琴誹序的序列的个数，8主fl?列鑒3)1ipess any Jkew eentiftiie5.3时间复杂度与空间复杂度分析堆排序是选择排序中的一种，它只需要一个记录大小的辅助空间，每个待排序的记录仅占 有一个存储空间。堆排序方法对记录较少的文件不值得提倡，但对于较大的文件是很有效的。堆排序在最坏的情况下，其时间复杂度也

24、为0 (nlogn)。相对于快速排序来说，这是最大的优点。6 总结学期初的课程设计实践让我把以前学习到的知识得到巩固和进一步的提高认识， 对已有知 识有了更进一步的理解和认识。在课程设计中，我碰到了很多的问题，比如说：在函数 PRINTF1(LIST) 中，进行输出大顶堆堆型时进行的流程控制。while(1)for(int i=0;ih;i+)for(int j=0;jh-i;j+)printf( );for(j=0;jlist0.key)goto end; printf(%5d,listcnt+);printf(n);tmp*=2;end:printf(n); 这个流程控制函数在设计的过程中

25、因为要得到一个理想的堆的形状并且在输出结果中呈现， 所以要进行不断的进行调试。过程比较枯燥。还有在排好了一定顺序后，剩下的堆元素进行调整的函数HeapAdjust (list )，也是要花一些时间来好好试数的。最终，通过查阅相关书籍，资料，通过自己钻研，同时特别是 得到了老师的谆谆教导， 给予了我很大的帮助， 不仅给了我思路上的开阔， 还让我认识到了 自己对以前所学知识的不足方面。计算机的迅速普及以及飞速发展， 掌握计算机方面相关的知识越来越迫切， 掌握一定的 计算机基础技术已经成为一大必备技能。 排序是计算机程序设计中极其重要的一部分， 是计 算机程序设计中的一个重要操作，它的功能是将一个数据元素(或记录)的任意序列，重新 排列成一个按关键字有序的序列。学习和研究各种排序方法是计算机工作者的重要课题之一。这次课程设计我主要应用所学，通过在C和C+编程环境下，实现了对符合堆的无序序列进行排序。参考文献1 严蔚敏，吴伟民 . 数据结构 （C 语言版 ）M. 北京：清华大学出版社 ,2002,20112 严蔚敏，李冬梅，吴伟民.数据结构（C语言版）M北京：人民邮电出版社3 谭浩强 .C 程序设计（第四版） M. 北京：清华大学出版社 ,2011