Chapter 3: 基础数据结构

本章来介绍一些基础的数据结构。

抽象数据类型与数据结构

抽象数据类型 (Abstract Data Type, ADT) 与 数据结构 (Data Structure) 本质上是两码事。抽象数据类型的角度较为宏观，例如“存在一个栈，允许我往里压入元素，弹出元素”。而数据结构关心的是更深层次的问题，例如“我要使用一个数组来构建这样一个栈”。

你知道如何去开车，但是你不需要去担心发动机盖下面的引擎是怎样运作的，

数组与链表

几乎所有的数据类型都构建在这两个数据类型之上。

数组 (Array) 是一个简单的数据结构。它往往使用内存上的连续位置来存储数据。

数组的优点在于随机访问。你可以直接在$O(1)$的时间复杂度内跳转到数组的任意元素。
当你想要在中间位置插入/删除元素时，这个数据类型就不是很高效了。时间复杂度为$O(N)$，因为就如我们刚才所说，数组使用内存上的连续位置来存储数据，所以一旦你在中间做出了改动，你需要移动它后面的所有元素来腾出位置，或者补齐因删除元素空出来的位置。

链表 (Linked List) 相比之下是一个更灵活的数据结构，在实现原理上更加灵活。链表不需要使用连续的内存位置来存储数据，相反，链表使用串联在一起的节点来存储数据。每个节点存储指向下一个节点的指针 (如果是双链表的话还会包含一个前指针)，将分布在内存各个地方的节点串起来。

链表的优势在于增删操作。想要在某个位置添加或者删除元素，你只需要在那个位置重新连接节点就可以了。假设我们已经有指向该元素位置的指针，那么增加元素，删除元素的时间复杂度为$O(1)$。
缺点在于不够灵活。如果我们想要这个链表中的第5000个数据，那么你只能需要从第一个元素开始，向后遍历，直到你找到了你需要的数据。时间复杂度为$O(n)$。

    ⚠注意

在链表中如果想要对链表头节点进行改动，包括在前面插入/删除头节点会很麻烦，因为你需要去更新一个叫做Head的全局变量。在编写程序时就代表你需要用一个if语句来处理这个现象。

一个优雅的解决方案是在链表的最开始插入一个虚拟节点。这个虚拟节点不存储任何数据，只有一个指向后方节点的指针。这样，链表的真正意义上的第一个元素就一定是这个虚拟节点的后面一个节点。这样你也不需要去对链表的Head作出改动了。

栈与队列

栈和队列建立在数组与链表之上，但是相比数组和列表，它们有更严格的增删改查规定。

栈 (Stack) 是一个后入先出 (Last In First Out, LIFO) 的数据结构。想要向栈内存入元素，则必须将元素压入栈顶。随着元素越来越多，最早进入栈的元素会被后来的元素埋得更深。

同样的，元素只能在栈的顶部被取出。如果想要拿取较早压入栈的元素，你就必须要把晚点压入栈的元素倒出来，才能够访问到这个元素。

栈可以很轻松的使用链表或数组实现，链表的压入和弹出操作时间复杂度均为$O(1)$。

队列 (Queue) 的规则与栈刚好相反。队列是一个先入先出 (First In First Out, FIFO) 的数据结构。就好比你插入复印机的纸盘：先进入打印机的大白纸会先从输出口出来。

队列同样只有存入和取出两个操作。不同的是，队列只能在它的一端存入数据，并在另一端取出数据。

队列的存取时间复杂度同样是$O(1)$。

    ⚠注意

如果想要使用数组来实现一个队列，那么队列的头尾会随着存取操作在数组里不停移动。我们使用两个指针来追踪队列的头尾。如果某一个指针来到了数组的尽头，但是我们还需要继续增加元素该怎么办？

我们使用循环数组来正确实现队列的效果。在这种情况下，头指针应该跳转到数组的另一头，并尝试将那里的空位置声明为新的头指针位置。

你可以通过这个公式来算出新指针的位置：

$$\text{NewPosition} = (\text{CurrentPosition} + 1) \text{ mod } \text{MaxCapacity}$$

图

图是一个由线 (Edges) 和顶点 (Vertices) 组成的数据结构。
图可以是有向的，也可以是无向的，区别在于连接节点的线是单向还是双向。同时，线上面有没有权重也能决定是不是权重图。

我们可以使用邻接矩阵 (Adjacency Matrix) 来表示一个图。邻接矩阵是一个大小为$V \times V$的表格。假如说节点1与节点2互相连接，那么我们就可以Grid[1][2]处设值为1。这表示两个节点互相连接。

使用邻接矩阵的好处是，查询两个节点是否存在连接的时间复杂度为$O(1)$。你只需要找到坐标，并看看值是1还是0就可以了。

坏处当然也非常明显，它的存储复杂度是$O(V^2)$。假设一个社交平台有1000000个用户，每个用户仅有50个好友，那么这个表格中有99.99%的单元格是空白的。

你也可以选择使用邻接链表 (Adjacency Lists) 来存储图。邻接链表顾名思义，使用链表来存储节点的连接情况。一般来讲我们使用数组来存储图中所有的节点对应的链表，然后在数组的每一个位置存入链表的Head。每一个这样的链表上面挂着连接到该节点的节点。例如，List[1]存储了连接第一个节点的所有节点，例如[2, 5, 9]。

这样做的好处是存储需求大大降低，仅需$O(V + E)$，非常适合比较离散的图的存储。
坏处就是检查两个节点是否存在连接相对复杂。例如查找A与B是否存在连接，你需要遍历A的链表来查找里面是否有B。时间复杂度就是$O(k)$，$k$代表图里连接节点数量最多的那个分支。

• 使用邻接矩阵：

尺寸为$V^2 \text{ bits}$，或$\text{ints}$。由此可得$10000 \times 10000 = 100000000 \text{ entries}$

即使我们使用bits来存储，那也要占用约$12.5 \text{MB}$的空间。

• 使用邻接链表：

共有10000个节点，因此存储链表头的数组共有10000个元素。大小为：

$$10000 \times 4 \text{ bytes } = 40 \text{ KB}$$

平均每个节点都有50个连接节点，由此可得平均每个链表的长度为50。按照这个来计算就一共有这么多链表节点：

$$10000 \times 50 = 500000 \text{ nodes}$$

按照单链表来计算，每个节点由key和指向下一个节点的指针构成，则每个链表节点的大小为4 + 4 = 8 bytes。

最后计算可得：

$$\text{Total Size } = 500000 \times 8 \text{ bytes } = 4 \text{ MB}$$

算下来还是你更省啊！

广度优先搜索

广度优先搜索 (Breadth-First Search, BFS) 通过一层层探索来在图中找到目标节点，或者就做一个单纯的遍历。

就好比向一个水塘里丢进去了一个小石块。波纹首先会到达近处，随后才能抵达远处。换到BFS中意味着，波纹先抵达该节点的周围节点，然后是这些节点的周围节点，以此类推。

广度优先搜索使用队列来跟踪搜索进程。BFS的步骤基本上是：

1. 将起始搜索节点放入队列
2. 当队列不为空时：
   • 从队列中移除$u$
   • 前往$u$节点
   • 找到$u$节点紧邻的所有节点。如果这些节点没有被找到过，就加入队列。

我们为什么使用队列来追踪BFS？因为队列是一个先入先出的数据结构，这要求程序只能在完成遍历离起始节点相近的节点之后，再继续往更深层探索。

如果图使用邻接数组来实现，则完成广度优先搜索的时间复杂度为$O(V + E)$。因为在访问V个节点过后，你还需要走过E条边。

如果是邻接矩阵，则时间复杂度为$O(V^2)$。这是因为除了访问V个节点，你还需要为每个节点去寻找可能的直接连接节点。由于邻接数组可以直接找到哪些节点与当前节点直接相连，因此这一步是邻接矩阵特有的。

深度优先搜索

深度优先搜索 (Depth-First Search, DFS) 与 BFS 形成鲜明对比。如果说 BFS 是"一层层推进"，那么 DFS 就是"一条路走到黑"。

想象你在探索一个迷宫。DFS 的策略是：选择一条路，一直往前走，直到走到死胡同走不通了，我们回退 (Backtrack) 到上一个岔路口，尝试另一条路。

DFS 使用栈 (Stack) 来跟踪搜索进程（或者直接使用递归，因为递归本身就是利用调用栈）。步骤如下：

1. 将起始节点压入栈
2. 当栈不为空时：
   • 从栈顶弹出节点 $u$
   • 如果 $u$ 未被访问过，标记为已访问
   • 将 $u$ 的所有未访问邻居压入栈

DFS 的时间复杂度与 BFS 相同：

• 邻接链表：$O(V + E)$
• 邻接矩阵：$O(V^2)$

BFS vs DFS：什么时候用哪个？

Dijkstra 最短路径算法

前面我们说 BFS 可以在无权图中找到最短路径。但如果图的边有不同的权重（比如道路的距离、通行的费用），BFS 就不够用了。这时候我们需要 Dijkstra 算法。

Dijkstra 算法使用贪心策略：

1. 维护一个"距离表"，记录从起点到每个节点的当前已知最短距离
2. 每次从未处理的节点中，选择距离最小的那个节点 $u$
3. 用 $u$ 来松弛 (Relax) 它的所有邻居：如果经过 $u$ 到达邻居 $v$ 的距离比之前记录的更短，就更新它
4. 重复直到所有节点都处理完毕

松弛操作是关键：
$$\text{if } dist[u] + weight(u, v) < dist[v] \text{ then } dist[v] = dist[u] + weight(u, v)$$

因为我们每次都选择当前距离最小的未处理节点。由于边权重都是非负的，一旦某个节点被处理，它的最短距离就确定了，不会再被更新。这就是为什么Dijkstra是一个有效的算法。

注意：Dijkstra 不能处理负权边！如果有负权边，需要使用 Bellman-Ford 算法。好在这个课程中我们没有涉及（

时间复杂度

• 简单实现（数组）：$O(V^2)$
• 优先队列（最小堆）：$O((V + E) \log V)$

Dijkstra 伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

function Dijkstra(Graph, source):
    dist[source] ← 0
    for each vertex v in Graph:
        if v ≠ source:
            dist[v] ← INFINITY
        prev[v] ← UNDEFINED
        add v to Q (unprocessed set)
    
    while Q is not empty:
        u ← vertex in Q with min dist[u]
        remove u from Q
        
        for each neighbor v of u still in Q:
            alt ← dist[u] + weight(u, v)
            if alt < dist[v]:       // 松弛操作
                dist[v] ← alt
                prev[v] ← u
    
    return dist[], prev[]

数据结构复杂度速查

干货速记！