使用C语言编写的堆排序数据结构课设.doc

数据结构课程设计设计说明书 内部堆排序的实现 学生姓名李智学号1018014053班级计本102成绩指导教师林勇 数学与计算机科学学院2012 年9月7日数据结构课程设计评阅书题 目 内部堆排序算法的实现学生姓名李智学号1018014053指导教师评语及成绩成绩： 教师签名： 年 月 日答辩教师评语及成绩成绩： 教师签名： 年 月 日教研室意见总成绩： 室主任签名： 年 月 日注：指导教师成绩60%，答辩成绩40%，总成绩合成后按五级制记入。课程设计任务书20122013学年 第一学期专业： 计算机科学与技术 学号： 1018014053 姓名： 李智 课程设计名称： 数据结构课程设计 设 计 题 目： 内部堆排序算法的实现 完 成 期 限：自 2012 年 8 月 27 日至 2012 年 9 月 8 日共 2 周设计依据、要求及主要内容（可另加附页）：堆排序是数据结构中内排序部分的重点知识。堆分为大顶堆和小顶堆。堆排序的过程主要解决两个问题：（1）把无序序列建成一个堆；（2）输出堆顶元素后，重新将剩余元素调整成新堆。本课程设计主要完成的核心内容即为此。按以下的要求运用C/ C+结构体、指针、数据结构等基知识编程实现。任务要求：1） 阐述设计思想,画出流程图;2）对用户任意给定的数据序列进行存储；3）完成将无序数据序列建成堆；4）将堆顶数据按一定顺序输出;5）说明测试方法,写出完整的运行结果,较好的界面设计；6）按照格式要求完成课程设计说明书。设计要求:1）问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？确定问题的输入数据。2）逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的功能说明），各个主要模块的算法，并画出模块之间的调用关系图；3）详细设计及程序编码：详细设计的结果是对数据结构和基本操作做出进一步的求精，写出数据存储结构的类型定义，阐述各模块的设计思路和设计方法，并画出算法流程图；4）程序调试与测试：能够熟练掌握调试工具的各种功能，设计测试数据确保程序正确。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；5）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析；指导教师（签字）： 教研室主任（签字）： 批准日期： 年 月 日 摘要随着计算机技术的发展，为了查找方便，通常希望通过排序使表是按键字有序的。本课题利用简单排序的堆排序方法，通过建立大根堆，并对元素进行输出，实现用户输入的一组可以组成堆的数据元素进行处理，使其按关键字排成一个有序的序列，从而有效的提高了查找效率。此外为使程序更加完美，还增加了文件保存，读取的模块，使整个设计趋于完美。关键词：堆；排序；查找 目录1 课题描述12 问题分析和任务定义23逻辑设计.3 3.1 整体设计布局.3 3.2 数据存储结构.3 3.3抽象数据类型.33.4 各模块调用关系.4 4详细设计.5 4.1 函数设计思想流程图.5 4.2 程序流程图(核心算法).5 4.2.1 堆排序函数(含建立大顶堆).5 4.2.2 输出堆排序后的函数.6 4.3 文件保存，读取函数.7 4.4 创建及输入函数.9 4.5 菜单函数.9 4.6 主函数.105程序编码.126 程序调试及测试.167结果分析.19总结 .20参考文献. 211 课题描述随着计算机技术的发展，为了查找方便，通常希望计算机中的表是按关键字有序的，因为有序的顺序表可以采用查找效率较高的堆排序查找法，而无序的表只能进行顺序查找，排序是计算机程序设计中的一个重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列，因此，学习和研究各种排序方法是计算机工作者的重要课题之一。本课题简单选择排序中的堆排序方法，通过用户输入的可以组成堆排序的数据元素建立大根堆，并将其进行排序输出，使其成为一个按关键字排序的有序列，从而有效都提高查找效率。此外，通过本课题也是为了更好的体会和掌握课设的思想与流程。开发环境：VC6.0。2问题分析及任务定义本课题主要研究堆排序算法的实现，首先由堆的定义：n个关键字序列Kl，K2，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质) (1) kiK2i且kiK2i+1 或(2)KiK2i且kiK2i+1(1i )若将此序列所存储的向量R1.n看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字实现堆排序，可以将Rl.n看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大(或最小)的记录。故实现核心部分堆排序主要解决两个问题：（1）把无序序列建成一个堆；（2）输出堆顶元素后，重新将剩余元素调整成新堆。本课题设定包括核心的堆排序算法之外，其余的主要是定义相关关的抽象数据类型，创建数据，把堆排序的结果输出，设定菜单函数，使界面表现出友好型，还有为了使程序更加的健壮，需要考虑非法数据的测试。3逻辑设计3.1整体设计布局本课题按从自顶向下设计方法，整体界面表现出友好性，从一开始进入程序显示的是主要菜单，内涵有各个要选择的小项（即分模块）他们为：进行堆排序操作；保存堆排序的数据元素，从文件读取堆排序的数据。在本课题中核心主要是堆排序的操作，但为了在测试时显出更友好型，为此特增加了，文件保存，读取两部分模块，在程序运行时，系统自动读取了存在文件中的数据，然后跳出菜单，供客户选择。(设计布局图如下) 图 3.1整体设计流程图3.2 数据存储结构 typedef struct H /数据类型 int * data; /堆序列元素的关键字 int length; /堆序列元素的个数Heaptype;3.3 抽象数据类型ADT Heapty pe 数据对象： D=k1,k2,k3|k1,k2,k3Elemset(定义关系运算的集合) 数据关系: R1= kiK2i&kiK2i+1 基本操作： void creat(Heaptype &h) /操作结果： 创建函数，即给相应的存储结构申请空间 void input(Heaptype &h) /操作结果： 用键盘输入建堆的原始数据，使相应的元素存储到内存中void heapadjust(Heaptype &h,int s,int m) /初始条件： 已知h.datas.m中除h.datas.key之外均满足堆的定义/操作结果：本函数调整h.datas的关键字，使h.atas.m成为一个大顶堆void heapsort(Heaptype &h) /初始条件： h以经为一个大顶堆了/操作结果： 对h 这个大顶堆进行排序，结果元素是从大到小的依次有序的序列void print(Heaptype &h) /初始条件： 堆排序的有序顺序表已经排好了/操作结果： 把对应的堆序列元素给打印出来void savetofile(Heaptype &h) / 初始条件：h中已经有相关元素/ 操作结果：把堆排序后的有序顺序表存储到文件中去int readfromfile(Heaptype &H) / 初始条件：文件中以保存了堆排序的相关记录/ 操作结果：把文件中存储的数据读出来，赋给相应的存储结构中ADT Heapty pe3.4 各模块之间的调用关系 由于本程序的各个函数的性对独立性比较高，故只有在堆排序算法过程中，才用到了函数的调用。即在堆排序函数heapsort(Heaptype &h)中两次调用了调整大顶堆函数heapadjust(Heaptype &h,int s,int ，在主程序中分别调用的模块以在整体设计布局中展示 图 3.2 各模块的调用关系4详细设计4.1 函数设计思想流程图 设计思想: 在整体上完成堆排序的两个核心步骤，先建立大顶堆，即筛选，然后在进行排序，流程图如图4.1所示。 图 4.1堆排序流程图4.2程序流程图4.2.1 堆排序函数(含建立大根堆) 设计思想：从第一个非终端结点开始，与其的左右孩子比较找到最大的max，若关键字比 max小，则进行交换，然后倒着走，按上述规律进行比较，直到树根为止，注意关键字与其左右孩子比较好交换位置后，还要继续向下比较，直到叶子结点，流程图如图4.2所示。 图 4.2建立大根堆函数 堆排序函数流程图设计思想: 先将初始文件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调整为堆,直到无序区只有一个元素为止，流程图如图4.3所示。 图 4.3堆排序函数流程图4.2.2输出堆排序的顺序表序列函数设计思想：此函数主要是一个打印函数，即把堆排序排好了的数据打印出来，流程图如图4.4所示 图 4.4 打印函数流程图4.3 文件保存，读取函数 设计思想: (1)保存函数 首先得以w+方式建立个文本文档，然后利用fprintf()函数把堆排序的数据保存到文件stu.txt中，流程图如图4.5所示； (2) 读取函数 利用fscanf() 函数把保存到文件中的数据读取出来赋给程序中设定存储结构中，流程图如图4.6所示。开始fp=fopen(stu.txt,w+);fprintf(fp,%dn,h.length);adr=1；adr=h.length;fprintf(fp,%dn,h.dataadr); adr+结束 否 是 图4.5 文件保存流程图 编码void savetofile(Heaptype &h) /对所输入的记录进行保存FILE *fp;int adr;fp=fopen(stu.txt,w+); /打开并建立以个stu.txt文件fprintf(fp,%dn,h.length); /把堆序列个数写入文件 for (adr=1;adr=h.length;adr+) fprintf(fp,%dn,h.dataadr);fclose(fp); /关闭文件printf (保存成功!n);开始FILE *fp; int i; char a10;fp=fopen(stu.txt,r+)=NULLfscanf(fp,%s,a); H.length=atoi(a); i=1;return 0;i=H.lengthfscanf(fp,%s,a); H.datai=atoi(a);打印出数据；fclose(fp);return 1结束 否 是 否 是 图4.6 文件读取流程图 编码 int readfromfile(Heaptype &H) /从文件中读取数据FILE *fp;int i;char a10; if(fp=fopen(stu.txt,r+)=NULL) return 0; /打开stu.txt文件,若文件为空，则返回0，若文件不为空则进行读取操作fscanf(fp,%s,a); /把存在文件中堆序列数据个数读出来付给aH.length=atoi(a); /把a赋给h.lengthfor(i=1;i=H.length;i+) /把文件中的数据全部读出来 fscanf(fp,%s,a); /读取文件中的数据读取出来赋给a H.datai=atoi(a);printf(从文件中读取数据n); for(i=1;i-1&n5&strlen(ch)=1) break; printf(输入有误!n); printf(请重新输入操作按键(0-4):); /scanf(%s,ch);switch(n)case 0: printf(退出程序!); break;case 1: input(h); printf(创建数据后的数据序列为:n); print(h); break;case 2: printf(排序后如下n); heapsort(h); print(h); break;case 3: savetofile(h); print(h); break;case 4: readfromfile(h); printf(n); break;default: printf(ntt输出出错!请重新输入!);printf(继续运行吗？继续请按(y或Y),否则按(n或N)退出本程序!请输入: ); scanf(%s,s); while(strcmp(s,y)!=0&(strcmp(s,Y)!=0)if(strcmp(s,n)=0|strcmp(s,N )=0) printf(退出图的相关操作!n); return ;printf(输入有误!继续运行请输入(y或Y)否则(n或N):t); scanf(%s,s); 5 程序编码/*试验项目名称：内部堆排序算法的实现 ，要求 1）对用户任意给定的数据序列进行存储；2）完成将无序数据序列建成堆；3）将堆顶数据按一定顺序输出;*/#includestdio.h#includemalloc.h#includestring.h#includestdlib.h#define OVERFLOW -1#define MAX 100typedef struct H /数据类型int *data;int length;Heaptype;void heapadjust(Heaptype &h,int s,int m) /*已知h.datas.m中除h.datas.key之外均满足堆的定义，本函数调整h.datas的关键字 ，使h.atas.m成为一个大顶堆*/ int j,Rc ; Rc=h.datas; /沿数据元素较大的孩子向下筛选 for(j=2*s;j=m;j*=2) if(jm&h.datajh.dataj+1) +j; /j为k较大的记录的下标 if(!(Rc0;-i) /把h.data1.h.length构建成大顶堆heapadjust(h,i,h.length);for(i=h.length;i1;-i)a=h.data1; /将对顶记录和当前未经排序子序列h.data1.i中最后一个记录相互交换h.data1=h.datai;h.datai=a;/printf(%dn,h.datai); heapadjust(h,1,i-1); /将h.data1.i-1重新调整为大顶堆 void creat(Heaptype &h) /创建函数h.data=(int *)malloc(MAX *sizeof(int); /申请一片连续空间if(!h.data) exit(OVERFLOW);h.length=0; void input(Heaptype &h) int i=1;char s10=y;h.length=0;do printf(请输入数据n); scanf(%d,&h.datai); printf(您还需要继续输入吗?是(Y或y): n); h.length=h.length+1; i+; scanf(%s,s);while(strcmp(s,y)=0|(strcmp(s,Y)=0);void print(Heaptype &h) /输出函数int i;for(i=1;i=h.length;i+)printf(%d,h.datai);printf(n);void savetofile(Heaptype &h) /对所输入的记录进行保存FILE *fp;int adr;fp=fopen(stu.txt,w+); /打开并建立以个stu.txt文件fprintf(fp,%dn,h.length); /把堆序列个数写入文件 for (adr=1;adr=h.length;adr+) fprintf(fp,%dn,h.dataadr);fclose(fp); /关闭文件printf (保存成功!n);int readfromfile(Heaptype &H) /从文件中读取数据FILE *fp;int i;char a10; if(fp=fopen(stu.txt,r+)=NULL) return 0; /打开stu.txt文件,若文件为空，则返回0，若文件不为空则进行读取操作fscanf(fp,%s,a); /把存在文件中堆序列数据个数读出来付给aH.length=atoi(a); /把a赋给h.lengthfor(i=1;i=H.length;i+) /把文件中的数据全部读出来 fscanf(fp,%s,a); /读取文件中的数据读取出来赋给a H.datai=atoi(a);printf(从文件中读取数据n); for(i=1;i-1&n5&strlen(ch)=1) break; printf(输入有误!n); switch(n)case 0: printf(退出程序!n); return ;case 1: input(h); printf(创建数据后的数据序列为:n); print(h); break;case 2: printf(排序后如下n); heapsort(h); print(h); break;case 3: savetofile(h); print(h); break;case 4: readfromfile(h); printf(n); break;default: printf(ntt输出出错!请重新输入!);printf(继续运行吗？继续请按(y或Y),否则按(n或N)退出本程序!请输入: ); scanf(%s,s); while(strcmp(s,y)!=0&(strcmp(s,Y)!=0)if(strcmp(s,n)=0|strcmp(s,N )=0) printf(退出图的相关操作!n); return ;printf(输入有误!继续运行请输入(y或Y)否则(n或N):t); scanf(%s,s); 6 程序调试及测试内含有合法及非法的数据输入及其相对应的数据输出 （1）测试创建堆函数，采用交互式循环，方便灵活。 图 6.1 创建函数的测试，（内涵有打印函数）（2）对堆排序操作进行测试，原始序列为25,23,49,16,8,3, 堆排序后的序列为8,13,16,23,25,49复合逻辑堆排序的结果 图 6.2 堆排序函数的测试（3）把数据保存到文件中，为了查看是否保存成功，特地查看程序中所建的文件，与创建保存后的数据完全吻合 图 6.3 数据文件保存函数的测试 图 6.4 所建立的stu.txt文本文档中保存的数据(4)从文件中把数据读取出来 图6.5 读取文件函数的测试(5)退出操作 图6.6 退出程序7 结果分析 (1)算法分析：堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用heapadjust(Heaptype &h,int s,int m)实现的。堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为O(1)，它是不稳定的排序方法算法的正确输入及其输出结果，和错误的输入及其输出结果均在程序测试中给与展现(2)通过自己查阅书籍，询问老师，同学，基本完成了本次课程设计的相关要求，从分析问题，及解决问题，都展现良好的设计模式，在核心程序编写过程中，采用自顶向下的程序设计方法，把问题细化，逐个到每一模块，程序界面友好，在必要处有相关的提示及注解。使人看了一目了然。 (3)在课程设计过程中虽然整体上完成了课设的相关要求，但是其中也遇见了些问题，主要面临的问题是，在程序编写过程中，根据整个设计思想，在核心程序之外增加了，文件保存，读取函数，即savetofile(Heaptype &h) ，readfromfile(Heaptype &H) ，想在程序运行开始()进入界面菜单之前)就直接从文件中读取数据，然而一开始把readfromfile() 放在switch()语句之前，加过运行却不能正确，把readfromfile()函数放在switch()语句之内是却能运行，一开始不知道问题出在哪里，后来通过学问同学才找到问题所在，即在运行readfromfile()函数时并没有给抽象数据类型申请空间，导致程序不能正确执行，后在readfromfile()函数之前加了个创建函数即creat(Heaptype &h) ，从而解决了问题 . 总结本次课设采用宏观构思，自顶向下的程序设