数据结构与算法基础知识

数据结构就是计算机存储、组织数据的方式。就像生活中我们会用衣柜整理衣服、用书架摆放书籍一样，数据结构决定了数据如何存放和访问。

1. 数组（Array）

是什么：最简单、最常用的数据结构，就像一排并排的储物柜，每个格子有编号（下标），可以存放东西。所有格子类型相同，在内存中连续排列。

示意图：

下标:   0    1    2    3    4
      +----+----+----+----+----+
数据： | 10 | 20 | 30 | 40 | 50 |
      +----+----+----+----+----+

特点：

• 通过下标访问非常快（O(1)），比如 arr[3] 直接拿到 40。
• 插入和删除较慢（O(n)），因为要移动后面的元素。

生活例子：电影院的一排座位，每个座位都有号码，你可以快速找到座位，但如果要在中间插入一个人，后面所有人都要挪位置。

2. 链表（Linked List）

是什么：像一列火车，每节车厢（节点）装着货物（数据），并且挂着一根链条指向下一节车厢。节点在内存中可以不连续。

单向链表示意图：

head
 ↓
+-----+    +-----+    +-----+    +-----+
| 10  |--->| 20  |--->| 30  |--->| 40  |---> null
+-----+    +-----+    +-----+    +-----+

双向链表示意图：

null <--+-----+    +-----+    +-----+    +-----+ --> null
        | 10  |<-->| 20  |<-->| 30  |<-->| 40  |
        +-----+    +-----+    +-----+    +-----+

循环链表示意图（最后一个节点指向第一个）：

    +-----+    +-----+    +-----+
    | 10  |--->| 20  |--->| 30  |---
    +-----+    +-----+    +-----+  |
      ^                           |
      |                           |
      +---------------------------+

特点：

• 插入和删除很快（O(1)），只需改变链条指向。
• 查找较慢（O(n)），因为需要从头顺着链条找。

生活例子：寻宝游戏，每张纸条告诉你下一个线索的位置。要找到第10个线索，必须从第1个开始依次找到第10个。

3. 栈（Stack）

是什么：一种“后进先出”的结构，像一摞盘子，你只能从最上面拿盘子，新盘子也放在最上面。

示意图：

    push(30) →     +-----+
                   | 30  |  ← top
                   +-----+
    push(20) →     | 20  |
                   +-----+
    push(10) →     | 10  |
                   +-----+

弹出（pop）时，从顶部取出。

特点：

• 只能从一端（栈顶）操作：添加（push）、移除（pop）、查看栈顶（peek）。
• 常用场景：函数调用、括号匹配、撤销操作。

生活例子：浏览器的后退按钮，你访问的页面依次压入栈，后退就是弹出栈顶。

4. 队列（Queue）

是什么：一种“先进先出”的结构，像排队买东西，先来的人先得到服务。

示意图：

   enqueue(10)  enqueue(20)  enqueue(30)
        ↓            ↓            ↓
   +-----+      +-----+      +-----+
   | 10  |  →  | 20  |  →  | 30  |
   +-----+      +-----+      +-----+
      ↑                          ↑
    front                      rear
   dequeue() → 取出 10

特点：

• 从队尾添加（enqueue），从队首移除（dequeue）。
• 常用场景：任务调度、打印机队列、广度优先搜索。

生活例子：奶茶店排队，先来的人先点单。

特殊队列：

• 双端队列（Deque）：两端都可以插入和删除。
• 优先队列（Priority Queue）：元素有优先级，优先级高的先出队（通常用堆实现）。

5. 哈希表（Hash Table）——也叫散列表

是什么：一种根据关键码直接访问数据的数据结构。它通过一个哈希函数将键映射到表中的位置。简单说，你给一个名字，它能立刻找到对应的东西。

示意图（链地址法解决冲突）：

键: "apple"  → 哈希函数 → 索引 2
键: "banana" → 哈希函数 → 索引 5
键: "cherry" → 哈希函数 → 索引 2（冲突）

哈希表数组：
索引:  0      1       2       3       4       5
      +---+  +---+  +-----+  +---+  +---+  +-----+
      |   |  |   |  |  *  |  |   |  |   |  |  *  |
      +---+  +---+  +-|---+  +---+  +---+  +-|---+
                      ↓                      ↓
                  +-----+                +-----+
                  |apple|                |banana|
                  +-----+                +-----+
                      ↓
                  +-----+
                  |cherry|
                  +-----+

特点：

• 查找、插入、删除平均时间复杂度 O(1)。
• 需要解决哈希冲突（不同键映射到同一位置），常用链地址法或开放地址法。

生活例子：字典的目录，你想查“苹果”这个字，通过拼音索引直接翻到那一页。哈希函数就是拼音索引。

在编程中的形式：

• 哈希集合（HashSet）：只存键，没有值，用于快速判断元素是否存在。
• 哈希映射（HashMap）：存储键值对，如字典。

6. 树（Tree）

是什么：一种分层的数据结构，像一棵倒长的树，有一个根节点，下面有很多子节点。每个节点可以有多个子节点，但只有一个父节点（根节点除外）。

示意图（通用树）：

        根节点
        (CEO)
       /  |  \
      /   |   \
  经理A  经理B  经理C
   / \         / \
员工 员工    员工 员工

基本术语：

• 根节点：最顶层的节点。
• 叶子节点：没有子节点的节点。
• 父节点、子节点、兄弟节点：顾名思义。
• 深度、高度：深度是从根往下数，高度是从叶子往上数。

生活例子：公司的组织架构，CEO下面是各部门经理，经理下面是员工。

常见类型：

二叉树（Binary Tree）

每个节点最多有两个子节点（左孩子、右孩子）。

      1
     / \
    2   3
   / \   \
  4   5   6

二叉搜索树（BST）

左子树所有值 < 根节点值 < 右子树所有值，查找很快。中序遍历会得到升序序列。

      5
     / \
    3   8
   / \   \
  2   4   9

平衡二叉树（AVL/红黑树）

左右子树高度差不超过1，防止树退化成链表，保证查找效率。

      4
     / \
    2   6
   / \ / \
  1  3 5  7

堆（Heap）

一种特殊的完全二叉树，用于实现优先队列。最大堆：父节点 >= 子节点；最小堆：父节点 <= 子节点。 最大堆示意图：

       90
      /  \
    80    70
   /  \  /  \
  60  50 40  30

字典树（Trie）

用于字符串快速检索，每个节点代表一个字符，从根到节点的路径组成单词的前缀。

        root
       / |  \
      c  a   b
     /   |   \
    a    t    o
   /     |     \
  t      e      y
（存储 cat, ate, boy）

树的遍历（Traversal）

树的遍历是指按一定顺序访问树的所有节点，主要有四种方式：

1. 前序遍历（Preorder Traversal）：根 → 左子树 → 右子树
顺序：1 → 2 → 4 → 5 → 3 → 6

      1
     / \
    2   3
   / \   \
  4   5   6

2. 中序遍历（Inorder Traversal）：左子树 → 根 → 右子树
顺序：4 → 2 → 5 → 1 → 3 → 6

3. 后序遍历（Postorder Traversal）：左子树 → 右子树 → 根
顺序：4 → 5 → 2 → 6 → 3 → 1

4. 层序遍历（Level Order Traversal）：按层次从上到下，从左到右（BFS）
顺序：1 → 2 → 3 → 4 → 5 → 6

---

7. 图（Graph）

是什么：由节点（顶点）和连接节点的边组成的网络。比树更复杂，可以有环路。

示意图：

• 无向图（边无方向）：

    A --- B
    |     |
    C --- D

• 有向图（边有方向）：

    A --> B
    ^     |
    |     v
    C <-- D

• 加权图（边上带权重）：

    A --5-- B
    |       |
    2       3
    |       |
    C --1-- D

分类：

• 有向图：边有方向，如关注关系（A关注B，B不一定关注A）。
• 无向图：边无方向，如朋友关系（互相为好友）。
• 加权图：边上有权重，如距离、时间。
• 连通图：任意两点都有路径相连。

生活例子：地铁线路图（站点是节点，轨道是边），社交网络（人是节点，好友关系是边）。

图的遍历：

• 深度优先搜索（DFS）：类似树的先序遍历，沿着一条路径走到头，再回溯。常用递归或栈实现。 示意图：从 A 出发 DFS：A → B → D → C
• 广度优先搜索（BFS）：类似树的层序遍历，按层次访问。常用队列实现。 示意图：从 A 出发 BFS：A → B → C → D

1. 递归（Recursion）

是什么：函数调用自身，把一个大问题分解成更小的相同问题，直到问题简单到可以直接解决（递归基）。

图示（计算阶乘 3!）：

factorial(3)
   = 3 * factorial(2)
         = 2 * factorial(1)
               = 1 * factorial(0)
                     = 1
               ← 1
         ← 2 * 1 = 2
   ← 3 * 2 = 6

生活例子：俄罗斯套娃，打开一个娃娃，里面还有一个同样的小娃娃，直到最后一个不能再拆开。

核心：

• 要有递归基（终止条件），否则会无限循环。
• 例如求阶乘：n! = n * (n-1)!，且 0! = 1。

2. 回溯（Backtracking）

是什么：一种通过尝试所有可能并“撤销”错误选择的算法，常用于解决组合问题（如排列、子集、八皇后）。可以看作是递归的一种形式，在尝试失败时回到上一步换条路走。

示意图（走迷宫）：

入口 → [路] → [岔路A] → [死胡同]  ← 回溯
        ↓
      [岔路B] → [出口]

生活例子：走迷宫，走到死胡同就退回上一个路口换方向。

模板：做选择 → 递归 → 撤销选择。

3. 分治（Divide and Conquer）

是什么：把一个大问题分成多个小问题，分别解决，最后合并结果。典型应用：归并排序、快速排序。

示意图（归并排序）：

[38,27,43,3,9,82,10]
         /           \
[38,27,43,3]    [9,82,10]
   /     \         /    \
[38,27] [43,3]  [9,82] [10]
  / \     / \     / \     |
[38][27] [43][3] [9][82] [10]
  \ /     \ /     \ /     |
[27,38] [3,43]  [9,82] [10]
   \     /         \     /
 [3,27,38,43]    [9,10,82]
       \             /
    [3,9,10,27,38,43,82]

生活例子：打扫一个大房间，先分成几个区域分别打扫，最后整体检查一遍。

步骤：分解 → 解决 → 合并。

4. 动态规划（Dynamic Programming，DP）

是什么：一种用空间换时间的技巧，把大问题拆成重叠的子问题，并记住子问题的答案，避免重复计算。通常用于求最值、计数等问题。

示意图（斐波那契数列）： 传统递归会重复计算：

fib(5)
    ├── fib(4)
    │   ├── fib(3)
    │   │   ├── fib(2)
    │   │   └── fib(1)
    │   └── fib(2)
    └── fib(3)
        ├── fib(2)
        └── fib(1)

DP 用数组存储中间结果，避免重复计算：

dp[0]=0, dp[1]=1
dp[2]=1, dp[3]=2, dp[4]=3, dp[5]=5

生活例子：爬楼梯，你要爬到第10层，可以一步走1层或2层。爬到第i层的方法数 = 爬到第i-1层的方法数 + 爬到第i-2层的方法数。你只需要记住之前算过的结果，不用每次都重新算。

关键：

• 最优子结构：子问题的最优解能推导出原问题的最优解。
• 重叠子问题：子问题被反复计算，可以用数组记录。

5. 贪心（Greedy）

是什么：每一步都选择当前看起来最优的选择，希望通过局部最优达到全局最优。贪心不一定能得到最优解，但适用于某些特定问题（如最小生成树、最短路径的Dijkstra算法）。

示意图（找零钱：用最少硬币凑出11元，有1、2、5元）： 贪心策略：先选最大面额

目标 11
取 5 → 剩余 6
取 5 → 剩余 1
取 1 → 完成，用了 3 枚硬币

生活例子：换零钱时，尽量用大面额硬币，这就是贪心策略（但某些面额组合下不一定最优）。

6. 二分查找（Binary Search）

是什么：在有序数组中查找目标值，每次将搜索区间缩小一半，时间复杂度 O(log n)。

示意图： 在有序数组 [2,5,8,12,16,23,38,56] 中找 23。

初始区间 [0,7] 中间下标 3 值 12 < 23 → 区间 [4,7]
区间 [4,7] 中间下标 5 值 23 = 23 → 找到！

生活例子：猜数字游戏，告诉你是大了还是小了，每次猜中间数，很快就能猜到。

前提：数组必须有序。

7. 双指针（Two Pointers）

是什么：使用两个指针（下标）在数组或链表上协同移动，解决特定问题。常用技巧：

• 快慢指针：一个快一个慢，用于找中点、环检测。
• 左右指针：从两端向中间移动，用于两数之和、回文判断。

示意图（左右指针找两数之和）： 有序数组 [2,7,11,15]，target=9

左指针 L=0, 右指针 R=3
L+R=2+15=17 >9 → R-- → R=2
L+R=2+11=13 >9 → R-- → R=1
L+R=2+7=9 → 找到 [2,7]

生活例子：两个人一起找东西，一个从前往后找，一个从后往前找，碰头时就找到了。

8. 滑动窗口（Sliding Window）

是什么：维护一个窗口（连续区间），随着遍历移动窗口，动态更新窗口内的信息，常用于解决子数组/子串问题。

示意图（找无重复字符的最长子串）： 字符串 "abcabcbb"

窗口 [a] → [ab] → [abc] → (遇到 a 重复) 窗口左移 → [bca] → [cab] → ...

生活例子：用放大镜看地图，放大镜框住一个区域，然后移动放大镜，每次只关心框内的内容。

常见场景：最大/最小连续子数组、无重复字符的最长子串。

9. 位运算（Bit Manipulation）

是什么：直接操作整数的二进制位，速度快。常见运算：

• 与（&）：两位都为1才为1。
• 或（|）：有一位为1即为1。
• 异或（^）：两位不同为1，相同为0（特性：a ^ a = 0，a ^ 0 = a）。
• 左移（<<）、右移（>>）。

示意图：

  5 = 0101
  3 = 0011
5 & 3 = 0001 = 1
5 | 3 = 0111 = 7
5 ^ 3 = 0110 = 6

用途：判断奇偶、交换两数、消除二进制中的1（n & (n-1)）、状态压缩等。

10. 排序（Sorting）

是什么：把一组数据按某种顺序排列。常见排序算法：

冒泡排序：相邻比较交换，大的元素逐渐“冒泡”到末尾。

初始： [5,3,8,4]
第一轮：3,5,4,8
第二轮：3,4,5,8
第三轮：3,4,5,8

插入排序：像打牌，每次把新牌插入已排序的手牌。

初始： [5,3,8,4]
将3插入到5前：[3,5,8,4]
将8不动：[3,5,8,4]
将4插入到5前：[3,4,5,8]

归并排序：分治，先分后合（见前面分治图）。

快速排序：选基准，分区，递归。

[3,8,2,5,1,4] 选基准 3
分区后小于3：[2,1]，大于3：[8,5,4]
递归处理左右...

堆排序：构建最大堆，反复交换堆顶和末尾，再调整堆。

11. 拓扑排序（Topological Sort）

是什么：对有向无环图（DAG）的顶点进行排序，使得对于每条有向边 u→v，u 都在 v 前面。常用于任务调度、课程安排。

示意图： 课程依赖关系：C1 → C2, C1 → C3, C2 → C4, C3 → C4

C1
 / \
v   v
C2  C3
 \   /
  v v
  C4

拓扑排序结果之一：C1, C2, C3, C4（C1, C3, C2, C4 也可）

算法：Kahn 算法（基于入度）或 DFS 后序。

12. 最短路径算法（Shortest Path）

是什么：找图中两点之间的最短路径（按权重）。

Dijkstra 算法（适用于非负权图）： 从起点出发，不断选择距离最小的未处理节点，更新其邻居距离。

起点 A，到 B、C、D 的距离初始为无穷，A 到 B=5，A 到 C=2
先选 C（距离2），从 C 更新 D 距离为 2+3=5
再选 B（距离5），从 B 更新 D 距离为 5+1=6（不更新，因为 5 < 6）
最终 A→C→D 距离 5

Bellman-Ford：可处理负权，通过松弛所有边 V-1 次。

Floyd-Warshall：多源最短路径，动态规划思想。

13. 最小生成树（Minimum Spanning Tree）

是什么：在连通加权图中，找一棵树连接所有节点，且总权值最小。

Kruskal 算法（按边权排序，用并查集判断环）：

边集：(A-B:5), (A-C:2), (B-C:1), (B-D:4), (C-D:3)
排序后：B-C:1, A-C:2, C-D:3, B-D:4, A-B:5
依次选边：选 B-C(1)，选 A-C(2)，选 C-D(3)（不形成环），选 B-D(4) 会形成环（B-C-D-B），跳过，选 A-B(5) 也会环，跳过。最终得到 MST 权值 1+2+3=6。

Prim 算法：类似 Dijkstra，每次找最小边连接新节点。

生活例子：给几个城市铺设光纤，要连接所有城市且总造价最低。

14. 并查集（Union-Find）

是什么：一种树型数据结构，用于处理不相交集合的合并与查询。支持两个操作：find（找元素所属集合的代表）、union（合并两个集合）。

示意图： 初始每个元素自成一棵树：

0    1    2    3    4
union(0,2) → 0 成为 2 的父节点
0        1        3    4
 \
  2
union(2,4) → 找到 0，将 4 的父设为 0
    0
   / \
  2   4

生活例子：朋友圈，判断两个人是否属于同一个圈子，或者合并两个圈子。

15. 字典树（Trie）

是什么：一种多叉树，用于高效存储和查找字符串集合。每个节点代表一个字符，从根到节点的路径组成一个单词的前缀。常用于自动补全、拼写检查。

示意图： 插入 "cat", "car", "dog" 后的 Trie：

        root
       /    \
      c      d
     /        \
    a          o
   /  \         \
  t    r         g
 (cat)(car)     (dog)

节点中常标记是否为单词结尾（例如 t、r、g 节点标记为 isEnd=true）。

常见术语对照（中文 ↔ 英文）

• 数组 → Array
• 链表 → Linked List
• 栈 → Stack
• 队列 → Queue
• 双端队列 → Deque
• 优先队列 → Priority Queue
• 哈希表/散列表 → Hash Table
• 哈希集合 → HashSet
• 哈希映射 → HashMap
• 树 → Tree
• 二叉树 → Binary Tree
• 二叉搜索树 → Binary Search Tree (BST)
• 堆 → Heap
• 图 → Graph
• 递归 → Recursion
• 回溯 → Backtracking
• 分治 → Divide and Conquer
• 动态规划 → Dynamic Programming (DP)
• 贪心 → Greedy
• 二分查找 → Binary Search
• 双指针 → Two Pointers
• 滑动窗口 → Sliding Window
• 位运算 → Bit Manipulation
• 排序 → Sorting
• 拓扑排序 → Topological Sort
• 最短路径 → Shortest Path
• 最小生成树 → Minimum Spanning Tree (MST)
• 并查集 → Union-Find / Disjoint Set Union (DSU)
• 字典树 → Trie / Prefix Tree