何松柏《数据结构课程设计》.doc

1、长沙理工大学数据结构课程设计报告何 松 柏学 院 城 南 学 院 专 业 计算机科学与技术 班 级 计算机 0701 班 学 号 200786250119 学生姓名 何 松 柏 指导教师 肖增良 课程成绩 完成日期 2009 年 9 月 16 日 课程设计成绩评定学 院 计算机与通信工程 专 业 计算机科学与技术班 级 计算机 07-01 学 号 200786250119学生姓名 何松柏 指导教师 肖增良 课程成绩 完成日期 2009 年 09 月 16日指导教师对学生在课程设计中的评价评 分 项 目 优 良 中 及 格 不 及 格课程设计中的创造性成果学生掌握课程内容的程度课 程 设 计 完

2、 成 情 况课 程 设 计 动 手 能 力文 字 表 达学 习 态 度规 范 要 求课程设计论文的质量指导教师对课程设计的评定意见综合成绩 指导教师签字 年 月 日课程设计任务书城南学院 计算机科学与技术专业课程名称二叉树的建立和后序遍历的演示 时间 200920010 学年第 1 学期12 周学生姓名 何松柏 指导老师 肖增良题 目 二叉树的建立和后序遍历的演示主要内容：建立一个链式存储结构的栈，存放二叉树的节点，并利用二叉树的后序非递归算法，实现基本的插入，删除，查找等功能，并实现二叉树的后序遍历算法。要求：（1）通过实际项目的分析、设计、编码、测试等工作，掌握用C 语言来开发和维护软件。

3、（2）按要求编写课程设计报告书，能正确编写分析、设计、编码、测试等技术文档和用户使用手册。应当提交的文件：（1）课程设计学年论文。（2）课程设计附件（主要是源程序） 。基于 Linux 下 Web 服务器的配置和完善 第 1 页 共 15 页二叉树的建立和后序遍历的演示学生姓名：何松柏 指导老师：肖增良摘 要：二叉树是每个结点最多有两个子树的有序树。通常节点的子树被称作“左子树 ”（left subtree）和 “右子树”（right subtree） 。遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二

4、叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。后序遍历是先按遍历左子树，然后遍历右子树，最后访问根节点。而访问下一层节点是，必须记录上一层的节点信息，便于访问结束后退回上一层节点，所以用栈才存储节点信息。 Abstract:Binary 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“. Trav

5、ersal of a tree is the most basic computing, the so-called binary tree traversal, that is, according to certain rules and order of every 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 conv

6、erted into a linear sequence to express. After the traversal is to their left subtree traversal, and then traverse the right subtree, 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

7、 of the layer of nodes, so we can use stack storage node information.关键词：二叉树 递归后序遍历 非递归后序遍历 栈Key words:Binary tree After the recursive traversal After the non-recursive traversal 基于 Linux 下 Web 服务器的配置和完善 第 2 页 共 15 页1 引 言在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树” （left subtree）和“右子树 ”（right subtree）

8、 。二叉树常被用作二叉查找树和二叉堆。后序遍历是二叉树遍历的一种。后序遍历指在访问根结点、遍历左子树与遍历右子树三者中，首先遍历左子树，然后遍历右子树，最后遍历访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。后序遍历有递归算法和非递归算法两种。栈（stack）在计算机科学中是限定仅在表尾进行插入或删除操作的线形表。它是是一种数据结构，它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来） 。所以它非常适合存储二叉树的节点信息。1.1 课题背景自 1946 年第一台计算机问世以来,

9、计算机产业的飞速发展已远远超出人们对它的预料，在某些生产线上，甚至几秒钟就能生产出一台微型计算机，产量猛增，价格低廉，这就使它的应用范围迅速扩展。如今，计算机已深入到人类社会的各个领域。计算机的应用已不再局限于科学计算，而更多地用于控制管理用数据处理等非数值计算的处理工作。数据结构作为一门独立的课程最早是美国的一些大学开设的，1968 年美国唐欧克努特教授开创了数据结构的最初体系，他所著的计算机程序设计技巧第一卷基本算法是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。从 60 年代末到 70 年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们就越

10、来越重视数据结构，认为程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法。从 70 年代中期到 80 年代初，各种版本的数据结构著作就相继出现。目前在我国， 数据结构也已经不仅仅是计算机专业的教学计划中的核心课程之一，而且是其它非计算机专业的主要选修课程之一。 基于 Linux 下 Web 服务器的配置和完善 第 3 页 共 15 页“数据结构”在计算机科学中是一门综合性的专业基础课。 “数据结构”的研究不仅涉及到计算机的硬件的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储中的分配问题。在研究信息检索时也必须考虑如何组织数据

11、，以便查找和存取数据元素更为方便。因此，可以认为“数据结构”是介于数学，计算机硬件和计算机软件三者之间的一门核心课程。在计算机科学中， “数据结构”不仅是一般的程序设计（特别是非数值计算的程序）的基础，而且是设计和实现编译程序、操作系统、数据库系统用其他系统程序和大型应用程序的重要基础。 “数据结构”的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型的观点来讨论数据，已成为一种新的趋势，越来越被人们所注视。1.2 课题研究的目的和意义（1）在此过程中我们将会了解编程的一些方法和技巧，认识到实现一个问有提出问题、分析问题、设计

12、问题、实现等环节。此实践过程会是大家熟练掌握基本的数据结构和常用的算法，并最终设计一个能够解决实际问题并具有一定规模的大学数据课程设计。（2）这次做程序设计目的是为更好地掌握 C 语言编写数据结构程序的方法和技巧，了解 C 语言的强大的功能，更好地学习 C 语言，并且在这个过程中更好地锻炼自己的动手能力和实践能力。（3）通过对此次数据结构大型作业内容的分析，锻炼学生分析与编写大型软件代码的能力。通过与同组同学的合作，锻炼协作的能力。1.3 需求分析二叉树一种数据结构，用于保存和处理树状的数据，比如家谱。他的应用极为广泛，因为根据数据结构的理论，任何复杂的树够可以转换为二叉中并进行处理，二叉树在

13、排序、查找、大规模数据索引方面有很多很多应用。而且二叉树排序是简单算法排序中速度最快的。基于 Linux 下 Web 服务器的配置和完善 第 4 页 共 15 页在二叉树的一些应用中，常常要求在树中查找具有某种特征的节点，或者对树中全部节点逐一进行某种处理。这就提出了遍历二叉树。根据遍历的方向的选择，就有了后序遍历二叉树。因此掌握二叉树的后序遍历二叉树算法非常重要，而且高效的后序遍历算法能够节省很多成本。2 设计思路与方案2.1 设计思路类是所有面向对象语言的共同特征，因此类是 C+中十分重要的概念，是实现面向对象程序设计的基础。是 C+的灵魂。C+支持面向过程的程序设计，也支持基于对象的程序

14、设计，又支持面向对象的程序设计。基于对象就是基于类，与面向过程的程序不同，基于对象的程序是以类和对象为基础的，程序的操作是围绕对象进行的。在此基础上利用了继承机制和多态性，就成为面向对象的程序设计。C+中对象的类型称为类，类代表了某一批对象的共性和特征，类是对象的抽象，而对象是类的具体实例。在类体中是类的成员列表，列出类中的全部成员。它是一种广义的数据类型，除了数据部分以外，还包括了对这些数据操作的函数。这体现了把数据和操作封装在一起。2.2 设计方案下面分 2 个部分来说明：（1）栈的数据结构设计采用线性存储结构template class Stackprivate:DataType *ba

15、se; /栈尾DataType *top; /栈顶int stacksize; /栈分配的长度; 基于 Linux 下 Web 服务器的配置和完善 第 5 页 共 15 页（2）二叉树的存储结构设计二叉树的节点类型，并作为二叉树的友元类便于二叉树进行操作template class TreeNodeTreeNode():lchild(NULL),rchild(NULL)friend class BiTree;private:DataType data;TreeNode *lchild,*rchild;二叉树的存储结构template class BiTreeprivate:TreeNode*

16、root; /树根DataType temp; /代表元素为空的符号，便于输入时使用;基于 Linux 下 Web 服务器的配置和完善 第 6 页 共 15 页3 系统实现 本程序主要包括栈头文件和二叉树头文件，其中栈头文件包括栈的建立，插入元素，删除元素。二叉树头文件主要阐述了非递归后序算法，具体情况如下图 3.1 所示。栈的建立插入元素删除元素后序算法图 3.1 系统流程图系统采用链栈为栈的存储结构链栈采用链表作为存储结构。为便于操作，采用带头结点的单链表实现栈。由于栈的插入和删除操作仅限制在表头位置进行，所以链表的表头指针就作为栈顶指针，如图 3.2 所示。系统实现基于 Linux 下

17、Web 服务器的配置和完善 第 7 页 共 15 页niltop 栈顶date next栈底图 3.2 链栈示意图3.1 栈的建立分配一块空间给栈底，栈顶指针指向最上面元素的上端，当栈的空间不够用时，追加空间。以下为具体实现代码：Stack:Stack()if(!(base=(DataType*)malloc(STACK_INIT_SIZE*sizeof(DataType) exit(1);top=base;stacksize=STACK_INIT_SIZE;3.2 插入栈顶元素由于栈的存储结构为先进后出，所以当插入新元素 e 后，e 处于这个栈的栈顶。具体实现下图 3.3 所示。an a1进栈出栈栈顶 栈底