线性结构，数组、矩阵和广义表，树与二叉树，图

NULL

考纲

线性结构

基本概念

• 每个元素最多只有一个出度和入度 ，表现为一条线状。线性表按照储存方式可分为顺序表和链表

储存结构

• 顺序存储：用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的元素物理上也相邻。

• 链式存储：存储各数据元素的结点的地址并不要求是连续的，数据元素逻辑上相邻，物理上分开。

线性表

• 顺序存储和链式存储对比

  

• 在空间方面，因为链表还需要存储指针，因此有空间浪费存在。

• 在时间方面，由顺表和链表的存储方式可知，当需要对元素进行破坏性操作（插入、删除）时，链表效率更高，因为其只需要修改指针指向即可，而顺序表因为地址是连续的，当删除或插入一个元素后，后面的其他节点位置都需要变动。

• 而当需要对元素进行不改变结构操作时（读取、查找），顺序表效率更高，因为其物理地址是连续的，如同数组一般，只需按索引号就可快速定位，而链表需要从头节点开始，一个个的查找下去。

单链表

• 单链表的插入和删除

  

• 在上图中p所指向的节点后插入s所指向的节点，操作为：

  1 2	s -> next = p -> next; p -> next = s;

• 同理，在单链表中删除p所指向节点的后继节点q时，操作为：

  1 2	p -> next = p -> next -> next; free(p);

栈和队列

• 队列和栈的基本特点：

  • 队列和栈都属于线性结构。
  • 队列是一种先进先出（FIFO）的结构，包括队头和队尾。
  • 栈是一种先进后出（LIFO）的结构，只有栈顶元素可以进出。

• 循环队列的特点：

  • 在循环队列中，头指针指向第一个元素，尾指针指向最后一个元素的下一个位置。
  • 当队列为空时，头尾指针相等（head=tail）。
  • 当队列满时，头尾指针也相等（head=tail），这会导致无法区分队列是空还是满。
  • 为解决这个问题，通常循环队列会少存储一个元素。
  • 这使得队列满的条件变为了tail+1=head，或者更通用地，使用取余操作：(tail+1)%size=head。
  • 循环队列的长度可以通过公式计算：(Q.tail - Q.head) % size。

• 优先队列的特点：

  • 优先队列是一种将元素赋予优先级，并在访问时删除具有最高优先级的元素的数据结构。
  • 堆结构常用于实现优先队列，因为元素的进队列顺序不决定元素的优先级。

串

• 字符串是一种特殊的线性表，其数据元素都为字符。

• 空串：长度为0的字符串，没有任何字符。

• 空格串：由一个或多个空格组成的串，空格是空白字符，占一个字符长度。

• 子串：串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主串，空串是任意串的子串。

• 串的模式匹配算法：子串的定位操作，用于查找子串在主串中第一次出现的位置的算法。

• 基本的模式匹配算法：也称为布鲁特一福斯算法，其基本思想是从主串的第1个字符起与模式串的第1个字符比较，若相等，则继续逐个字符进行后续的比较；否则从主串中的第2个字符起与模式串的第1个字符重新比较，直至模式串中每个字符依次和主串中的一个连续的字符序列相等时为止，此时称为匹配成功，否则称为匹配失败。

• KMP算法：对基本模式匹配算法的改进，其改进之处在于：每当匹配过程中出现相比较的字符不等时，不需要回溯主串的字符位置指针，而是利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的距离，再继续进行比较。

数组、矩阵和广义表

数组

• 数组是定长线性表在维度上的扩展，即线性表中的元素又是一个线性表。N维数组是一种“同构”的数据结构，其每个数据元素类型相同、结构一致。

• 一个m行列的数组表示如下：

  

• 其可以表示为行向量形式或者列向量形式线性表，单个关系最多只有一个前驱和一个后继，本质还是线性的。

• 数组结构的特点：数据元素数目固定：数据元素类型相同：数据元素的下标关系具有上下界的约束且下标有序。

• 数组数据元素固定，一般不做插入和删除运算，适合于采用顺序结构

• 数组存储地址的计算，特别是二维数组，要注意理解，假设每个数组元素占用存储长度为len，起始地址为a，存储地址计算如下：

  

矩阵

• 特殊矩阵：矩阵中的元素（或非0元素）的分布有一定的规律。常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵。

• 稀疏矩阵：在一个矩阵中，若非零元素的个数远远少于零元素个数，且非零元素的分布没有规律。

• 存储方式为三元组结构，即存储每个非零元素的(行，列，值)。

广义表

• 广义表是线性表的推广，是由0个或多个单元素或子表组成的有限序列。

• 广义表与线性表的区别：线性表的元素都是结构上不可分的单元素，而广义表的元素既可以单元素，也可以是有结构的表。

• 广义表一般记为：

  

• 其中LS是表名，ai是表元素，它可以是表（称为子表），也可以是数据元素（称为原子）。其中n是广义表的长度（也就是最外层包含的元素个数），n=0的广义表为空表：而递归定义的重数就是广义表的深度，即定义中所含括号的重数（单边括号的个数，原子的深度为0，空表的深度为1）。

• head()和tail()：取表头（广义表第一个表元素，可以是子表也可以是单元素）和取表尾（广义表中，除了第一个表元素之外的其他所有表元素构成的表，非空广义表的表尾必定是一个表，即使表尾是单元素）操作。

树与二叉树

树

• 树结构是一种非线性结构，树中的每一个数据元素可以有两个或两个以上的直接后继元素，用来描述层次结构关系。

• 树是n个结点的有限集合（n>=0），当n=0时称为空树，在任一颗非空树中，有且仅有一个根节点；其余结点可分为m（m>=0)个互不相交的有限子集T1，T2 ... Tm。其中每个Ti文都是一棵树，并且成为根结点的子树。

• 树的结构如下图所示：

  

• 树的基本概念如下：

  1. 亲属关系：

     • 双亲、孩子和兄弟之间的关系
     • 结点的子树根是孩子，相应地，该点是子结点的双亲
     • 具有相同双亲的结点是兄弟

  2. 结点度：

     • 结点的子树个数定义为结点的度

  3. 叶子结点：

     • 叶子结点也叫终端结点
     • 指度为0的结点

  4. 内部结点：

     • 度不为0的结点
     • 也称为分支结点或非终端结点
     • 除根结点外，分支结点也称为内部结点

  5. 结点层次：

     • 根是第一层
     • 根的孩子是第二层
     • 以此类推，结点在第i层，孩子结点在第i+1层

  6. 树的高度：

     • 最大层数是树的高度（或深度）

  7. 有序（无序）树：

     • 树中子树从左到右有次序称为有序树
     • 否则称为无序树

二叉树

• 二叉树是n个节点的有限集合，它或者是空树，或者是由一个根节点及两颗互不相交的且分别称为左、右子树的二叉树所组成。与树的区别在于每个根节点最多只有两个孩子结点。

• 二叉树的主要特性如下：

  

• 设一棵二叉树上叶结点数为n0，单分支结点数为n1，双分支结点数为n2，则总结点数=n0+n1+n2。在一棵二叉树中，所有结点的分支数（即度数）应等于单分支结点数加上双分支结点数的2倍，即总的分支数=n1+2n2。由于二叉树中除根结点以外，每个结点都有唯一的一个分支指向它，因此二叉树中：总的分支数=总结点数-1。

• 满二叉树：每层都是满的

• 完全二叉树的k-1层是满结点的，第k层从左至右是满的

• 如下图：

  

二叉树的存储结构

• 二叉树的顺序存储结构：

  • 采用一组连续的存储单元，按照从上到下、从左到右的顺序存储节点。

  • 对于深度为k的完全二叉树，每层节点数除第k层外都是上一层的两倍，节点编号可推知双亲、左孩子、右孩子节点的编号。假设节点编号为n，则有如下关系：

    

• 二叉树的链式存储结构：

  • 使用二叉链表存储二叉树节点，每个节点存储自身数据以及左孩子和右孩子节点的指针，即 “一个数据+两个指针”。
  • 每个二叉链表节点对应一个二叉树节点，头指针指向根节点。

二叉树的遍历

• 一颗非空的二叉树由根节点、左子树、右子树三部分组成，遍历这三部分，也就遍历了整颗二叉树。这三部分遍历的基本顺序是先左子树后右子树，但根节点顺序可变，以根节点访问的顺序为准有下列三种遍历方式：

  • 先序（前序）遍历：根左右。
  • 中序遍历：左根右。
  • 后序遍历：左右根。
  • 层次遍历：按层次，从上到下，从左到右。

• 示例：

  

  • 前序：12457836

  • 中序：42785136

  • 后序：48752631

线索二叉树

• 引入线索二叉树的目的是为了在遍历二叉树时能够方便地获取某节点的前驱节点和后继节点信息。在传统的二叉树链式存储结构中，我们只能轻松访问节点的左孩子和右孩子，但无法迅速获取前驱和后继节点，因此我们考虑扩展链式存储，添加两个指针域分别指向前驱和后继节点。然而，这种方法可能会浪费存储空间，因此我们需要一种更精巧的实现方法。

• 如果我们将每个节点的二叉树使用二叉链表进行存储，必然会有一个空指针域。我们可以充分利用这些空指针域来存储节点的前驱和后继节点信息。为了区分指针域究竟存储的是孩子结点还是遍历节点，我们引入两个标志位，如下所示

  

  • 当二叉树的二叉链表采用上述结构时，我们称之为线索链表，其中指向前驱和后继节点的指针称为线索。这样的二叉树被称为线索二叉树。这种实现方法既充分利用了存储空间，又能够高效获取前驱和后继节点信息。

最优二叉树

• 最优二叉树通常被称为哈夫曼树，它是一种带权路径长度最短的树，相关概念如下：

  名称	定义
  路径	树中一个结点到另一个结点之间的通路。
  结点的路径长度	路径上的分支数目。
  树的路径长度	根节点到达每一个叶子节点之间的路径长度之和。
  权	节点代表的值。
  结点的带权路径长度	该结点到根结点之间的路径长度乘以该节点的权值。
  树的带权路径长度（树的代价）	树的所有叶子节点的带权路径长度之和。

  

• 最优二叉树的构造：

  • 哈夫曼树的求法：给出一组权值，将其中两个最小的权值作为叶子节点，其和作为父节点，组成二叉树，而后删除这两叶子节点权值，并将父节点的值添加到该组权值中。重复进行上述步骤，直至所有权值都被使用完。

  • 构造出的哈夫曼树中，所有初始给出的权值都作为了叶子节点，此时，求出每个叶子节点的带权路径长度，而后相加，就是树的带权路径长度，这个长度是最小的。

  • 构造过程如下：

    

树和森林

• 树的存储结构

  • 双亲表示法：用一组连续的地址单元存储树的节点，并在每个节点中附带一个指示器，指出其双亲节点所在数组元素的下标。
  • 孩子表示法：在存储结构中用指针指示出节点的每个孩子，为树中每个节点的孩子建立一个链表。
  • 孩子兄弟表示法：又称为二叉链表表示法，为每个存储节点设置两个指针域，分别指向该节点的第一个孩子和下一个兄弟节点。

• 树和森林

  • 由于树中每个节点可能有多个子树，因此遍历树的方法有两种：
    • 先根遍历：先访问根节点，再依次遍历根的各颗子树
    • 后根遍历：先遍历根的各颗子树，再访问根节点。
  • 森林中有很多棵树，森林的遍历方法也分为两种，与树的遍历类似，就是对森林中的每棵树都依次做先根遍历或后根遍历。

• 树和二叉树的转换

  • 规则是：树的最左边节点作为二叉树的左子树，树的其他兄弟节点作为二叉树的右子树节点。

  • 示例如下图：采用连线法，将最左边节点和其兄弟节点都连接起来，而原来的父节点和兄弟节点的连线则断开，这种方法最简单，要求掌握。

    

查找二叉树

• 查找二叉树上的每个节点都存储一个值，且每个节点的所有左孩子结点值都小于父节点值，而所有右孩子结点值都大于父节点值，是一个有规律排列的二叉树，这种数据结构可以方便查找、插入等数据操作

• 二叉排序树的查找效率取决于二叉排序树的深度，对于结点个数相同的二叉排序树，平衡二叉树的深度最小，而单枝树的深度是最大的，故效率最差

平衡二叉树

• 前面讲过查找（排序）二叉树，特点是所有左子树值小于根节点值，所有左子树值大于根节点值，而这个特点可以构造出多个不同的二叉树，并不唯一，因此提出平衡二叉树的概念，在查找二叉树特点的基础上，要求每个节点的平衡度只能为0或1或-1

• 节点的左右子树深度就是其左右子树各自的层数，而后将左子树深度减去右子树深度，就得到了该节点的平衡度。因此，平衡二叉树就是任意左右子树层次相差不超过1

图

基本概念

• 图也是一种非线性结构，图中任意两个节点间都可能有直接关系。

  定义	描述
  无向图	图的结点之间连接线是没有箭头的，不分方向。
  有向图	图的结点之间连接线是箭头，区分A到B和B到A是两条线。
  完全图	无向完全图中，节点两两之间都有连线；有向完全图中，节点两两之间都有互通的两个箭头。从任意节点出发，都能直接到达任一另外节点。
  度	顶点的度是关联与该顶点的边的数目。在有向图中，顶点的度为出度和入度之和。
  出度	以该顶点为起点的有向边的数目。
  入度	以该顶点为终点的有向边的数目。
  路径	存在一条通路，可以从一个顶点到达另一个顶点，有向图的路径也是有方向的。
  连通图	针对无向图。若从顶点到顶点u之间是有路径的，则说明和u之间是连通的，若无向图中任意两个顶点之间都是连通的，则称为连通图。
  连通分量	针对无向图。无向图G的极大连通子图称为其连通分量。
  强连通图	针对有向图。若有向图任意两个顶点间都互相存在路径，即存在v到u，也存在u到v的路径，则称为强连通图。
  强连通分量	针对有向图。有向图中的极大连通子图称为其强连通分量。
  网	边带权值的图称为网。

图的储存

• 邻接矩阵：假设一个图中有n个节点，则使用n阶矩阵来存储这个图中各节点的关系，规则是若节点i到节点j有连线，则矩阵R[i,j]=1，否则为0。因此，如果是一个无向图，肯定是沿对角线对称的，只需要存储上三角或者下三角就可以了，而有向图则不一定对称。示例如下图所示：

  

  • 其中，图中从1到2有连通，那么[1,2]就标记为1，同时从2到1也有连通，那么[2,1]也为1

• 邻接链表：用到了两个数据结构，先用一个一维数组将图中所有顶点存储起来而后，对此一维数组的每个顶点元素，使用链表挂上和其有连线关系的结点的编号和权值，示例如下图所示：

  

  • 其中，V1的邻接点为V2,V4,V6，权值分别为6,1,50。其储存结构如上所示。

    

图的遍历

• 图的遍历是指从图的任意节点出发，沿着某条搜索路径对图中所有节点进行访问且只访问一次，分为以下两种方式：

  • 深度优先遍历：从任一顶点出发，遍历到底，直至返回，再选取任一其他节点出发，重复这个过程直至遍历完整个图；
  • 广度优先遍历：先访问完一个顶点的所有邻接顶点，而后再依次访问其邻接顶点的所有邻接顶点，类似于层次遍历。
  

图的最小生成树

• 假设有n个节点，那么这个图的最小生成树有n-1条边（不会形成环路，是树非图），这n-1条边会将所有顶点都连接成一个树，并且这些边的权值之和最小，因此称为最小生成树。

• 普里姆算法：从任意顶点出发，找出与其邻接的边权值最小的，此时此边的另外一个顶点自动加入树集合中，而后再从这这个树集合的所有顶点中找出与其邻接的边权值最小的，同样此边的另外一个顶点加入树集合中，依次递归，直至图中所有顶点都加入树集合中，此时此树就是该图的最小生成树。

• 克鲁斯卡尔算法（推荐）：这个算法是从边出发的，因为本质是选取权值最小的n-1条边，因此，就将边按权值大小排序，依次选取权值最小的边，直至囊括所有节点，要注意，每次选边后要检查不能形成环路。

  

  • 上图中，依次选择A-B: 100,A-E: 200,D-F: 200,A-D: 250,C-D: 300。到此已经囊括所有节点，就构成了最小生成树

图的拓扑序列

• AOV网（以顶点表示活动的网）：在有向图中，以顶点表示活动，用有向边表示活动之间的优先关系。

• AOV网用来表示大的工程项自执行计划，因此不能出现有向环，若存在，则意味着某项活动必须以自身任务的完成为先决条件，因此，若要检测一个工程是否可行，首先应检查对应的AOV网是否存在回路。检测的方法是对有向图构造其顶点的拓扑有序序列。

• 构造方法：将有向图的有向边作为活动开始的顺序，若图中一个节点入度为0，则应该最先执行此活动，而后删除掉此节点和其关联的有向边，再去找图中其他没有入度的结点：执行活动，依次进行，示例如下：