设计出树结构的相关函数库.doc

1、西安文理学院软件学院课程设计报告1西安文理学院软件学院课程设计报告设计名称数据结构课程设计设计题目设计出树结构的相关函数库学生学号专业班级软件工程学生姓名学生成绩指导教师（职称）课题工作时间2014616至2014627西安文理学院软件学院课程设计报告II说明1、报告中的任务书、进度表由指导教师在课程设计开始前填写并发给每个学生。2、学生成绩由指导教师根据学生的设计情况给出各项分值及总评成绩。3、所有学生必须参加课程设计的答辩环节，凡不参加答辩者，其成绩一律按不及格处理。答辩由指导教师实施。4、报告正文字数一般应不少于3000字，也可由指导教师根据本门综合设计的情况另行规定。5、平时表现成绩低

2、于6分的学生，取消答辩资格，其本项综合设计成绩按不及格处理。西安文理学院软件学院课程设计报告III软件学院课程设计任务书学生姓名学号专业班级设计题目设计出树结构的相关函数库内容概要在日常生活中，树结构在程序调用中很常用，因此，为了更方便的在程序设计中使用树结构，所以设计了此函数库。本函数使用MICROSOFTVISUALC60设计二叉链表结构的相关函数库，操作系统通过执行MAIN函数开始运行一个C程序，实现对树的创建，查找，和遍历。函数库将实现一下功能树的建立，增删查改，各种遍历。文献资料1严蔚敏数据结构（C语言版）M北京清华大学出版社,19972谭浩强C程序设计（第三版）M北京清华大学出版社

3、，200513徐孝凯编著数据结构实用教程（第二版）X北京清华大学出版社，20063设计要求本次设计将完成以下要求1包括树结构的存储结构及各种基本函数以及常用函数（自己确定函数、函数形式及理由）。2最好能借助语言环境实现图形显示功能，以便能将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来。3给出若干例程，演示通过调用自己的库函数来实现相关问题的求解。工作期限设计工作自2014年6月16日至2014年6月27日止。指导教师院长日期2014年6月16日西安文理学院软件学院课程设计报告IV软件学院课程设计进度安排表学生姓名学号专业班级起止日期内容备注6月16日6月17日下任务书；

4、收集、阅读、整理相关参考文献，并进行归纳和概括总结，完成项目/任务背景介绍部分文字内容。6月18日11月20日系统功能设计和模块设计、系统体系结构构建。6月21日6月24日各功能模块编码实现，系统各功能模块调试与维护。6月25日6月26日系统功能集成、系统调试与测试，按照模板要求撰写课程设计/项目设计报告。6月27日课程设计/项目设计分组答辩，提交课程设计/项目设计报告以及相关文档，进行成绩评定。指导教师签名2014年6月16日西安文理学院软件学院课程设计报告V成绩评定表学生姓名学号专业班级类别合计分值各项分值评分标准实际得分合计得分平时表现1010按时参加设计指导，无违反纪律情况。完成情况3

5、020按设计任务书的要求完成了全部任务，能完整演示其设计内容，符合要求。10能对其设计内容进行详细、完整的介绍，并能就指导教师提出的问题进行正确的回答。报告质量3510报告文字通顺，内容翔实，论述充分、完整，立论正确，结构严谨合理；报告字数符合相关要求，工整规范，整齐划一。5课题背景介绍清楚，综述分析充分。5设计方案合理、可行，论证严谨，逻辑性强，具有说服力。5符号统一；图表完备、符合规范要求。5能对整个设计过程进行全面的总结，得出有价值的结论或结果。5参考文献数量在2篇以上，格式符合要求，在正文中正确引用。答辩情况2510在规定时间内能就所设计的内容进行阐述，言简意明，重点突出，论点正确，条

6、理清晰。15在规定时间内能准确、完整、流利地回答教师所提出的问题。总评成绩分指导教师（签字）日期2014年6月27日西安文理学院软件学院课程设计报告1目录目录1摘要2第一章课题背景311课程设计的目的3第二章设计简介及设计方案论述421问题的模型描述422定义二叉树的结点类型4第三章详细设计631设计树的构建和遍历6311入队6312队列判空6313出队6314先序递归建立二叉树6315递归遍历输出函数7316层次遍历输出算法7317求二叉树深度算法8318求二叉树叶子结点数的算法8第四章设计结果及分析941程序运行结果9参考文献12附录源程序代码13西安文理学院软件学院课程设计报告12摘要摘

7、要作为用户我们极少接触系统调用，但是我们熟悉C语言，对库函数的调用并不陌生。C语言支持一系列库函数的调用，而事实上，库函数的调用是C语言在较高层次上调用的一种方式，函数调用是操作系统内核提供给程序员的程序设计界面，它们是内核提供给用户调用的函数。在日常生活中，树结构在程序调用中很常用，因此，为了更方便的在程序设计中使用树结构，所以设计了此函数库。使用MICROSOFTVISUALC60设计二叉链表结构的相关函数库，操作系统通过执行MAIN函数开始运行一个C程序。MAIN函数可以调用C程序中的其他函数来完成程序的任务，其他函数也可以互相调用，但其他函数（非MAIN函数）不能调用MAIN函数MAI

8、N函数只能由操作系统来调用。函数库将实现一下功能树的建立，增删查改，各种遍历。关键词函数库；C程序；树结构；遍历。西安文理学院软件学院课程设计报告3第一章课题背景11课程设计的目的VISUALC60由许多组件组成，包括编辑器、调试器以及程序向导APPWIZARD、类向导CLASSWIZARD等开发工具。编译就是把高级语言变成计算机可以识别的2进制语言，计算机只认识1和0，编译程序把人们熟悉的语言换成2进制的。编译程序把一个源程序翻译成目标程序的工作过程分为五个阶段词法分析；语法分析；语义检查和中间代码生成；代码优化；目标代码生成。主要是进行词法分析和语法分析，又称为源程序分析，分析过程中发现有

9、语法错误，给出提示信息。将编译产生的OBJ文件和系统库连接装配成一个可以执行的程序。由于在实际操作中可以直接点击BUILD从源程序产生可执行程序，将源程序翻译成可执行文件的过程分为编译和链接两个独立的步骤，之所以这样做，主要是因为在一个较大的复杂项目中，有很多人共同完成一个项目每个人可能承担其中一部分模块，其中有的模块可能是用汇编语言写的，有的模块可能是用VC写的，有的模块可能是用VB写的，有的模块可能是购买不是源程序模块而是目标代码或已有的标准库模块，因此，各类源程序都需要先各自编译成目标程序文件，再通过链接程序将这些目标程序文件连接装配成可执行文件，再调用函数或运行可执行程序文件。西安文理

10、学院软件学院课程设计报告4第二章设计简介及设计方案论述21问题的模型描述设计程序结构，如图21所示图21设计模型22定义二叉树的结点类型TYPEDEFCHARDATATYPETYPEDEFSTRUCTNODECHARDATASTRUCTNODELCHILDSTRUCTNODERCHILDBITNODE,BITREE/二叉树节点，二叉链表TYPEDEFSTRUCTQUEUENODE中序遍历后序遍历遍历深度叶子结点数输出结果结束开始建立链式存储结构的二叉树队列定义初始化入队出队用先序遍历创建二叉链表西安文理学院软件学院课程设计报告5BITREEDATASTRUCTQUEUENODENEXTLINK

11、QUEUENODE/队列中的每个节点TYPEDEFSTRUCTLINKQUEUENODEFRONTLINKQUEUENODEREARLINKQUEUE/队列西安文理学院软件学院课程设计报告6第三章详细设计31设计树的构建和遍历树的设计和遍历包括入队，判空，出队，建立和遍历。311入队OIDINITQUEUELINKQUEUEQQFRONTLINKQUEUENODEMALLOCSIZEOFLINKQUEUENODEIFQFRONTNULLQREARQFRONTQFRONTNEXTNULLELSEPRINTF“分配空间失败N“312队列判空VOIDENTERQUEUELINKQUEUEQ,BITR

12、EEXLINKQUEUENODENEWNODENEWNODELINKQUEUENODEMALLOCSIZEOFLINKQUEUENODEIFNEWNODENULLNEWNODEDATAXNEWNODENEXTNULLQREARNEXTNEWNODEQREARNEWNODE313出队INTQUEUEISEMPTYLINKQUEUEQIFQFRONTQREARRETURN1ELSERETURN0314先序递归建立二叉树VOIDDELETEQUEUELINKQUEUEQ,BITREEXLINKQUEUENODEPIFQFRONTQREARRETURNPQFRONTNEXT西安文理学院软件学院课程设计

13、报告7QFRONTNEXTPNEXTIFQREARPQREARQFRONTXPDATAFREEP315递归遍历输出函数VOIDCREATEBITREEBITREEBTCHARCHCHGETCHARIFCHBTNULLELSEBTBITREEMALLOCSIZEOFBITNODEBTDATACHCREATEBITREECREATEBITREE/先序递归遍历二叉树/VOIDPREORDERBITREEROOTIFROOTNULLPRINTF“C“,ROOTDATAPREORDERROOTLCHILDPREORDERROOTRCHILD/后序递归遍历二叉树/316层次遍历输出算法VOIDPOSTOR

14、DERBITREEROOTIFROOTNULLPOSTORDERROOTLCHILDPOSTORDERROOTRCHILDPRINTF“C“,ROOTDATAVOIDINORDERBITREEROOTIFROOTNULLINORDERROOTLCHILD西安文理学院软件学院课程设计报告8PRINTF“C“,ROOTDATAINORDERROOTRCHILD317求二叉树深度算法VOIDDEPTHBITREEROOT,INTIFROOTDEP0ELSEDEPTHROOTLCHILD,DEP1DEPTHROOTRCHILD,DEP2DEPDEP1DEP2DEP11DEP21318求二叉树叶子结点数

15、的算法VOIDCOUNTLEAFBITREEROOT,INTIFROOTLCHILDCOUNTLEAFROOTRCHILD,N西安文理学院软件学院课程设计报告9第四章设计结果及分析41程序运行结果给定一个树结构ABCD，求其遍历结果，深度和叶子结点数。结果如图41所示图41实验结果1给定一个树结构ABDECFG，求其遍历结果，深度和叶子结点数。结果如图42所示西安文理学院软件学院课程设计报告10图42实验结果2西安文理学院软件学院课程设计报告11总结本次课程设计为时二周，我选的课题是设计出树结构的相关函数库，以便在程序设计中的调用。其主要研究内容在于实现了二叉链表的相关函数库的调用。为了实现以

16、链表为存储结构的二叉树的有关操作，要熟练掌握二叉链表的特性，但对于一些算法较为复杂，代码量多些，容易出现一些变量的定义、函数声明、函数调用等细节上的问题出错。在本程序的设计过程中，为了克服以上困难，采取了一些措施建立清晰的程序设计的步骤方法，分步各个模块程序设计，进行仔细的总体结构设计，反复调试、细心观察达到完善整个系统等。二叉树的递归算法主要是将二叉树存储到链表结构中。遍历是二叉树各种操作的基础，先序、中序、后序是二叉树遍历的三种基本遍历方法。而这些都是数据结构的基础内容，是我们必须理解和牢记的基础知识。将这些基础算法综合起来，更能清晰地认识和理解各种算法的作用。当然，要学会编程不会仅局限于

17、课本知识，而是根据课本知识进行有效的拓展，并且不得不学会在众多的参考资料中搜索有用的自己所需的知识，并迫使自己去学习掌握它们，从中不断提高自己。虽然程序规模不大，我们依然为此付出了努力，仍免不了各种错误的出现。编程过程需要很大的毅力和耐心，而且要有良好的思维和扎实的专业基础知识，所以我们需要不断的学习，发现自身不足之处并改正它，逐步提高自身能力，不断取得进步。对于数据结构的学习，一直感到很吃力，也想过放弃。通过实践，我们接触到了很多关于的MICROSOFTVISUALC60编程让我们认识到知识的运用性，并加深对基础知识的理解，从中了解自己需要学习的东西并学会自学。在此我们要感谢我的老师对我们专

18、心致志的辅导，让我们学会了许多分析和解决问题的方法，让我们受益匪浅。通过几个星期的努力，虽然从中也发现了自己很多不足，可能其中还有不少问题，但我觉得最重要的是自己也从中得到很多；不敢说百分百的完成也应该基本上完成了课题任务，成功地实现课题目标。西安文理学院软件学院课程设计报告12参考文献1严蔚敏数据结构（C语言版）M北京清华大学出版社,19972谭浩强C程序设计（第三版）M北京清华大学出版社，200513徐孝凯编著数据结构实用教程（第二版）X北京清华大学出版社，20063西安文理学院软件学院课程设计报告13附录源程序代码INCLUDEINCLUDETYPEDEFSTRUCTNODECHARDA

19、TASTRUCTNODELCHILDSTRUCTNODERCHILDBITNODE,BITREE/二叉树节点，二叉链表TYPEDEFSTRUCTQUEUENODEBITREEDATASTRUCTQUEUENODENEXTLINKQUEUENODE/队列中的每个节点TYPEDEFSTRUCTLINKQUEUENODEFRONTLINKQUEUENODEREARLINKQUEUE/队列/队列的初始化/VOIDINITQUEUELINKQUEUEQQFRONTLINKQUEUENODEMALLOCSIZEOFLINKQUEUENODEIFQFRONTNULLQREARQFRONTQFRONTNEXT

20、NULLELSEPRINTF“分配空间失败N“/入队/VOIDENTERQUEUELINKQUEUEQ,BITREEXLINKQUEUENODENEWNODENEWNODELINKQUEUENODEMALLOCSIZEOFLINKQUEUENODEIFNEWNODENULLNEWNODEDATAXNEWNODENEXTNULLQREARNEXTNEWNODEQREARNEWNODE/队列判空/INTQUEUEISEMPTYLINKQUEUEQIFQFRONTQREAR西安文理学院软件学院课程设计报告14RETURN1ELSERETURN0/出队/VOIDDELETEQUEUELINKQUEUE

21、Q,BITREEXLINKQUEUENODEPIFQFRONTQREARRETURNPQFRONTNEXTQFRONTNEXTPNEXTIFQREARPQREARQFRONTXPDATAFREEP/利用扩展先序遍历序列创建二叉链表/VOIDCREATEBITREEBITREEBTCHARCHCHGETCHARIFCHBTNULLELSEBTBITREEMALLOCSIZEOFBITNODEBTDATACHCREATEBITREECREATEBITREE/先序递归遍历二叉树/VOIDPREORDERBITREEROOTIFROOTNULLPRINTF“C“,ROOTDATAPREORDERROO

22、TLCHILDPREORDERROOTRCHILD/后序递归遍历二叉树/VOIDPOSTORDERBITREEROOTIFROOTNULL西安文理学院软件学院课程设计报告15POSTORDERROOTLCHILDPOSTORDERROOTRCHILDPRINTF“C“,ROOTDATAVOIDINORDERBITREEROOTIFROOTNULLINORDERROOTLCHILDPRINTF“C“,ROOTDATAINORDERROOTRCHILD/层序遍历对给定的二叉树进行层序遍历/VOIDLAYERORDERBITREEROOTBITREEX/这里要记得申请空间XBITREEMALLOCS

23、IZEOFBITREEIFXNULLPRINTF“内存分配失败N“LINKQUEUEQQLINKQUEUEMALLOCSIZEOFLINKQUEUEINITQUEUEQENTERQUEUEQ,ROOTWHILEQUEUEISEMPTYQDELETEQUEUEQ,XPRINTF“C“,XDATAIFXLCHILDENTERQUEUEQ,XLCHILDIFXRCHILDENTERQUEUEQ,XRCHILDVOIDCOUNTLEAFBITREEROOT,INTIFROOTLCHILDCOUNTLEAFROOTRCHILD,NVOIDDEPTHBITREEROOT,INT西安文理学院软件学院课程设计

24、报告16IFROOTDEP0ELSEDEPTHROOTLCHILD,DEP1DEPTHROOTRCHILD,DEP2DEPDEP1DEP2DEP11DEP21INTMAININTARGC,CHARARGVINTN0,DEPBITREEROOTCREATEBITREEPRINTF“先序递归遍历N“PREORDERROOTPRINTF“N“PRINTF“中序递归遍历N“INORDERROOTPRINTF“N“PRINTF“后序递归遍历N“POSTORDERROOTPRINTF“N“PRINTF“层序遍历N“LAYERORDERROOTPRINTF“N“DEPTHROOT,DEPPRINTF“深度DEPDN“,DEPCOUNTLEAFROOT,NPRINTF“叶子结点数NDN“,NPRINTF“N“RETURN0