第七章 数据结构

常见的数据结构包括数组、链表、栈、队列、哈希表、树、堆、图，它们可以从“逻辑结构”和“物理结构”两个维度进行分类。

  • 逻辑结构揭示了数据元素之间的逻辑关系。逻辑结构可分为“线性”和“非线性”两大类

  • 物理结构反映了数据在计算机内存中的存储方式，可分为连续空间存储（数组）和分散空间存储（链表）

线性结构比较直观，指数据在逻辑关系上呈线性排列；非线性结构则相反，呈非线性排列。

  • 线性数据结构：数组、链表、栈、队列、哈希表，元素之间是一对一的顺序关系。
  • 非线性数据结构：树、堆、图、哈希表。

非线性数据结构可以进一步划分为树形结构和网状结构。

  • 树形结构：树、堆、哈希表，元素之间是一对多的关系。
  • 网状结构：图，元素之间是多对多的关系。

值得说明的是，所有数据结构都是基于数组、链表或二者的组合实现的。例如，栈和队列既可以使用数组实现，也可以使用链表实现；而哈希表的实现可能同时包含数组和链表。

  • 基于数组可实现：栈、队列、哈希表、树、堆、图、矩阵、张量（维度 ≥3 的数组）等。
  • 基于链表可实现：栈、队列、哈希表、树、堆、图等。

1. 线性结构

  • 线性结构：每个元素最多只有一个出度和一个入度，表现为一条线状。线性表按存储方式分为顺序表和链表
  • 存储结构： 顺序存储：用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的元素物理上也相邻
  • 链式存储：存储各数据元素的结点的地址并不要求是连续的，数据元素逻辑上相邻，物理上分开

1.1 线性表

线性表 顺序存储和链式存储对比：

  • 在空间方面，因为链表还需要存储指针，因此有空间浪费存在
  • 在时间方面，由顺序表和链表的存储方式可知，当需要对元素进行破坏性操作(插入、删除）时，链表效率更 高，因为其只需要修改指针指向即可，而顺序表因为地址是连续的，当删除或插入一个元素后，后面的其他 节点位置都需要变动。而当需要对元素进行不改变结构操作时(读取、查找)，顺序表效率更高，因为其物理 地址是连续的，如同数组一般，只需按索引号就可快速定位，而链表需要从头节点开始，一个个的查找下去
1.1.1 数组

数组（array）是一种线性数据结构，其将相同类型的元素存储在连续的内存空间中。我们将元素在数组中的位置称为该元素的索引（index）。

  • 索引本质上是内存地址的偏移量。首个元素的地址偏移量是0

  • 在数组中访问元素非常高效，我们可以在 O(1)O(1) 时间内随机访问数组中的任意一个元素。

  • 数组的长度是不可变的。

    如果我们希望扩容数组，则需重新建立一个更大的数组，然后把原数组元素依次复制到新数组。这是一个 O(n)O(n) 的操作，在数组很大的情况下非常耗时。

数组的访问

1
2
3
4
5
6
7
8
/* 随机访问元素 */
int randomAccess(int *nums, int size) {
    // 在区间 [0, size) 中随机抽取一个数字
    int randomIndex = rand() % size;
    // 获取并返回随机元素
    int randomNum = nums[randomIndex];
    return randomNum;
}

数组的插入

需要将该元素之后的所有元素都向后移动一位，之后再把元素赋值给该索引。

1
2
3
4
5
6
7
8
9
/* 在数组的索引 index 处插入元素 num */
void insert(int *nums, int size, int num, int index) {
    // 把索引 index 以及之后的所有元素向后移动一位
    for (int i = size - 1; i > index; i--) {
        nums[i] = nums[i - 1];
    }
    // 将 num 赋给 index 处的元素
    nums[index] = num;
}

数组的删除

需要把删除位置的索引之后的元素都向前移动一位。

1
2
3
4
5
6
7
8
/* 删除索引 index 处的元素 */
// 注意：stdio.h 占用了 remove 关键词
void removeItem(int *nums, int size, int index) {
    // 把索引 index 之后的所有元素向前移动一位
    for (int i = index; i < size - 1; i++) {
        nums[i] = nums[i + 1];
    }
}

总的来看，数组的插入与删除操作有以下缺点。

  • 时间复杂度高：数组的插入和删除的平均时间复杂度均为 O(n)O(n) ，其中nn为数组长度。
  • 丢失元素：由于数组的长度不可变，因此在插入元素后，超出数组长度范围的元素会丢失。
  • 内存浪费：我们可以初始化一个比较长的数组，只用前面一部分，这样在插入数据时，丢失的末尾元素都是“无意义”的，但这样做会造成部分内存空间浪费。

数组查找

1
2
3
4
5
6
7
8
/* 在数组中查找指定元素 */
int find(int *nums, int size, int target) {
    for (int i = 0; i < size; i++) {
        if (nums[i] == target)
            return i;
    }
    return -1;
}

优点与局限

数组存储在连续的内存空间内，且元素类型相同。这种做法包含丰富的先验信息，系统可以利用这些信息来优化数据结构的操作效率。

  • 空间效率高：数组为数据分配了连续的内存块，无须额外的结构开销。
  • 支持随机访问：数组允许在 O(1)O(1) 时间内访问任何元素。
  • 缓存局部性：当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓存来提升后续操作的执行速度。

连续空间存储是一把双刃剑，其存在以下局限性。

  • 插入与删除效率低：当数组中元素较多时，插入与删除操作需要移动大量的元素。
  • 长度不可变：数组在初始化后长度就固定了，扩容数组需要将所有数据复制到新数组，开销很大。
  • 空间浪费：如果数组分配的大小超过实际所需，那么多余的空间就被浪费了。

数组存储地址的计算

假设每个数组元素占用内存长度为len，起始地址为a，存储地址计算如下：

1.1.2 链表

链表（linked list）是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过“引用”相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。

  • 链表除了包含值，还需额外保存一个引用（指针）。因此在相同数据量下，链表比数组占用更多的内存空间。
  • 我们通常将头节点当作链表的代称

单链表的插入和删除：

插入和删除改变两个节点引用（指针）即可，时间复杂度为 O(1)O(1)

插入操作：

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

删除操作：

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

单链表的访问：

在链表中访问节点的效率较低，时间复杂度O(1)O(1)

总结了数组和链表的各项特点并对比了操作效率。由于它们采用两种相反的存储策略，因此各种性质和操作效率也呈现对立的特点。

数组 链表
存储方式 连续内存空间 分散内存空间
容量扩展 长度不可变 可灵活扩展
内存效率 元素占用内存少、但可能浪费空间 元素占用内存多
访问元素 0(1) O(n)
添加元素 O(n) 0(1)
删除元素 O(n) 0(1)

1.2 队列与栈

  • 栈：先进后出，只有栈顶能进出

  • 队列：先进先出，分队头和队尾

1.3 串

  • 字符串是一种特殊的线性表，其数据元素都为字符
    • 空串：长度为0的字符串，没有任何字符
    • 空格串：由一个或多个空格组成的串，空格是空白字符，占一个字符长度
    • 子串：串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主串，空串是任意串的子串
  • 串的模式匹配算法：子串的定位操作，用于查找子串在主串中第一次出现的位置的算法
    • 基本的模式匹配算法：也称为布鲁特一福斯算法，其基本思想是从主串的第1个字符起与模式串的第1个 字符比较，若相等，则继续逐个字符进行后续的比较；否则从主串中的第2个字符起与模式串的第1个字 符重新比较，直至模式串中每个字符依次和主串中的一个连续的字符序列相等时为止，此时称为匹配成 功，否则称为匹配失败
    • KMP算法：对基本模式匹配算法的改进，其改进之处在于：每当匹配过程中出现相比较的字符不相等时， 不需要回溯主串的字符位置指针，而是利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的 距离，再继续进行比较

1.4 矩阵

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

  • 稀疏矩阵：在一个矩阵中，若非零元素的个数远远少于零元素个数，且非零元素的分布没有规律。存储方式 为三元组结构，即存储每个非零元素的(行，列，值)

2. 树

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

2.1 二叉树

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

2.1.1 常见二叉树类型
  • 完美二叉树：所有层的节点都被完全填满。在完美二叉树中，叶节点的度为0 ，其余所有节点的度都为2 ；若树的高度为 ℎ ，则节点总数为2h+1−12^{h+1}-1 ，呈现标准的指数级关系，反映了自然界中常见的细胞分裂现象。
  • **完全二叉树：**只有最底层的节点未被填满，且最底层节点尽量靠左填充。
  • **完满二叉树：**除了叶节点之外，其余所有节点都有两个子节点。
  • **平衡二叉树：**中任意节点的左子树和右子树的高度之差的绝对值不超过 1 。
2.1.2 二叉树的常用术语
  • 根节点（root node）：位于二叉树顶层的节点，没有父节点。
  • 叶节点（leaf node）：没有子节点的节点，其两个指针均指向 None 。
  • 边（edge）：连接两个节点的线段，即节点引用（指针）。
  • 节点所在的层（level）：从顶至底递增，根节点所在层为 1 。
  • 节点的度（degree）：节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2 。
  • 二叉树的高度（height）：从根节点到最远叶节点所经过的边的数量。
  • 节点的深度（depth）：从根节点到该节点所经过的边的数量。
  • 节点的高度（height）：从距离该节点最远的叶节点到该节点所经过的边的数量。

2.1.3 二叉树的重要特性

  • 二叉树第i层（i≥1）上最多有2i−12^{\mathrm{i}-1}个结点

  • 高度为k的二叉树最多有2k−12^{\mathrm{k}}-1个结点（k≥1)

  • 对于任何一棵二叉树，若其终端结点数为n0n_{0}，度为2的结点数为 n2，则n0 = n2 + 1n_{0}\:=\:n_{2}\:+\:1

  • 具有n个结点的完全二叉树的深度为：⌊1og2n⌋+1\lfloor1og_2n\rfloor+1

  • 对一棵有n个结点的完全二叉树的所有结点按层次自上而下、自左至右进行编号，则对于任一结点i（1 ≤ i ≤ n）有:

    • 若 i = 1 ，则结点i是二叉树的根，无双亲：
    • 若 i > 1，则其双亲为： $\lfloor\frac i2\rfloor $
    • 若 2i > n ，则结点 i 没有左孩子，否则其左孩子为2i
    • 若 2i + 1 > n ，则结点i没有右孩子，否则其右孩子为 2i + 1

  • 完美二叉树是理想情况，可以充分发挥二叉树“分治”的优势。

  • 链表则是另一个极端，各项操作都变为线性操作，时间复杂度退化至O(n)O(n)。

  • 具有N个节点的二叉树有几种形态,计算公式:

    A[0]=1,A[1]=1\mathrm{A[0]}=1,\mathrm{A[1]}=1

    A[N]=∑M=0N−1(A[M]×A[N−M−1])\mathrm{A[N]=\sum_{M=0}^{N-1}(A[M]\times A[N-M-1])}

二叉树的最佳结构与最差结构

2.1.3 二叉树的遍历

二叉树常见的遍历方式

  • 层序遍历:按层次，从上到下，从左到右

    • 层序遍历本质上属于广度优先遍历，也称广度优先搜索
    • 时间复杂度为O(n)O(n) ：所有节点被访问一次，使用O(n)O(n) 时间，其中nn为节点数量。
    • 空间复杂度为O(n)O(n) ：在最差情况下，即满二叉树时，遍历到最底层之前，队列中最多同时存在 (n+1)/2(n+1)/2个节点，占用O(n)O(n)空间。

  • 前序遍历:根左右

  • 中序遍历:左根右

  • 后序遍历:左右根

    • 时间复杂度为 O(n)O(n) ：所有节点被访问一次，使用O(n)O(n) 时间。
    • **空间复杂度为 O(n)O(n) ** ：在最差情况下，即树退化为链表时，递归深度达到 nn ，系统占用 O(n)O(n) 栈帧空间。
2.1.4 二叉搜索树

二叉搜索树（binary search tree）满足以下条件。

  1. 对于根节点，左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值。
  2. 任意节点的左、右子树也是二叉搜索树，即同样满足条件 1. 。
  • 查找节点:二叉搜索树的查找操作与二分查找算法的工作原理一致，都是每轮排除一半情况。循环次数最多为二叉树的高度，当二叉树平衡时，使用⌊1og2n⌋\lfloor1og_2n\rfloor时间。
  • **插入节点:**与查找节点相同，插入节点使用⌊1og2n⌋\lfloor1og_2n\rfloor时间。
  • 删除节点:删除节点操作同样使用⌊1og2n⌋\lfloor1og_2n\rfloor时间，其中查找待删除节点需要⌊1og2n⌋\lfloor1og_2n\rfloor时间，获取中序遍历后继节点需要⌊1og2n⌋\lfloor1og_2n\rfloor时间。

二叉搜索树的效率

只有在高频添加、低频查找删除数据的场景下，数组比二叉搜索树的效率更高。

2.1.6 最优二叉树

最优二叉树又称为哈夫曼树，是一类带权路径长度最短的树

  • 路径：树中一个结点到另一个结点之间的通路
  • 结点的路径长度：路径上的分支数目
  • 树的路径长度：根节点到达每一个叶子节点之间的路径长度之和
  • 权：节点代表的值
  • 结点的带权路径长度：该结点到根结点之间的路径长度乘以该节点的权值
  • 树的带权路径长度（树的代价）：树的所有叶子节点的带权路径长度之和
  • 哈夫曼树的求法：给出一组权值，将其中两个最小的权值作为叶子节点，其和作为父节点，组成二叉树，而 后删除这两个叶子节点权值，并将父节点的值添加到该组权值中。重复进行上述步骤，直至所有权值都被使 用完。
    • 构造出的哈夫曼树中，所有初始给出的权值都作为了叶子节点，此时，求出每个叶子节点的带权路径长 度，而后相加，就是树的带权路径长度，这个长度是最小的
2.1.7 树和森林的遍历

由于树中每个节点可能有多个子树，因此遍历树的方法有两种：

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

树二叉树的转换

  • 规则是:树的最左边节点作为二叉树的左子树，树的其他兄弟节点作为二叉树的右子树节点
  • 示例如下图：采用连线法，将最左边节点和其兄弟节点都连接起来，而原来的父节点和兄弟节点的连线则断开

3.图

3.1 图的概念

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

  • 无向图：图的结点之间连接线是没有箭头的，不分方向
  • 有向图：图的结点之间连接线是箭头，区分A到B，和B到A是两条线
  • 完全图：
    • 无向完全图中，节点两两之间都有连线，n个结点的连线数为(n-1)+(n-2)+…+1=n (n-1)/2;
    • 有向完全图中，节点两两之间都有互通的两个箭头，n个节点的连线数为n (n-1)
  • 度、出度和入度：顶点的度是关联与该顶点的边的数目。
  • 在有向图中，顶点的度为出度和入度之和。
    • 出度是以该顶点为起点的有向边的数目。
    • 入度是以该顶点为终点的有向边的数目
  • 路径：存在一条通路，可以从一个顶点到达另一个顶点，有向图的路径也是有方向的
  • 连通图和连通分量：
    • 针对无向图。若从顶点v到顶点u之间是有路径的，则说明v和u之间是连通的
    • 若无向图 中任意两个顶点之间都是连通的，则称为连通图。
    • 无向图G的极大连通子图称为其连通分量
  • 强连通图和强连通分量：
    • 针对有向图。若有向图任意两个顶点间都互相存在路径即存在v到u，也存在u到v的路径，则称为强连通图。
    • 有向图中的极大连通子图称连通分量
  • 网：边带权值的图称为网

3.2 图的存储

  • 邻接矩阵：假设一个图中有n个节点，则使用n阶矩阵来存储这个图中各节点的关系，规则是若节点i到节点j 有连线，则矩阵Rij=1，否则为0。
  • 如果是一个无向图，肯定是沿对角线对称的，只需要存储上三角或 者下三角就可以了
  • 有向图则不一定对称
  • 使用邻接矩阵表示图时，我们可以直接访问矩阵元素以获取边，因此增删查改操作的效率很高，时间复杂度均为 O(1)O(1) 。然而，矩阵的空间复杂度为 O(n2)O(n^2) ，内存占用较多。

  • 邻接链表:用到了两个数据结构，先用一个一维数组将图中所有顶点存储起来。

  • 对此一维数组的每个顶点元素，使用链表挂上和其有连线关系的结点的编号和权值。

  • 邻接表仅存储实际存在的边，而边的总数通常远小于 n2n^2，因此它更加节省空间。然而，在邻接表中需要通过遍历链表来查找边，因此其时间效率不如邻接矩阵。

邻接表结构与哈希表中的“链式地址”非常相似，因此我们也可以采用类似的方法来优化效率。比如当链表较长时，可以将链表转化为 AVL 树或红黑树，从而将时间效率从 O(n)O(n) 优化至 O(log⁡n)O(\operatorname{log}n) ；还可以把链表转换为哈希表，从而将时间复杂度降至 O(1)O(1) 。

3.3 图的遍历

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

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

    image-20240920084204784

3.4 图的拓扑

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

  • AOV网用来表示大的工程项目执行计划，因此不能出现有向环，若存在，则意味着某项活动必须以自身任务的完成为先决条件

  • 因此若要检测一个工程是否可行，首先应检查对应的AOV网是否存在回路。检测的 方法是对有向图构造其顶点的拓扑有序序列

  • 构造方法：将有向图的有向边作为活动开始的顺序若图中一个节点入度为0，则应该最先执行此活动，

  • 而后删除掉此节点和其关联的有向边，再去找图中其他没有入度的结点，执行活动，依次进行

  • 示例如下：

    image-20240920090225388

3.4 图的最小生成树

  • 假设有n个节点，那么这个图的最小生成树有 n-1 条边（不会形成环路，是树非图)，这n-1条边会将所有顶 点都连接成一个树，并且这些边的权值之和最小，因此称为最小生成树
    • 普里姆算法：从任意顶点出发，找出与其邻接的边权值最小的，此时此边的另外一个顶点自动加入树集合中，而后再从这这个树集合的所有顶点中找出与其邻接的边权值最小的，同样此边的另外一个顶点加 入树集合中，依次递归，直至图中所有顶点都加入树集合中，此时此树就是该图的最小生成树
    • 克鲁斯卡尔算法（推荐）：这个算法是从边出发的，因为本质是选取权值最小的n-1条边，因此，就将边 按权值大小排序，依次选取权值最小的边，直至囊括所有节点，要注意，每次选边后要检查不能形成环路

image-20240920091720410