数据结构课程设计86645

1、武汉理工大学数据结构课程设计说明书学 号： 0120810340332课 程 设 计题 目完全二叉树的判别学 院计算机科学与技术专 业计算机科学与技术班 级0803姓 名董梦菲指导教师陈天煌2010年7月1日课程设计任务书学生姓名： 董梦菲 专业班级： 计算机0803 指导教师： 陈天煌 工作单位： 计算机科学系 题 目:完全二叉树的判别 初始条件：试写一个判别给定二叉树是否为完全二叉树的程序。（1）此二叉树以二叉链表作存储结构；（2）自行设计正、反测试用例；要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）课程设计报告按学校规定格式用A4纸打印（书写），并应包

2、含如下内容： 1. 问题描述简述题目要解决的问题是什么。2. 设计存储结构设计、主要算法设计（用类C/C+语言或用框图描述）、测试用例设计；3. 调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4. 经验和体会（包括对算法改进的设想）5. 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出。说明：1. 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。2. 凡拷贝往届任务书或课程设计充数者，成绩一律无效，以0分记。时间安排：1、第18周完成。2、7月2日8:30时到实验中心检查程序、交课程设计报告、源程

3、序（U盘）。指导教师签名： 2010年6月22日系主任（或责任教师）签名： 年 月 日 目录1.问题分析与任务定义2.数据类型和系统设计 2.1储存结构设计 2.2主要算法设计2.2.1二叉树构造的算法 2.2.2判定是否为完全二叉树的算法 2.2.3测试用例设计 2.2.4程序各模块之间的关系图3.程序调试3.1.对设计和编码的讨论和分析3.2调试4.程序运行结果5.经验与体会6.参考文献 完全二叉树的判别1、问题分析与任务定义 该课程设计的题目为：完全二叉树的判别。也就是对于输入的二叉树进行判定，看是否为完全二叉树。为实现此次课程设计的完成，对程序设计作了相应的定义与限制。首先，为了输入的

4、简洁，将树的结点树不大于20；其次，对于二叉树的输入就按照前序遍历的顺序进行输入；最后，对于程序的测试，应该从正反两面进行测试，即输入一个是完全二叉树和一个不是完全二叉树的。由于输入二叉树时，对于不是完全二叉树的，有的结点会没有左子树或右子树，甚至两子树都没有，为跟好的表示没有子树的情况，在此次程序设计中用“”来表示。对于此次的正反测试，分别用一下的两个二叉树进行测试： a) 完全二叉树 b) 非完全二叉树所以输入的顺序分别为：正面测试：a b d e c f ；反面测试：a b d c e f 。2、数据类型和系统设计 2.1储存结构设计 根据设计的要求，对于本程序的储存结构要用二叉链表。

5、以下是作为本次设计数据的存储结构的定义：template class binarytree; template class treenodefriend class binarytree;private:type1 data;treenode* leftchild;treenode* rightchild;public:treenode():leftchild(NULL),rightchlid(NULL)treenode(type1 item,treenode*left=NULL,treenode*right=NULL):data(item),leftchild(left),rightchil

6、d(right)type1 getdata()const return data;treenode* getleft()const return leftchlid; treenode*getright()constreturn rightchlid;void setdata(const type1& item) data=item;voidsetleft(treenode*left)leftchild=left; voidsetright(treenode*right)rightchild=right;2.2主要算法设计2.2.1二叉树构造的算法 对于二叉树的构造，可以运用插入建立，还可以用

7、递归建立。在此次设计中运用的是递归建立。运用队列的进队函数进行对二叉树的结点的输入。对于进队的第一个数据为二叉树的根结点，如果为非空，则继续输入第二个进队元素，将其设置为该根结点的左子树，然后将该左子树作为新的根结点，依次进行到下一层的结点，直至到达叶节点（即既没有左子树也没有右子树），然后对于这以后进队的元素则作为右子树，用相同的方法建树。2.2.2判定是否为完全二叉树的算法 判定完全二叉树，首先要知道什么是完全二叉树，对完全二叉树定义以前，要明白满二叉树的定义。一棵深度为k且有2k-1个结点的二叉树称为满二叉树。对满二叉树的你借点进行连续编号，约定编号从根结点起，自上而下，自左而右。由此引

8、出完全二叉树的定义。深度为k的，右n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树的编号从1至n的结点一一对应时，称之为完全二叉树。所以对于二叉树的判定，假如某一结点有右子树但没有左子树则该树不是完全二叉树。如果某一结点没有右子树或没有左子树，但是其后的结点有左子树或右子树，则该树不是完全二叉树。根据这种判定方法，可以判定其是不是完全二叉树。 2.2.3测试用例设计 按照课程设计报告要求，要分别从正面和反面两个方面进行测试。所以分别用是完全二叉树的树和不是完全二叉树的树用其的前序遍历顺序输入，就可以完成设计要求。 2.2.4程序各模块之间的关系图 程序模块关系图3.程序调试3.1对

9、设计和编码的讨论和分析编码建立上一步详细设计结果的基础上，对编码进行调试。3.2调试调试一向是我感觉很头疼的一个环节，因为程序中会因为各种各样的原因出现很多错误。所以在调试前应该做好充分的准备，比如说准备一本高级语言程序设计的教材以及先建立好工程和文件。在设计中，我使用的是Visual C+ 6.0为平台对程序进行调试。调试之前就是要把源程序输入进去，我建立了一个.cpp文件。输完源代码后对代码进行编译，出现了诸多问题。比如说，会在语句后面丢掉分号、输入的标点符号不是英语输入中的而是中文输入中的、语法错误、函数调用不匹配的问题等等。对于这些错误需要相当大的耐性，但是都不难解决，只要细心的检查程

10、序就可以更正了。可以在调试错误中找到出错的地方，根据错误信息提示进行改错。对于有的错误提示并不明白是什么错误，也是通过查资料书和在网络上搜索到底是什么错误，在寻求解决方法。在编译没有错误之后开始组建。在组建出现了内存泄露，这是在编程中经常出现的问题。产生这种问题的原因也有很多种。大多数情况下就是指针出现错误。于是我就开始检查程序中使用到指针的地方，进行检测，最后查出来问题并更正了。调试没有错误以后，就是进行程序执行。4.程序运行结果首先是正面测试结果：然后是反面测试结果：5.经验与体会 其实此次的程序设计你还有很多需要改进的地方。比如说此次测试是一次性的可以加入while循环来完成我那个多次验

11、证。加入while循环后程序运行结果如下：还有本程序中没有destroy函数析构函数，这是个不足点，容易引起错误。还可以引入二叉树的print函数，将二叉树打印出来，更加的直观。 在这次课程设计中，我还学到了许多东西。对于程序设计中的错误处理也有了更多的认识，也掌握了关于内存泄露的相关知识。而且对于二叉链表也有了更好的理解，对于用递归法建立二叉树也有了更多的理解。 对于程序设计也有了更好的理解，程序设计不光只是要得到相应的运行结果就可以的，还有考虑它的健壮性，以及与用户之间的交流，要能够直观的，简洁的表示该程序的使用方法和功能，而且还要有很好的重复使用性，这样的算法才是好的算法。 当然在这方面上我还有很多的不足，需要更多的努力，在反复实践过程中不断地完善自己在这方面的能力。6.参考文献 【1】数据结构（C语言版），严蔚敏，编著，出版社：清华大学出版，社出版时间：2008年2月【2】c+程序设计教程，闵联营，何克右，编著，出版社：武汉理工大学出版社，出版时间：2005年7月 【3】老师上课课件本科生课程设计成绩评定表班级：计科0803班 姓名：董梦菲学号