数据结构说明书

1 / 15 数据结构说明书 目 录 引言 . 错误！未定义书签。 一、设计要求 . 错误！未定义书签。 二、算法原理及思想 . 1 1 、 遍 历 概念 . 1 2 、 遍 历 方案 . 2 遍 历 方案 . 2 三种遍历的命名 .2 / 15 . 2 3 、 二 叉 树 的 链 式 存 储 结构 . 2 、结点的结构 . 2 、 结 点 的 类 型 说明 . 3 、 二叉链表 . 3 4 、 二 叉 树 的 非 递 归 遍历 . 4 先序非递归算法 . 4 中序非递归算法 . 5 后序非递归算3 / 15 法 . 6 三、遍历过程 . 6 四、程序测试 . 8 五、实验 总结 . 8 六、参考文献 . 9 附录：源代码 . 10 1 选题背景 数据结构在 计算机科学中是一门综合性的专业基础课 .数据结构的研究不仅涉及到计算机的硬件的研究范围 ,而且和计算机软件的研究有着更密切的关系 ,无论是编译程序还是操作系统 ,都涉及到数据元素在存储器中的分配4 / 15 问题 .在研究信息检索时也必须考虑如何组织数据 ,以便查找和存取数据元素更为方面 .因此 ,可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程 .在计算机科学中 ,数据结构不仅是一般程序设计的基础 ,而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。 树是一种重要的非线 性数据结构，直观地看，它是数据元素按分支关系组织起来的结构，很象自然界中的树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。满二叉树，完全二叉树，排序二叉树。 二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树， 而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。此程序主要实现二叉树的遍历并且是基于栈的非递归遍历方法。 2 方案论证 遍历概念 所谓遍历是指沿着某条搜索路线，依次对树中每个5 / 15 结点均做一次且仅做一次 访问。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。 遍历方案 遍历方案 从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基 本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作： 访问结点本身， 遍历该结点的左子树， 遍历该结点的右子树。 以上三种操作有六种执行次序： NLR、 LNR、 LRN、 NRL、 RNL、 RLN。 三种遍历的命名 根据访问结点操作发生位置命名： NLR：前序遍历 ) 访问结点的操作发生在遍历其左右子树之前。 LNR：中序遍历 访问结点的操作发生在遍历其左右 子树之中。 LRN：后序遍历 访问结点的操作发生在遍历其左右子树之后。 6 / 15 二叉树的链式存储结构 结点的结构 二叉树的每个结点最多有两个孩子。用链接方式存储二叉树时，每个结点除了存储结点本身的数据外，还应设置两个指针域 lchild 和 rchild，分别指向该结点的左孩子和右孩子。结点的结构为： 图 1 链式存储结点结构 结点的类型说明 typedef struct BiNode DataType data; /数据域 struct BiNode *LChild; /左孩子 struct BiNode *RChild; /右孩子 BiTNode,*BiTree; 二叉链表 在一棵二叉树中，所有类型为 BinTNode的结点，再加上一个指向开始结点的 BinTree 型头指针 root，就构成了二叉树的链式存储结构，并将其称为二叉链表。如图 2所示： 图 2 二叉链表存储的二叉树 注意： 一个 二叉链表由根指针 root惟一确定。若二叉树为空，则 root=NULL；若结点的某个孩子不存在，则相应7 / 15 的指针为空。 具有 n 个结点的二叉链表中，共有 2n个指针域。其中只有 n-1个用来指示结点的左、右孩子，其余的 n+1 个指针域为空。 /建立二叉树的二叉链表存贮结构 void CreateBiTree DataType ch; ch = getchar; if else *bt = malloc); -data = ch; CreateBiTree-LChild); *bt = NULL;CreateBiTree-RChild); 二叉树的非递归遍历 先序非递归算法 Void PreOrderTree int top = -1; BiTNode* StackMAX_STACK_SIZE=NULL; BiTNode* p; p = root; while while top+; Stacktop = malloc); if if return; 摘 要 数据结构是研究与数据之间的关系，我们称这一关系为数据的逻辑结构，简 8 / 15 称数据结构。当数据的逻辑结构确定以后，数据在物理空间中的存储方式，称为 数据的存储结构。相同的逻辑结构可以具有不同的存储结构，因而有不同的算法。 本次课程设计，程序中的数据采用“树形结构”作为其数据结构。具体采用 的是“二叉排序树”，并且使用“一维数组”来作为其存储结构。一维数组顺序表存储结构是用一组地址连续的存储单元依次自上而下、自左而右存储完全二叉树上的结点元素；本课程设计实现了二叉排序树的创建、中序遍历、计算二叉排序树的平均查找长度和删除二叉排序树中某个结点。 本课程主要介绍了本课题的开发背景，所要完成的功能和开发的过程。重点 说明了系统的设计思路、总体设计、各个功能模块的设计与实现方法。 关键词：二叉排序树的实现； C语言；数据结构；线性表；顺序表；中序遍历。 目录 摘 要 . I 9 / 15 1 课 题 背 景 的 介绍 . 3 课 题 背景 . 3 目的 . 3 2 需求分析 . 3 课 程 设 计 题 目 、 任 务 及 要求 . 3 课程设计思想 . 4 3 系统总体设计 . 5 系 统 模 块 划分 . 10 / 15 5 二 叉 排 序 树 的 生 成 过程 . 5 主 要 功 能 模 块 设计 . 5 4 系统详细设计 . 7 主 函 数 菜 单 模块 . 7 查 找 模块 . 8 插 入 模块 . 9 中 序 遍 历 模块 . 10 删除模块 .11 / 15 . 11 5 系 统 连 编 与 运行 . 13 6 总 结 . 14 参考文献 . 15 附录 .14 A）课题背景的介绍 课题背景 随着经济的迅速发展，各行各业纷纷应用计算机数据信息管理。当然数据信息是一个很笼统的概念，随着现代信息的大量增加，其处理难度也越来越大，如何对各个数据信息进行更好的树立，这就是我们研究这个课题的目的。 在计算机迅速发展的今天，将计算机这一信息处理器应用于实际数据问题问题的信息计算已是势必所然，而且这也将数据信息处理带来前所未有的改变。采用计算机对数12 / 15 据的信息处理是信息科学化和现代化的重要标志，它也给各行各业带来了明显的经济效益。主要体现在：极大地提高了工作人员的工作效率，大大地减少了以往的手工操作的各种弊端，同时也加强和规范掌握对于数据信息的计算。 目的 本课题运用 C 语言进行开发， C语言能够简单的进行编译一些程序，来实现对一些问题的解决。它虽然比较简单的处理一些问题，但却有更高的效率。它能够被大多数用户所接受，因为它能够呈现出清晰的界面，是人们能够很好的理解。能在一些方面给人们更好的服务，成为人们的好帮手。 经过这一个学期对数据结构的学习，我们都学到了不少东西，可能有些学的还不够理想，但无论如何这些知识都为我们的下一步学习打下了坚实的基础。做这么一个课程设计，一方面是为了检查我们一个学期以来的学习成果，另一方面也是为了让我们进一步的掌握和运用它，同时也让 我们认清自己的不足之处和薄弱环节，加以弥补和加强。 B）需求分析 课程设计题目、任务及要求 二叉排序树。用顺序表作存储结构 以回车为输入结束标志 ,输入数列 L，生成一棵二叉排序树 T； 13 / 15 对二叉排序树 T作中序遍历 ,输出结果； 计算二叉排序树 T查找成功的平均查找长度 ,输出结果； 输入元素 x,查找二叉排序树 T:若存在含 x 的结点 ,则删除该结点 ,并作中序遍历；否则输出信息“无 x”； 课程设计思想 建立二叉排序树采用 边查找边插入的方式。查找函数采用递归的方式进行查找。如果查找成功则不应再插入原树，否则返回当前结点的上一个结点。然后利用插入函数将该元素插入原树。 对二叉树进行中序遍历采用递归函数的方式。在根结点不为空的情况下，先访问左子树，再访问根结点，最后访问右子树。 计算二插排序树的平均查找长度时，仍采用类似中序遍历的递归方式，用 s 记录总查找长度， j 记录每个结点的查找长度， s 置初值为 0，采用累加的方式最终得到总查找长度 s。平均查找长度就等于 s/i。 删除结点函数，采用边查找边删除的 方式。如果没有查找到，则不对树做任何的修改；如果查找到结点，则分四种情况分别进行讨论： 1、该结点左右子树均为空； 2、该结点仅左子树为空； 14 / 15 3、该结点仅右子树为空； 4、该结点左右子树均不为空。 C）系统总体设计 系统模块划分 二叉排序树是一种动态树表。 二叉排序树的定义：二叉排序树或者是一棵空树， 或者是一棵具有如下性质的二叉树： 若它的左子树非空，则左子树上所有结点的值均小于根结点的值； 若它的右子树非空，则右子树上所有结点的值均大于根结点的值； 左、右子树本身又各是一棵二叉排序树。 二叉排序树的生成过程 二叉排序树的生成，采用递归方式的边查