第十二章数据结构.ppt

第十二章 数据结构 主要内容： 12.1数据结构的主要研究内容 12.2数据结构基本概念 12.3 数据的逻辑结构 12.4 线性表及其顺序存储结构 12.5栈和队列 12.6 树与二叉树 12.7 查找技术 12.8 排序技术 二叉树也可以采用两种存储方式：顺序存储结构和链式存储结构。 1．二叉树的顺序存储结构 这种存储结构适用于完全二叉树。其存储形式为：用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。 2．二叉树的链式存储结构 在顺序存储结构中，利用编号表示元素的位置及元素之间孩子或双亲的关系，因此对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。 常见的二叉树结点结构如下所示： ■ 12.6.4 二叉树的存储结构 Rchild item Lchild 二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。 二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按层次访问。 在遍历二叉树的过程中，一般先遍历左树，再遍历右树。在先左后右的原则下，根据访问结点的顺序，二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍历。下面分别介绍这三种遍历的方法。 ■ 12.6.5二叉树的遍历 线性链表分为单链表、双向链表和循环链表三种类型。在单链表中，每一个结点只有一个指针域，因此，在这种线性链表中，只能沿指针向链尾方向进行扫描，这对于某些问题的处理会带来不便，因为在这种链接方式下，由某一个结点出发，只能找到它的后件，而为了找出它的前件，必须从头指针开始重新寻找。因此，在某些应用中，对于线性链表中的每个结点设置两个指针，一个称为左指针(Llink)，指向其前件结点；另一个称为右指针(Rlink)，指向其后件结点，这种链表称为双向链表。循环链表与单链表的区别仅仅在于其尾结点的链域值不是空，而是一个指向头结点的指针。循环链表的主要优点是：从表中任一结点出发都能通过后移操作而扫描整个循环链表。但对单链表来说，只有从头结点开始才能扫描表中全部结点。 ■ 12.5.1 栈及其基本运算 栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制，故又称运算受限的线性表。栈和队列被广泛应用于各种程序设计中。 12.5栈和队列 1．栈的基本概念 栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。 （1）通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。 （2）当表中没有元素时称为空栈。 （3）栈顶元素总是最后被插入的元素，栈底元素总是最先被插入的元素。 （4）栈为后进先出（Last In First Out，简称为LIFO）或先进后出（First In Last Out，简称为FILO）的线性表。 栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中“必威体育精装版”的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。例如元素是以，，…， 的顺序进栈，退栈的次序却是，，…，。在顺序存储结构下，对这种类型线性表的插入与删除运算是不需要移动表中其他数据元素的。 栈的顺序存储结构示意图如图12-8 所示。通常用指针top来指示栈顶的位置，用指针bottom指向栈底。栈中插入一个元素称为入栈运算，从栈中删除一个元素(即删除栈顶元素)称为退栈运算。栈顶指针top动态反映了栈中元素的变化情况。 与一般的线性表一样，在程序设计语言中，用一维数组S(1：m)作为栈的顺序存储空间，其中m为栈的最大容量。通常，栈底指针指向栈空间的低地址一端(即数组的起始地址这一端)。在栈的顺序存储空间S(1：m)中，S(bottom)通常为栈底元素(在栈非空的情况下)，S(top)为栈顶元素。top=0表示栈空，top=m表示栈满。 2．栈的基本运算 栈具有记忆作用，栈的基本运算主要包括入栈、退栈及读栈顶元素三种。 （1）入栈运算：指在栈顶位置插入一个新元素。这个运算有两个基本操作：首先将栈顶指针进一(即top加1)，然后将新元素插入栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不可能再进行入栈操作。这种情况称为栈“上溢”错误。 （2）退栈运算：是取出栈顶元素并赋给一个指定的变量。这个运算有两个基本操作：首先将栈顶元素(栈顶指针指向的元素)赋给一个指定的变量，然后将栈顶指针退一(即top减1)。