《何松柏《数据结构课程设计》》由会员分享，可在线阅读，更多相关《何松柏《数据结构课程设计》（25页珍藏版）》请在金锄头文库上搜索。
1、长沙理工大学长沙理工大学数据结构数据结构课程设计报告课程设计报告何何 松松 柏柏学学 院院 城城 南南 学学 院院 专专 业业 计算机科学与技术计算机科学与技术 班班 级级 计算机计算机 0701 班班 学学 号号 200786250119 学生姓名学生姓名 何何 松松 柏柏 指导教师指导教师 肖增良肖增良 课程成绩课程成绩 完成日期完成日期 2009 年年 9 月月 16 日日 课程设计成绩评定课程设计成绩评定学学 院院 计算机与通信工程计算机与通信工程 专专 业业 计算机科学与技术计算机科学与技术班班 级级 计算机计算机 07-01 学学 号号 200786250119学生姓名学生姓名 何
2、松柏何松柏 指导教师指导教师 肖增良肖增良 课程成绩课程成绩 完成日期完成日期 2009 年年 09 月月 16 日日指导教师对学生在课程设计中的评价指导教师对学生在课程设计中的评价 评分项目优良中及格不及格课程设计中的创造性成果学生掌握课程内容的程度课程设计完成情况课程设计动手 能力文字表达学习态度规范要求课程设计论文的质量指导教师对课程设计的评定意见指导教师对课程设计的评定意见综合成绩 指导教师签字 年 月 日课程设计任务书课程设计任务书城南学院 计算机科学与技术专业课程名称二叉树的建立和后序遍历的演示时间200920010 学年第 1 学期 12 周学生姓名何松柏指导老师肖增良题 目二叉
3、树的建立和后序遍历的演示主要内容：建立一个链式存储结构的栈，存放二叉树的节点，并利用二叉树的后序非递归算法，实现基本的插入，删除，查找等功能，并实现二叉树的后序遍历算法。要求： （1）通过实际项目的分析、设计、编码、测试等工作，掌握用C 语言来开发和维护软件。（2）按要求编写课程设计报告书，能正确编写分析、设计、编码、测试等技术文档和用户使用手册。应当提交的文件：（1）课程设计学年论文。（2）课程设计附件（主要是源程序） 。基于 Linux 下 Web 服务器的配置和完善 第 1 页 共 15 页二叉树的建立和后序遍历的演示二叉树的建立和后序遍历的演示学生姓名：何松柏学生姓名：何松柏 指导老师
4、：肖增良指导老师：肖增良摘 要：二叉树是每个结点最多有两个子树的有序树。通常节点的子树被称作“左子树”（left subtree）和“右子树”（right subtree） 。遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。后序遍历是先按遍历左子树，然后遍历右子树，最后访问根节点。而访问下一层节点是，必须记录上一层的节点信息，便于访问结束后退回上一层节点，所以用栈才存储节点信息。 Abstract:Abstract:B
5、inary tree is an orderly tree that each node hava no more than two sub-trees. Subtree node is usually referred to as the “left sub-tree“ and “the right sub-tree“. Traversal of a tree is the most basic computing, the so-called binary tree traversal, that is, according to certain rules and order of ev
6、ery tree of all nodes and each node have been visited once. Binary tree structure as a result of non-linear, therefore, the tree is to traverse all tree nodes can converted into a linear sequence to express. After the traversal is to their left subtree traversal, and then traverse the right subtree,
7、 and finally visit the root node. The visit to the next layer of nodes is the need to record its previous layers information, to facilitate return visits after the end of the layer of nodes, so we can use stack storage node information.关键词：二叉树 递归后序遍历 非递归后序遍历 栈Key words:Binary tree After the recursiv
8、e traversal After the non-recursive traversal 基于 Linux 下 Web 服务器的配置和完善 第 2 页 共 15 页1 引引 言言在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树” （left subtree）和“右子树” （right subtree） 。二叉树常被用作二叉查找树和二叉堆。后序遍历是二叉树遍历的一种。后序遍历指在访问根结点、遍历左子树与遍历右子树三者中，首先遍历左子树，然后遍历右子树，最后遍历访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。后序遍历有递归算法和
9、非递归算法两种。栈（stack）在计算机科学中是限定仅在表尾进行插入或删除操作的线形表。它是是一种数据结构，它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来） 。所以它非常适合存储二叉树的节点信息。1.1 课题背景课题背景 自 1946 年第一台计算机问世以来,计算机产业的飞速发展已远远超出人们对它的预料，在某些生产线上，甚至几秒钟就能生产出一台微型计算机，产量猛增，价格低廉，这就使它的应用范围迅速扩展。如今，计算机已深入到人类社会的各个领域。计算机的应用已不再局限于科学计算，而更多地用于控制管理用数据处理等
10、非数值计算的处理工作。数据结构作为一门独立的课程最早是美国的一些大学开设的，1968 年美国唐欧克努特教授开创了数据结构的最初体系，他所著的计算机程序设计技巧第一卷基本算法是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。从 60 年代末到 70 年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们就越来越重视数据结构，认为程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法。从 70 年代中期到 80 年代初，各种版本的数据结构著作就相继出现。目前在我国， 数据结构也已经不仅仅是计算机专业的教学计划中的核心课程之一，而且是其它非计算机
11、专业的主要选修课程之一。 基于 Linux 下 Web 服务器的配置和完善 第 3 页 共 15 页“数据结构”在计算机科学中是一门综合性的专业基础课。 “数据结构”的研究不仅涉及到计算机的硬件的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便查找和存取数据元素更为方便。因此，可以认为“数据结构”是介于数学，计算机硬件和计算机软件三者之间的一门核心课程。在计算机科学中， “数据结构”不仅是一般的程序设计（特别是非数值计算的程序）的基础，而且是设计和实现编译程序、操作系统、数据库系统用其
12、他系统程序和大型应用程序的重要基础。 “数据结构”的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型的观点来讨论数据，已成为一种新的趋势，越来越被人们所注视。1.2 课题研究的目的和意义课题研究的目的和意义 （1）在此过程中我们将会了解编程的一些方法和技巧，认识到实现一个问有提出问题、分析问题、设计问题、实现等环节。此实践过程会是大家熟练掌握基本的数据结构和常用的算法，并最终设计一个能够解决实际问题并具有一定规模的大学数据课程设计。（2）这次做程序设计目的是为更好地掌握 C 语言编写数据结构程序的方法和技巧，了解 C 语言的
13、强大的功能，更好地学习 C 语言，并且在这个过程中更好地锻炼自己的动手能力和实践能力。（3）通过对此次数据结构大型作业内容的分析，锻炼学生分析与编写大型软件代码的能力。通过与同组同学的合作，锻炼协作的能力。1.3 需求分析需求分析二叉树一种数据结构，用于保存和处理树状的数据，比如家谱。他的应用极为广泛，因为根据数据结构的理论，任何复杂的树够可以转换为二叉中并进行处理，二叉树在排序、查找、大规模数据索引方面有很多很多应用。而且二叉树排序是简单算法排序中速度最快的。基于 Linux 下 Web 服务器的配置和完善 第 4 页 共 15 页在二叉树的一些应用中，常常要求在树中查找具有某种特征的节点，
14、或者对树中全部节点逐一进行某种处理。这就提出了遍历二叉树。根据遍历的方向的选择，就有了后序遍历二叉树就有了后序遍历二叉树。因此掌握二叉树的后序遍历二叉树算法非常重要，而且高效的后序遍历算法能够节省很多成本。2 设计思路与方案设计思路与方案2.1 设计思路设计思路类是所有面向对象语言的共同特征，因此类是 C+中十分重要的概念，是实现面向对象程序设计的基础。是 C+的灵魂。C+支持面向过程的程序设计，也支持基于对象的程序设计，又支持面向对象的程序设计。基于对象就是基于类，与面向过程的程序不同，基于对象的程序是以类和对象为基础的，程序的操作是围绕对象进行的。在此基础上利用了继承机制和多态性，就成为面
15、向对象的程序设计。C+中对象的类型称为类，类代表了某一批对象的共性和特征，类是对象的抽象，而对象是类的具体实例。在类体中是类的成员列表，列出类中的全部成员。它是一种广义的数据类型，除了数据部分以外，还包括了对这些数据操作的函数。这体现了把数据和操作封装在一起。2.2 设计方案设计方案下面分 2 个部分来说明：（1）栈的数据结构设计采用线性存储结构template class Stackprivate:DataType *base; /栈尾DataType *top; /栈顶int stacksize; /栈分配的长度; 基于 Linux 下 Web 服务器的配置和完善 第 5 页 共 15 页（2）二叉树的存储结构设计二叉树的节点类型，并作为二叉树的友元类便于二叉树进行操作template class TreeNodeTreeNode():lchild(NULL),rchild(NULL)friend class BiTree;private
