公共基础1-数据结构与算法介绍.ppt

线性表除了可以采用顺序存储结构，还可以采用链式存储结构。采用链式存储结构的线性表称为线性链表。 链式存储结构的每个结点有两个域，一个用于存放数据，一个用于存放指针。 链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素的逻辑关系可以不一致，而数据之间的逻辑关系由指针域来确定的。 access 链式存储方式既可以用于表示线性结构（线性表），也可以用于表示非线性结构（如：树）。 循环链表是一种特殊线性链表。 2005.4（5）下列对于线性链表的描述中正确的是 A) 存储空间不一定是连续，且各元素的存储顺序是任意的 B) 存储空间不一定是连续，且前件元素一定存储在后件元素的前面 C) 存储空间必须连续，且前件元素一定存储在后件元素的前面 D) 存储空间必须连续，且各元素的存储顺序是任意的 ?2006.4（5）下列叙述中正确的是 A．线性链表是线性表的链式存储结构 B．栈与队列是非线性结构 C．双向链表是非线性结构 D．只有根结点的二叉树是线性结构 ? 2008.9（4）下列叙述中正确的是（?）。 A）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C）顺序存储结构能存储有序表，链式存储结构不能存储有序表D）链式存储结构比顺序存储结构节省存储空间 ? 2009.3（1）下列叙述中正确的是 A 栈是“先进先出”的线性表 B 队列是“先进后出”的线性表 C 循环队列是非线性结构 D 有序线性表既可以采用顺序存储结构，也可以采用链式存储结构 树的基本概念 树是一种简单的非线性结构。 树中，所有的数据元素之间的关系具有明显的层次特征。 在树的图形表示，总认为用直线连起来的两个端点，上端是前件，下端是后件，表示前后件关系的箭头就可以省略。 厦门理工学院 机械系 电子系 商学系 财务管理 电子商务 A F E B D G 树的术语 结点：一个数据元素，ADBGEF都称为结点 父结点：每个结点只有一个前件，称为父节点。D、B的父节点是A。 树的根节点：树中，没有前件的节点只有一个，称为树的根节点，简称树的根。该树，根节点是A。 子结点：每一个节点可以有多个后件，它们都称为该结点的子结点。A的子结点是D、B. 叶子结点：没有后件的结点称为叶子结点。G、E、F是叶子结点。 结点的度：一个结点所拥有的后件个数。A的度为2，D的度有为3，B的度为0. 树的度：所有结点中的最大的度称为树的度。该树的度为3. 树的层次：根结点在一层，依次递增。A为一层，DB为二层，GEF为三层。 树的深度：树的最大层次。该树的深度为3. 子树：以某个结点的一个子结点为跟构成的树称为该结点的一棵子树。A有两棵子树，分别是DGEF，B。 A F E B D G A F E B D H G 二叉树的基本性质 性质三：在任意的二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。 注：二叉树的结点，只有三种，一种是度数为0的结点，即叶子结点；一种是度数为1的结点； 最后一种是度数为2的结点。所以二叉树的总节点数=N0+N1+N2 =N0+2N2+1 性质四：具有N个结点的二叉树，其深度至少为[log2n]+1,其中 [log2n] 表示取[log2n]的整数部分。 A F E B D H G 满二叉树 即每一层上都含有最大结点数。 A F E B D H G 4 2 3 1 6 7 8 9 10 11 12 13 14 15 5 完全二叉树 除最后一层外，每一层都取最大结点数，最后一层结点都集中在该层最左边的若干位置。 4 2 3 1 6 7 8 9 10 11 12 5 非完全二叉树 4 2 3 1 6 7 8 9 10 11 12 5 完全二叉树 二叉树的遍历 二叉树的遍历是指不重复地访问二叉树中的所有结点。 遍历需要访问根结点、左子树上的所有结点、右子树上的所有结点。在遍历时，一般先遍历左子树，然后遍历右子树。在这个原则下，根据访问根结点的次序分为三种： 1.前序遍历（DLR）：首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。 二叉树的遍历 2.中序遍历(LDR)：首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。 3.后序遍历(LRD)：首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历