二叉树数据结构课程设计.doc

《二叉树数据结构课程设计.doc》由会员分享，可在线阅读，更多相关《二叉树数据结构课程设计.doc（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、目 录第一章 需求分析11.1课程设计题目11.2 课程设计任务及要求11.21 课程设计目的11.22 设计要求11.3课程设计思想21.4 软件运行环境及开发工具2第二章概要设计32.1 数据结构32.2 所用方法及其原理说明3第三章 详细设计43.1 详细设计方案43.2 模块设计43.21 二叉树定义43.22 树状显示二叉树设计73.22 主函数设计10第四章 调试和操作说明114.1 调试114.2 操作说明12第五章 总结与体会125.1 本文的主要工作125.2 存在问题125.3 心得体会12致 谢13参考文献14第一章 需求分析1.1课程设计题目树状显示二叉树：编写函数di

2、splaytree(二叉树的根指针，数据值宽度，屏幕的宽度)输出树的直观示意图。输出的二叉树是垂直打印的，同层的节点在同一行上。问题描述 假设数据宽度datawidth=2,而屏幕宽度screenwidth为64=26,假设节点的输出位置用（层号，须打印的空格数）来界定。第0层：根在（0，32）处输出；第1层：因为根节点缩进了32个空格，所以下一层的偏移量（offset）为32/2=16=screenwidth/22。即第一层的两个节点的位置为（1，32-offset）,(1,32+offset)即（1，16），（1，48）。第二层：第二层的偏移量offset为screenwidth/23。第

3、二层的四个节点的位置 分别是（2，16-offset），（2，16+offset），（2，48-offset），（2，48+offset）即（2，8），（2，24），（2，40），（2，56）。第i层：第i层的偏移量offset为screenwidth/2i+1。第i层的每个节点的位置是访问第i-1层其双亲节点时确定的。假设其双亲的位置为（i-1，parentpos）。若其第i层的节点是其左孩子，那末左孩子的位置是（i，parentpos-offset），右孩子的位置是（i，parentpos+offset）。实现提示 利用二叉树的层次遍历算法实现。利用两个队列Q，QI。队列Q中存放节点信息，

4、队列QI中存相应于队列Q中的节点的位置信息，包括层号和需要打印节点值时需要打印的空格数。当节点被加入到Q时，相应的打印信息被存到QI中。二叉树本身采用二叉链表存储。1.2 课程设计任务及要求1.21 课程设计目的据结构是计算机专业的核心课程，是一门实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段，要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C（C+）程序并上机调试的基本方法，还要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。1.22 设计要求1、课程设计

5、题目每组一题，每个学生必须独立完成；2、课程设计时间为2周；3、设计语言C（C+）不限；4、上机任务1）选择合适的数据结构，并定义数据结构的结构体；2）根据程序所要完成的基本要求，设计出完整的算法；3）设计出主程序（main函数），使其成为完整的程序。 6、上机时间：按照实验室上机时间安排计划执行 7、无论在校外、校内，都要严格遵守学校和所在单位的学习和劳动纪律、规章制度，学生有事离校必须请假。课程设计期间，无故缺席按旷课处理；缺席时间达四分之一以上者，其成绩按不及格处理。1.3课程设计思想二叉树是一种树形结构，它的特点是每个结点至多有两棵子树，即二叉树中不存在度大于2的结点，并且二叉树的子树

6、有左右之分，其次序不能任意颠倒。本设计主要根据二叉树的性质原理为设计的主体思路，二叉树的性质如下:性质1：在二叉树的第i层上至多有2i-1个结点（i=1）；性质2：深度为K的二叉树至多有2k-1个结点（K=1）；性质3：如果一棵有n各结点的完全二叉树的结点按层次编号，则对任一结点i(1=in,则结点无左孩子，否则其左孩子是结点2i；（2）若2i+1n,则结点i无右孩子，否则其右孩子为2i+1；另外，本设计利用二叉树的广度优先搜索算法实现。利用两个队列Q，QI。队列Q中存放节点信息，队列QI中存相应于队列Q中的节点的位置信息，包括层号和需要打印节点值时需要打印的空格数。当节点被加入到Q时，相应的

7、打印信息被存到QI中。二叉树本身采用二叉链表存储。本设计应用了C语言中的类来自定义头文件，将任务分成多个的模块，增强了可读性和简单性，同时为日后的编写，调试，维护提供了极大地方便。1.4 软件运行环境及开发工具本设计用到的软件是Microsoft Visual C+ 6.0程序开发软件，Microsoft Visual C+ 6.0是20世纪90年代中期由美国微软公司推出的一个强大的Windows应用程序开发平台，是“真正的程序员”首选的开发工具之一，也是有志于程序设计的程序员、大中专院校学生进入高级程序设计领域的首选软件之一。Microsoft Visual C+ 6.0程序开发软件提供了一

8、个可视化集成编程环境，能自动生成Windows应用程序的共有部分，帮助程序设计人员直接切入实际功能部分的代码编制主题，从而大大简化了复杂的Windows应用程序开发过程，极大的提高了程序设计的效率，其次， VC+功能强大，内容浩瀚在该环境下用户可以开发有关C和C+的各种应用程序，应用程序的开发包括建立、编辑、浏览、链接和调试等操作。第二章概要设计2.1 数据结构树状显示二叉树是二叉树的一种自然显示方法，本设计结果将二叉树形象的显示在屏幕上，直观易懂。因此本设计将对树状显示二叉树的设计步骤进行详细说明。首先得构造一个数组来存储整个二叉树的结点信息，建立两个队列Q和QI，队列Q中存放节点信息，队列

9、QI中存相应于队列Q中的节点的位置信息，包括层号和需要打印节点值时需要打印的空格数。当节点被加入到Q时，相应的打印信息被存到QI中。然后通过插入排序算法来构造一个二叉树，并用二叉树的层次遍历来使二叉树有顺序的存入队列Q，最后通过队列QI使得二叉树树状的显示在屏幕上。该程序的主要流程图如图2-1所示。2.2 所用方法及其原理说明 本设计主要运用了树的广度优先搜索和队列的先进先出的特点，树的广度优先搜索功能如下： 假设从图中某顶点v出发，在访问了v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有

10、已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 队列是一种先进先出的线性表，它只允许在表的一端进行插入，而在另一端删除元素。在队列中允许插入的一端叫队尾，允许删除的一端叫对头。队列的示意图如下： 图1 二叉树示意图第三章 详细设计3.1 详细设计方案本设计利用两个队列Q，QI，队列Q中存放结点信息，队列QI中存相应于队列Q中的节点的位置信息，包括层号和需要打印节点值时需要打印的空格数。当节点被加入到Q时，相应的打印信息被存到QI中。用二叉树（二叉树本身采用二叉链表存储）的层次遍历算法实现了二叉

11、树的树状显示。本设计应用了C语言中的类来自定义头文件，将任务分成多个的模块，增强了可读性和简单性，同时为日后的编写，调试，维护提供了极大地方便。3.2 模块设计本程序包括三部分，即二叉树定义部分（MyHeap.h），树状显示二叉树的实现（MyHeap.cpp）部分以及最重要的主函数部分(main.cpp)。下面将对各模块设计思想及设计方法进行详细的说明。3.21 二叉树定义需要显示的二叉树的示意图如下： 图2 树状二叉树#include #include #include #define TElemType char#define OK 1#define ERROR 0#define OVER

12、FLOW -2#define TRUE 1#define FALSE 0typedef int Status ; #define MAXQSIZE 100 typedef struct BiNode int data; struct BiNode *lchild; struct BiNode *rchild;BiNode, *BiTree;typedef int ElemType;typedef struct ElemType *base; /*数组首地址*/ int front; /*头指针,若队列不空，指向队列头元素*/ int rear; /*尾指针,若队列不空，指向队列尾元素的下一个位

13、置*/SqQueue;typedef struct int level;int pos;bool enter;int spaceNum;DisplayInfo;Status insert(BiTree bt,int key)BiTree p,q,newNode; newNode=(BiTree)malloc(sizeof(BiNode);p=NULL;q=bt;while(q)p=q;if(keydata)q=q-lchild;else q=q-rchild;if(p)if(keydata)p-lchild=newNode;elsep-rchild=newNode;elsebt=newNode

14、;Status InitQueue(SqQueue *Q) Q-base=(ElemType *)malloc(MAXQSIZE*sizeof(ElemType); if (!Q-base) printf(分配空间失败!); return OVERFLOW; Q-front=0; Q-rear=0; return OK;EnQueue(SqQueue *Q, ElemType e) /* 插入元素e为新的队尾元素 */ if ( (Q-rear+1)%MAXQSIZE=Q-front ) printf(队列满了!); return ERROR; Q-baseQ-rear=e; Q-rear=(

15、Q-rear+1)%MAXQSIZE;DeQueue(SqQueue *Q, ElemType *e) /* 删除队头元素，并由e返回其值 */ if (Q-front=Q-rear) return ERROR; *e=Q-baseQ-front; Q-front=(Q-front+1)%MAXQSIZE;Status IsEmpty(SqQueue *Q) if (Q-front=Q-rear) return OK; else return ERROR; BiTree CreateBiTree(BiTree bt) char ch; scanf(%c,&ch); if(ch=.) bt=NU

16、LL; else bt=(BiTree)malloc(sizeof(BiNode); /* 生成根结点 */ bt-data=ch; bt-lchild=CreateBiTree(bt-lchild); /* 生成左子树 */ bt-rchild=CreateBiTree(bt-rchild); /* 生成右子树 */ return bt;程序功能说明：该段程序分别用三个结构体定义了二叉树、队列和树的显示信息，还包含该程序需要用到C语言头文件、数据定义和二叉树的建立、队列的插入与删除等函数，是整个程序的基础。3.22 树状显示二叉树设计主要运用树的广度优先搜索，树的广度优先搜索功能如下： 假设

17、从图中某顶点v出发，在访问了v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。广度优先搜索的过程如下：图 3 广度优先搜索二叉树void BFSDisplayTree(BiTree bt)SqQueue Q;BiTree curNode;printf(BFS Display Tree:n);EnQueue(&Q,curNode); while(!

18、IsEmpty(&Q) DeQueue(&Q,&curNode); *curNode=Q.front;if(curNode-lchild)EnQueue(&Q, curNode-lchild);if(curNode-rchild)EnQueue(&Q, curNode-rchild);printf(%d ,curNode-data);printf(n);void NatureDisplayTree(BiTree bt)int i; SqQueue Q; SqQueue QI; int screenWidth=64; int dataWidth=2; DisplayInfo info; Disp

19、layInfo preInfo; BiTree curNode; DisplayInfo curInfo; if(!bt) printf(Tree is empty !n); return; printf(Nature Display Tree:n); EnQueue(&Q, bt); /* 若二叉树bt非空，则根结点bt入队，开始层次遍历 info.level=1; info.enter=true; info.spaceNum=screenWidthinfo.level; info.pos=info.spaceNum; EnQueue(&QI,info); preInfo=info; whi

20、le(!IsEmpty(&Q) curNode=Q.front; DeQueue(&Q,&e); curNode=QI.front; if(!curInfo.enter) printf(nn); for (i=0;idata); DeQueue(&QI,&curNode); if(!curNode-lchild) EnQueue(&Q, curNode-lchild); Info.level=curInfo.level+1; Info.pos=curInfo.pos-(screenWidthInfo.level); if(Info.levelpreInfo.level) Info.enter=

21、true;Info.spaceNum=Info.pos; else Info.enter=false; Info.spaceNum=Info.pos-preInfo.pos; Info.spaceNum-=dataWidth; EnQueue(&QI, Info); preInfo=Info; if(!curNode-rchild) EnQueue(&Q, curNode-rchild); info.level=curInfo.level+1; Info.pos=curInfo.pos+(screenWidthinfo.level); if(info.levelpreinfo.level) i

22、nfo.enter=true; info.spaceNum=info.pos; else info.enter=false; info.spaceNum=info.pos-preInfo.pos; info.spaceNum-=dataWidth; EnQueue(&QI, info);preinfo=info; printf(n);void Display(int *A,int n)int i;printf(Array Info:n);for (i=0;in;i+)printf(%dt,Ai);printf(n);程序功能说明： 程序先用广度优先搜索遍历二叉树（类似于二叉树的按层次遍历），使

23、二叉树的各结点依次进入队列Q，然后定义了另一个队列QI，它和队列Q形成一一对应关系，其中存放Q中结点的打印信息，每次从Q中取出一个节点curNode, 对应的打印信息为curInfo，当结点的输出位置用层号level（需打印的空格数）来界定，当level和.不同时，换行，通过Q与QI的结合，最后使二叉树树状的显示在屏幕上。3.22 主函数设计 主函数是一个程序最重要的部分，本程序也不例外。void main() BiTree bt,t;int i; int data9=5,4,2,7,1,9,3,0,6; Display(data,9); /打印数组 for (i=0;ikey=1)，刚开始做

24、的时候，写成了if (np-key = 1)，错误不太容易发现，主要是混淆了判断语句与赋值语句的区别。查到一个小小的建议，变量和常量比较时，把常量放在 = = 号的左边，这样如果你错写为 = 时，编译器就会报出禁止为常量赋值的错。因此，好的编程习惯的很重要。2、程序编写好后将程序在VC+环境中经过编译确认无误后调试并运行，得运行结果如下图。图4 运行结果14.2 操作说明程序还提供二叉树的结点个数及结点值的修改，若想修改结点的个数和结点的值，只需找到主函数（main()）中的“int data9=5,4,2,7,1,9,3,0,6”语句，把数组个数“9”改成结点的个数，把数组元素改成需要的结点

25、值即可。如把主函数中“int data9=5,4,2,7,1,9,3,0,6”改成“int data12=6,8,4,3,1,7,9,5,2,10,12,15”后的输出结果如下： 图5 运行结果2第五章 总结与体会5.1 本文的主要工作本设计的主要难点在于二叉树的层次遍历、队列模型的建立及队列与队列之间建立联系的设计与分析，以及程序的编译与运行。5.2 存在问题虽然经过努力，最终完成了树状显示二叉树的设计，但是我觉得在设计过程中还存在很多不足，例如：对一些C语言的编程思路不清楚，对实验软件运行步骤方法不熟悉，使得我在设计过程中遇到很多困难。5.3 心得体会紧张的两周数据结构实训很快过去了，通过

26、这周的学习使我巩固了以前的知识并在此基础上对数据结构的特点和算法有了更深的了解， 数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机科学的核心课程，而且已经成为其他理工专业的热门选修课。从设计中我学到了很多东西，最重要的是去做好一件事的心态，拿到题目的时候也许你觉得很难，但是只要你充满信心，一步一个脚印去实现它，不要怕麻烦，功夫不怕有心人，相信你一定会成功的。所以说，坐而言不如立而言，对于这些编程设计还是应该自己动手实际操作才会有深刻理解。首先这两周的学习，使我在巩固了原有的理论知识上，培养了我灵活运用和组合集成所学过知识及技能来分析、解决实际问题的能力，使我体会到自身知识和能力在实际

27、中的应用和发挥。其次，激发了我创新意识，开发创造的能力和培养沟通能力。另外，让我进一步熟悉了数据结构的设计应用。每一处编码都是在反复的熟悉数据结构的结构特性，及其语法、函数和程序设计思想的过程，对我数据结构的学习和提高很有益处，并且使我明白了程序设计过程有如解决一实际问题，从解决实际问题的角度，我们可以这样来看：第一要了解这个问题的基本要求，即输入、输出、完成从输入到输出的要求是什么；第二，从问题的要害入手，从前到后的解决问题的每个方面，即从输入开始入手，着重考虑如何从输入导出输出，在这个过程中，可确定所需的数据结构的基本类型线性表、栈、队列、串、数组、广义表、树和二叉树以及图等，然后确定处理

28、过程算法，可得最后结论。最后，在这次实训过程中，我深刻的认识到了自己在学习方面的不足之处，我知道我还有太多的基本的思想没有真正的理解，当然我不会灰心，我会在以后的日子里努力弥补我的不足。总之，两个礼拜的课程设计让我受益匪浅。要学好一门学科，没有刻苦钻研的精神是不行的，只有在不断的尝试中，不断经历失败，然后又不断的尝试才能获得成功。两个多礼拜中，我有过山穷水尽的困惑；有过柳暗花明的惊喜；有过唇枪舌剑的辩论；有过相互鼓励的安慰。两个礼拜的时间我经历了很多，也收获了很多。与其说它是体力与脑力的作业，不如说它是合作精神和毅力的考验。经过这次课程设计，我不仅学到了很多知识和技能，更重要的是我们学会了如何

29、运用所学知识去解决实际问题。致 谢在我们课程设计完善过程中，我也遇到了这样或那样的技术问题，但经过自己的不懈努力及查阅大量的资料，最终都得到了基本满意的答案。同时，其他同学也给了我许多有益的启示，促动和帮助，使我能够顺利的完成课题。感谢所有给予我帮助的老师，他们辛勤耕作，传道授业，不仅使我们开阔了视野，拓宽了思路，增长了学识，而且为我们今后的工作和学习打下了牢固的基础，也使增强我们对计算机的兴趣。是老师给予我无限的创造力和奋斗力，使我有无限的信心和希望来完成本次的实训内容。同时也感谢学校给了我们这次难得的实训机会，实训的过程让我们看到了自己理论知识上的不足，已掌握的知识也在这次的实训中有了质的

30、飞跃，知识能够应用了才是真正掌握了，也希望学校多给我们一些这样的机会。在最后，再次感谢我们的老师，如果没有老师的耐心指导，就不会有我们的成果。在我做论文期间，两位老师渊博的学识、严谨求实的科学精神、一丝不苟的治学态度和高尚的品格，深深的感染了我。程序的每次改动都离不开老师的辛勤工作，从各个方面来说，审查的工作往往比编写任务更复杂。正是老师百忙中不辞劳苦的帮助，才使我能够顺利完成这篇论文，在这里，对您衷心的表示感谢。本次实训中，老师对我的指导，我将永远感激在心，我相信这是我人生中宝贵的财富。老师，谢谢您！祝老师在今后的工作中，一帆风顺，事事顺利。参考文献1 佟伟光，杨政 实用数据结构（第二版）

31、科学出版社2 严蔚敏 数据结构（C语言版） 清华大学出版社3 李保春编著，数据结构习题与解析，清华大学出版 2001年第一版4 徐孝凯编著，数据结构课程实验，清华大学出版 2002年第一版5 张乃笑编著，数据结构与算法，电子工业出版社 2004年10月6 王卫东编著，数据结构辅导课，西安电子科技大学出版社 2001年7 陈文博 朱青著，数据结构与算法，机械工业出版社 1996年8 赵文静等编，数据结构辅导，西安交通大学出版社 1999年指导教师评语： 指导教师签名： 年 月 日成绩评定项 目权重成绩1、设计过程中出勤、学习态度等方面0.12、设计技术水平0.43、编程风格0.24、设计报告书写及图纸规范程度0.3总 成 绩