数据结构从零到一

21 章完整教程 · 从数组到图论 · 从零基础到面试通关

零基础友好 · 每个概念都讲透 · 配有生活类比 · 全程 Python 代码 · 涵盖排序/查找/DP/贪心/回溯 · 含高级数据结构 · 面试题实战

第一章:开篇——为什么要学数据结构?

1.1 什么是数据结构?

一句话:数据结构就是数据的"摆放方式"。同样的数据,摆放方式不同,操作效率天差地别。

类比:数据结构 = 收纳方式

想象你有一堆衣服要收纳:

• 随手扔进衣柜 → 找某件衣服要翻半天(无结构)
• 按季节叠好分层放 → 很快就能找到(有序结构)
• 按颜色挂起来 → 一目了然(索引结构)

数据结构就是决定"数据怎么放",从而决定"查找/插入/删除有多快"。

1.2 数据结构 vs 算法

数据结构是"数据怎么存",算法是"数据怎么算"。两者密不可分:

数据结构 + 算法 = 程序 举例:在通讯录中查找一个人 数据结构选择:数组 → 需要逐个遍历(慢) 数据结构选择:哈希表 → 直接定位(快) 同样的"查找"算法,数据结构不同,效率完全不同!
对比数据结构算法
关注点数据怎么存、怎么组织数据怎么处理、怎么算
类比仓库的货架布局取货/发货的流程
例子数组、链表、树、图排序、搜索、动态规划

1.3 学了能干嘛?

1
面试敲门砖——大厂面试几乎必考数据结构与算法。LeetCode 上 2000+ 题目,核心就是数据结构。
2
写出高效程序——选对数据结构,程序速度可能差 1000 倍。数据库索引用 B+ 树、缓存用哈希表、任务调度用堆……
3
理解底层原理——Python 的 list 底层是动态数组、dict 底层是哈希表。懂了数据结构,你就懂了它们为什么快。
4
培养算法思维——遇到问题时能想到"该用什么结构来组织数据",这是程序员的核心能力。

1.4 学习路线图

第1-2章
基础概念什么是数据结构 + 时间复杂度(约 2 小时)
第3-6章
线性结构数组、链表、栈、队列(约 4 小时)
第7章
哈希表哈希函数、冲突处理(约 2 小时)
第8-11章
树与堆二叉树、BST、平衡树、堆(约 5 小时)
第12-13章
图论图的表示、DFS、BFS、最短路径(约 4 小时)
第14-18章
经典算法排序、查找、分治、贪心、回溯(约 5 小时)
第19-21章
进阶与实战动态规划、高级数据结构、面试题(约 6 小时)
预计总时长:25-30 小时 每天学 2 小时,大约 2 周可以完成。每个数据结构都配有 Python 代码,建议自己敲一遍运行。

1.5 本章小结

本章要点回顾 • 数据结构 = 数据的组织方式,决定操作效率
• 数据结构 + 算法 = 程序
• 学数据结构 = 面试通关 + 写出高效代码 + 理解底层原理
• 本教程用 Python 讲解,零基础友好

第二章:前置知识——时间复杂度与大O

2.1 为什么需要时间复杂度?

同一段逻辑,用不同写法,运行时间可能差几万倍。我们需要一种方式来衡量算法的快慢,而不依赖于具体的电脑。

类比:时间复杂度 = 考试评分标准

判断一个算法好不好,不能靠"感觉快不快",得有一个标准。时间复杂度就是这个标准——它告诉你:当数据量变大时,运行时间会怎样变化?

2.2 大 O 表示法

常见时间复杂度(从快到慢): O(1) 常数时间 —— 不管数据多大,时间都一样 O(log n) 对数时间 —— 数据翻倍,时间只多一步 O(n) 线性时间 —— 数据翻倍,时间翻倍 O(n log n) 线性对数 —— 比线性稍慢一点 O(n^2) 平方时间 —— 数据翻倍,时间变 4 倍 O(2^n) 指数时间 —— 数据每多 1,时间翻倍 O(n!) 阶乘时间 —— 恐怖的增长速度
大 O 的直觉理解

假设 n = 1000:

• O(1) = 1 次操作
• O(log n) ≈ 10 次操作
• O(n) = 1000 次操作
• O(n log n) ≈ 10000 次操作
• O(n^2) = 1,000,000 次操作

差距一目了然!这就是为什么选对算法那么重要。

2.3 常见复杂度分析

O(1) —— 常数时间
# 无论列表多长,取第一个元素都是 O(1)
lst = [3, 1, 4, 1, 5, 9, 2, 6]
first = lst[0]  # O(1)

# 字典查找也是 O(1)
d = {"name": "Alice", "age": 25}
print(d["name"])  # O(1)
O(n) —— 线性时间
# 遍历列表 O(n)
lst = [3, 1, 4, 1, 5, 9, 2, 6]
total = 0
for x in lst:      # O(n)
    total += x
O(n^2) —— 平方时间
# 双重循环 O(n^2)
lst = [3, 1, 4, 1, 5, 9, 2, 6]
n = len(lst)
for i in range(n):
    for j in range(n):    # n * n = n^2
        pass
O(log n) —— 对数时间
# 二分查找:每次排除一半数据
def binary_search(lst, target):
    left, right = 0, len(lst) - 1
    while left <= right:
        mid = (left + right) // 2
        if lst[mid] == target:
            return mid
        elif lst[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# 1000 个数据最多查 10 次 (log2(1000) ≈ 10)
# 1000000 个数据最多查 20 次

2.4 空间复杂度

空间复杂度含义例子
O(1)只用固定几个变量交换两个变量
O(n)需要一个和输入等大的数组复制一个列表
O(log n)递归调用栈的深度二分查找的递归版
三种情况 • 最好情况:运气最好的时候
• 最坏情况:运气最差的时候——我们通常关注这个
• 平均情况:期望的平均表现

2.5 本章小结

本章要点回顾 • 时间复杂度用大 O 表示法,描述算法随数据量增长的趋势
• 常见复杂度:O(1) < O(log n) < O(n) < O(n log n) < O(n^2)
• 空间复杂度衡量额外内存使用
• 通常关注最坏情况的时间复杂度

第三章:数组——最基础的数据结构

3.1 什么是数组?

数组是一段连续的内存空间,里面存放相同类型的数据。

类比:数组 = 电影院的一排座位

电影院一排有 10 个座位,编号 0 到 9:

• 每个座位放一个人(元素)
• 座位是连续的(内存连续)
• 你知道编号就能直接找到对应座位(随机访问 O(1))
• 中间插入一个人?后面所有人都要往后挪(插入 O(n))

数组的内存布局: 地址: 1000 1004 1008 1012 1016 +-----+-----+-----+-----+-----+ | 3 | 1 | 4 | 1 | 5 | +-----+-----+-----+-----+-----+ 下标: 0 1 2 3 4 访问 arr[3]:地址 = 1000 + 3 * 4 = 1012 → O(1)

3.2 数组的基本操作与复杂度

操作时间复杂度说明
访问(按索引)O(1)直接计算地址
查找(按值)O(n)最坏遍历整个数组
尾部插入O(1)*直接放到末尾
中间插入O(n)后面的元素都要后移
删除O(n)后面的元素都要前移

3.3 Python 中的数组:list

数组基本操作
# 创建数组
arr = [3, 1, 4, 1, 5, 9, 2, 6]

# 访问 O(1)
print(arr[0])   # 3
print(arr[3])   # 1

# 查找 O(n)
idx = arr.index(5)  # 找到 5 的下标

# 尾部插入 O(1)
arr.append(7)

# 中间插入 O(n)
arr.insert(2, 99)   # 在下标 2 处插入

# 删除 O(n)
arr.remove(99)      # 删除第一个值为 99 的元素
del arr[0]          # 删除下标 0 的元素

# 遍历 O(n)
for x in arr:
    print(x, end=" ")

3.4 动态数组的原理

动态数组扩容过程: 初始:容量=4, 长度=0 [_, _, _, _] 插入 4 个元素后满了: [3, 1, 4, 1] 再插入一个 → 触发扩容(容量翻倍) 申请新空间(容量=8),复制旧数据 [3, 1, 4, 1, 5, _, _, _] 扩容代价 O(n),但均摊下来每次插入还是 O(1)
为什么容量翻倍而不是加 1? 如果每次只加 1,每次插入都要扩容,总时间 O(n^2)。翻倍扩容:n 次插入最多触发 log n 次扩容,均摊 O(1)。这是空间换时间的经典策略。

3.5 经典题目:两数之和

暴力解法 O(n^2) vs 哈希优化 O(n)
# 暴力解法 O(n^2)
def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

# 哈希优化 O(n)
def two_sum_hash(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

print(two_sum_hash([2, 7, 11, 15], 9))  # [0, 1]

3.6 本章小结

本章要点回顾 • 数组是连续内存,支持 O(1) 随机访问
• 插入/删除需要移动元素,O(n)
• Python list 是动态数组,自动扩容(容量翻倍)
• 数组适合频繁读取、少修改的场景

第四章:链表——灵活的链条

4.1 什么是链表?

链表是一种不需要连续内存的数据结构。每个节点包含数据和指向下一个节点的指针。

类比:链表 = 寻宝游戏

想象一个寻宝游戏:第一个线索告诉你"去公园长椅下面找",长椅下面有纸条"去图书馆第三排书架"……每条线索都知道下一条在哪里,串成一整条链。你必须从头开始,一个一个跟下去。

单链表结构: head v +---+--> +---+--> +---+--> +---+--> None | 3 | | 1 | | 4 | | 1 | +---+ +---+ +---+ +---+ 每个节点 = 数据 + 指向下一个节点的指针

4.2 链表 vs 数组

对比数组链表
内存连续分散
随机访问O(1)O(n)
头部插入O(n)O(1)
尾部插入O(1)O(n) 或 O(1)
删除O(n)O(1)*
缓存友好好差

4.3 实现单链表

Python 实现单链表
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None

    def prepend(self, val):
        """头部插入 O(1)"""
        self.head = ListNode(val, self.head)

    def append(self, val):
        """尾部插入 O(n)"""
        node = ListNode(val)
        if not self.head:
            self.head = node
            return
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = node

    def delete(self, val):
        """删除第一个值为 val 的节点"""
        dummy = ListNode(0, self.head)
        prev, cur = dummy, self.head
        while cur:
            if cur.val == val:
                prev.next = cur.next
                break
            prev, cur = cur, cur.next
        self.head = dummy.next

    def display(self):
        parts = []
        cur = self.head
        while cur:
            parts.append(str(cur.val))
            cur = cur.next
        print(" -> ".join(parts) + " -> None")

ll = LinkedList()
ll.append(3); ll.append(1); ll.append(4)
ll.display()  # 3 -> 1 -> 4 -> None
ll.prepend(0)
ll.display()  # 0 -> 3 -> 1 -> 4 -> None

4.4 经典题目

反转链表(面试高频)
def reverse_list(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev
检测环(快慢指针)
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

4.5 本章小结

本章要点回顾 • 链表是非连续存储,通过指针串联
• 插入/删除 O(1)(已知位置时),查找 O(n)
• 哨兵节点(dummy node)简化边界处理
• 快慢指针是链表题的经典技巧

第五章:栈——后进先出

5.1 什么是栈?

栈是一种后进先出(LIFO)的数据结构。只能从一端(栈顶)进行插入和删除。

类比:栈 = 一摞盘子

食堂里一摞盘子:放盘子只能放在最上面(push),取盘子只能从最上面拿(pop)。最后放上去的,最先被取走——后进先出。

5.2 用 Python 实现栈

# Python 的 list 天然支持栈操作
stack = []
stack.append(1)   # 入栈 O(1)
stack.append(2)
stack.append(3)
print(stack.pop())  # 出栈 → 3(后进先出)
print(stack[-1])    # 查看栈顶 → 2

5.3 经典应用:括号匹配

def is_valid(s):
    stack = []
    pairs = {")": "(", "]": "[", "}": "{"}
    for c in s:
        if c in "([{":
            stack.append(c)
        elif c in ")]}":
            if not stack or stack[-1] != pairs[c]:
                return False
            stack.pop()
    return len(stack) == 0

print(is_valid("({[]})"))  # True
print(is_valid("([)]"))    # False

5.4 经典应用:用栈实现计算器

def eval_rpn(tokens):
    """逆波兰表达式求值(后缀表达式)"""
    stack = []
    for t in tokens:
        if t in "+-*/":
            b, a = stack.pop(), stack.pop()
            if t == "+": stack.append(a + b)
            elif t == "-": stack.append(a - b)
            elif t == "*": stack.append(a * b)
            else: stack.append(int(a / b))
        else:
            stack.append(int(t))
    return stack[0]

# "2 1 + 3 *" = (2+1) * 3 = 9
print(eval_rpn(["2", "1", "+", "3", "*"]))  # 9

5.5 本章小结

本章要点回顾 • 栈 = 后进先出(LIFO),只能操作栈顶
• push/pop/peek 都是 O(1)
• 经典应用:括号匹配、表达式求值、DFS、撤销操作

第六章:队列——先来先排队

6.1 什么是队列?

队列是一种先进先出(FIFO)的数据结构。从队尾入队,从队头出队。

类比:队列 = 排队买奶茶

新来的人排到队尾(enqueue),队头的人先买到离开(dequeue)。先来的先走——先进先出。

6.2 用 Python 实现队列

from collections import deque

queue = deque()
queue.append("Alice")    # 入队 O(1)
queue.append("Bob")
queue.append("Charlie")
print(queue.popleft())   # 出队 O(1) → Alice
print(queue.popleft())   # → Bob
为什么用 deque 而不是 list? Python 的 list.pop(0) 是 O(n)(所有元素前移)。deque.popleft() 才是 O(1)。队列用 deque,不要用 list!

6.3 循环队列

循环队列用数组实现,让首尾相连,充分利用空间:

class CircularQueue:
    """用数组实现的循环队列"""
    def __init__(self, capacity):
        self.queue = [None] * capacity
        self.capacity = capacity
        self.front = 0
        self.rear = 0
        self.count = 0

    def enqueue(self, item):
        if self.count == self.capacity:
            raise Exception("队列已满")
        self.queue[self.rear] = item
        self.rear = (self.rear + 1) % self.capacity  # 循环
        self.count += 1

    def dequeue(self):
        if self.count == 0:
            raise Exception("队列为空")
        item = self.queue[self.front]
        self.front = (self.front + 1) % self.capacity  # 循环
        self.count -= 1
        return item

cq = CircularQueue(5)
cq.enqueue(1); cq.enqueue(2); cq.enqueue(3)
print(cq.dequeue())  # 1
print(cq.dequeue())  # 2

6.4 优先队列

优先队列(用堆实现)
import heapq

pq = []
heapq.heappush(pq, 3)
heapq.heappush(pq, 1)
heapq.heappush(pq, 4)
print(heapq.heappop(pq))  # 1(最小的先出)

6.4 本章小结

本章要点回顾 • 队列 = 先进先出(FIFO)
• Python 用 deque 实现 O(1) 入出队
• 优先队列按优先级出队,用堆实现

第七章:哈希表——闪电般的查找

7.1 什么是哈希表?

哈希表通过一个哈希函数把键映射到数组下标,实现 O(1) 的查找、插入和删除。

类比:哈希表 = 图书馆索引系统

图书馆有 100 万个座位,找"张三":
• 没有索引:从第 1 个开始一个一个找 → O(n)
• 有索引:算一下姓氏笔画 → 直接走到第 38 号书架 → O(1)

7.2 哈希冲突

两个不同的键可能映射到同一个位置——这叫哈希冲突。

方法原理优点缺点
链地址法冲突位置挂链表简单,负载因子可 > 1链表长了变慢
开放寻址法冲突了找下一个空位缓存友好负载因子不能太高

7.3 Python 中的哈希表

# dict 和 set 都是哈希表
d = {"apple": 1, "banana": 2}
print(d["apple"])     # O(1) 查找
d["cherry"] = 3       # O(1) 插入

s = {1, 2, 3}
s.add(4)              # O(1)
print(3 in s)         # O(1) 查找

# 注意:只有可哈希的类型才能做键
# 可哈希:int, str, tuple
# 不可哈希:list, dict, set

7.4 本章小结

本章要点回顾 • 哈希表通过哈希函数实现 O(1) 查找/插入/删除
• 哈希冲突用链地址法或开放寻址法解决
• Python 的 dict 和 set 都是哈希表
• 哈希表是用空间换时间的典范

第八章:树与二叉树

8.1 什么是树?

树是一种层次结构的数据结构。就像一棵倒着的树,根在上面,叶子在下面。

类比:树 = 公司组织架构

CEO 是根节点,各部门总监是子节点,普通员工是叶子节点。每个人只有一个直接上级,但可以有多个下属。

二叉树示例: 1 根节点:1 / \ 叶子节点:4, 5, 3 2 3 深度:0(根) → 1 → 2 / \ 4 5 前序遍历(根左右):1, 2, 4, 5, 3 中序遍历(左根右):4, 2, 5, 1, 3 后序遍历(左右根):4, 5, 2, 3, 1 层序遍历(逐层) :1, 2, 3, 4, 5

8.2 二叉树的遍历

递归实现三种遍历
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorder(root):
    """前序:根->左->右"""
    if not root: return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def inorder(root):
    """中序:左->根->右"""
    if not root: return []
    return inorder(root.left) + [root.val] + inorder(root.right)

def postorder(root):
    """后序:左->右->根"""
    if not root: return []
    return postorder(root.left) + postorder(root.right) + [root.val]

from collections import deque
def level_order(root):
    """层序遍历(BFS)"""
    if not root: return []
    result, queue = [], deque([root])
    while queue:
        node = queue.popleft()
        result.append(node.val)
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)
    return result

8.3 递归思维

树的递归定义 一棵二叉树 = 根节点 + 左子树 + 右子树。左子树和右子树本身也是二叉树——这就是递归!
处理树的问题 99% 用递归:终止条件 → 处理当前 → 递归子树。
求树的高度
def max_depth(root):
    if not root: return 0
    return max(max_depth(root.left), max_depth(root.right)) + 1

8.4 本章小结

本章要点回顾 • 树是层次结构,二叉树每个节点最多两个子节点
• 四种遍历:前序、中序、后序、层序
• 树的问题几乎都用递归解决

第九章:二叉搜索树(BST)

9.1 BST 的性质

二叉搜索树的核心性质:左子树所有节点 < 根 < 右子树所有节点。

类比:BST = 猜数字游戏

在 1~100 之间猜数字:猜 50,说"大了"→ 只需在 1~49 中继续猜。每次排除一半——这就是 BST 查找的思路!

BST 示例: 8 / \ 3 10 / \ \ 1 6 14 中序遍历(有序):1, 3, 6, 8, 10, 14

9.2 BST 的操作

def search_bst(root, target):
    """查找 O(log n) 平均"""
    if not root: return None
    if target == root.val: return root
    if target < root.val: return search_bst(root.left, target)
    return search_bst(root.right, target)

def insert_bst(root, val):
    """插入 O(log n) 平均"""
    if not root: return TreeNode(val)
    if val < root.val: root.left = insert_bst(root.left, val)
    elif val > root.val: root.right = insert_bst(root.right, val)
    return root
BST 的致命缺陷:可能退化成链表 如果按顺序插入 1, 2, 3, 4, 5,BST 变成一条链,所有操作都变成 O(n)。解决方案:平衡二叉树。

9.3 本章小结

本章要点回顾 • BST 性质:左 < 根 < 右,中序遍历有序
• 查找/插入/删除平均 O(log n)
• 缺点:可能退化成链表 O(n),需要平衡机制

第十章:平衡树

10.1 为什么需要平衡?

BST 可能退化成链表。平衡树通过自动调整,保证树的高度始终是 O(log n)。

10.2 AVL 树 vs 红黑树

对比AVL 树红黑树
平衡标准严格(高度差 ≤ 1)宽松(最长路径 ≤ 2×最短)
查找更快(树更矮)稍慢
插入/删除旋转次数多旋转次数少
适用场景查找密集插入删除频繁
实际使用数据库索引Java TreeMap、Linux 内核

10.3 B 树和 B+ 树

为什么数据库用 B+ 树? 磁盘 IO 是瓶颈。B+ 树每个节点存几百个键,3 层就能索引几亿条数据,只需 3 次 IO。层数越少 → IO 越少 → 越快。MySQL InnoDB 就用 B+ 树。

10.4 本章小结

本章要点回顾 • AVL 树严格平衡,查找快;红黑树近似平衡,插入删除快
• B+ 树是数据库索引的标准选择
• 内存中用红黑树/AVL,磁盘上用 B+ 树

第十一章:堆——优先级的世界

11.1 什么是堆?

堆是一种特殊的完全二叉树:最大堆中父节点 ≥ 子节点,最小堆中父节点 ≤ 子节点。

类比:堆 = 公司职级

最大堆像公司:总经理 > 部门经理 > 普通员工。任何时候你都能快速找到"最大的那个"(堆顶)。

最大堆示例(完全二叉树 + 父 >= 子): 9 / \ 7 8 / \ / \ 3 5 6 4 堆顶 = 最大值 = 9 用数组表示:[9, 7, 8, 3, 5, 6, 4] 父节点下标 i → 左子 2i+1,右子 2i+2

11.2 堆的核心操作

import heapq

# Python 的 heapq 是最小堆
heap = []
heapq.heappush(heap, 3)   # 插入 O(log n)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
print(heapq.heappop(heap)) # 弹出最小值 O(log n) → 1

# 从列表建堆 O(n)
nums = [5, 3, 8, 1, 2]
heapq.heapify(nums)
print(nums)  # [1, 2, 8, 3, 5](堆的数组表示)

# 最大堆技巧:取负数
max_heap = []
for x in [3, 1, 4]:
    heapq.heappush(max_heap, -x)
print(-heapq.heappop(max_heap))  # 4

11.3 堆排序

def heap_sort(arr):
    """堆排序 O(n log n)"""
    heapq.heapify(arr)           # 建堆 O(n)
    result = []
    while arr:
        result.append(heapq.heappop(arr))  # 逐个弹出 O(log n)
    return result

print(heap_sort([5, 3, 8, 1, 2]))  # [1, 2, 3, 5, 8]

11.4 经典应用:Top-K 问题

import heapq

def top_k(nums, k):
    """找出最大的 K 个数 O(n log k)"""
    return heapq.nlargest(k, nums)

print(top_k([3, 1, 4, 1, 5, 9, 2, 6], 3))  # [9, 6, 5]

11.5 本章小结

本章要点回顾 • 堆是完全二叉树,堆顶是最大/最小值
• 插入/删除都是 O(log n)
• Python 用 heapq 模块(最小堆)
• 经典应用:Top-K、优先队列、堆排序

第十二章:图——万物皆相连

12.1 什么是图?

图由顶点(节点)和边组成,用来表示"多对多"的关系。

类比:图 = 社交网络

微信好友关系就是一张图:每个人是节点,好友关系是边。你和朋友之间可能有共同好友,形成复杂的网络。

图的分类: 无向图(好友关系): 有向图(关注关系): 加权图(路线距离): A --- B A → B A --5-- B | / | ↑ ↓ | | | / | D ← C 3 2 | / | | | C --- D D --1-- C

12.2 图的存储方式

邻接矩阵 vs 邻接表
# 邻接矩阵(适合稠密图)
# graph[i][j] = 1 表示 i 和 j 之间有边
graph_matrix = [
    [0, 1, 1, 0],  # 节点 0 连接 1, 2
    [1, 0, 1, 1],  # 节点 1 连接 0, 2, 3
    [1, 1, 0, 1],  # 节点 2 连接 0, 1, 3
    [0, 1, 1, 0],  # 节点 3 连接 1, 2
]

# 邻接表(适合稀疏图,更常用)
from collections import defaultdict
graph = defaultdict(list)
edges = [(0,1), (0,2), (1,2), (1,3), (2,3)]
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)  # 无向图要加反向边

# graph = {0: [1,2], 1: [0,2,3], 2: [0,1,3], 3: [1,2]}
对比邻接矩阵邻接表
空间O(n^2)O(n + m)
判断是否有边O(1)O(degree)
遍历邻居O(n)O(degree)
适用稠密图稀疏图(更常用)

12.3 DFS 和 BFS

from collections import deque

def dfs(graph, start, visited=None):
    """深度优先搜索"""
    if visited is None: visited = set()
    visited.add(start)
    print(start, end=" ")
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

def bfs(graph, start):
    """广度优先搜索"""
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        print(node, end=" ")
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

12.4 本章小结

本章要点回顾 • 图由顶点和边组成,表示多对多关系
• 存储方式:邻接矩阵(稠密图)vs 邻接表(稀疏图)
• DFS 用栈/递归,BFS 用队列
• DFS 适合路径搜索,BFS 适合最短路径(无权图)

第十三章:图的经典算法

13.1 最短路径:Dijkstra 算法

Dijkstra 算法求单源最短路径——从一个起点到其他所有点的最短距离。要求边权非负。

Dijkstra = 导航软件

导航软件找最短路线的原理:从你的位置出发,每次都走当前"最近的未访问路口",逐步扩展,直到覆盖所有路口。

import heapq

def dijkstra(graph, start):
    """Dijkstra 最短路径 O((V+E) log V)"""
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]  # (距离, 节点)

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]: continue
        for v, w in graph[u]:  # (邻居, 权重)
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

# 带权图(邻接表)
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('A', 1), ('C', 2), ('D', 5)],
    'C': [('A', 4), ('B', 2), ('D', 1)],
    'D': [('B', 5), ('C', 1)]
}
print(dijkstra(graph, 'A'))  # {'A':0, 'B':1, 'C':3, 'D':4}

13.2 最小生成树:Kruskal 算法

最小生成树:用最少的边权总和连接所有节点。

def kruskal(n, edges):
    """Kruskal 最小生成树"""
    edges.sort(key=lambda x: x[2])  # 按权重排序
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    mst_weight = 0
    for u, v, w in edges:
        pu, pv = find(u), find(v)
        if pu != pv:
            parent[pu] = pv
            mst_weight += w
    return mst_weight

13.3 拓扑排序

拓扑排序用于有向无环图(DAG)——把节点排成一个线性序列,使得所有边从前指向后。

拓扑排序 = 选课顺序

大学里有些课有先修要求:学数据结构之前要学程序设计,学操作系统之前要学数据结构。拓扑排序就是找到一个合法的选课顺序。

from collections import deque, defaultdict

def topological_sort(num_courses, prerequisites):
    """拓扑排序(BFS / Kahn 算法)"""
    graph = defaultdict(list)
    in_degree = [0] * num_courses
    for dest, src in prerequisites:
        graph[src].append(dest)
        in_degree[dest] += 1

    queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return order if len(order) == num_courses else []

# 课程 0->1->2 的依赖关系
print(topological_sort(3, [[1,0], [2,1]]))  # [0, 1, 2]

13.4 本章小结

本章要点回顾 • Dijkstra:单源最短路径(非负权),O((V+E) log V)
• Kruskal/Prim:最小生成树
• 拓扑排序:DAG 的线性排序,用于任务调度

第十四章:排序算法大比拼

14.1 排序算法总览

算法时间(平均)时间(最坏)空间稳定性
冒泡排序O(n^2)O(n^2)O(1)稳定
选择排序O(n^2)O(n^2)O(1)不稳定
插入排序O(n^2)O(n^2)O(1)稳定
归并排序O(n log n)O(n log n)O(n)稳定
快速排序O(n log n)O(n^2)O(log n)不稳定
堆排序O(n log n)O(n log n)O(1)不稳定
计数排序O(n+k)O(n+k)O(k)稳定

14.2 冒泡排序

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

14.3 快速排序(最常用)

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

print(quick_sort([5, 3, 8, 1, 2]))  # [1, 2, 3, 5, 8]

14.4 归并排序

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

14.5 本章小结

本章要点回顾 • 小数据量用插入排序,大数据量用快速排序/归并排序
• 快排平均最快 O(n log n),最坏 O(n^2)
• 归并排序稳定 O(n log n),但需要额外空间
• Python 的 sort() 用 Timsort(归并+插入的混合)

第十五章:查找算法

15.1 顺序查找

def linear_search(arr, target):
    for i, x in enumerate(arr):
        if x == target: return i
    return -1  # O(n)

15.2 二分查找

前提:数组必须有序 二分查找每次排除一半,O(log n)。100 万个数据最多查 20 次。
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target: return mid
        elif arr[mid] < target: left = mid + 1
        else: right = mid - 1
    return -1

# 变体:查找第一个 >= target 的位置
def lower_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target: left = mid + 1
        else: right = mid
    return left

15.3 查找方式对比

方法时间要求适用场景
顺序查找O(n)无无序小数组
二分查找O(log n)有序数组有序大数组
哈希查找O(1)哈希表频繁查找
树查找O(log n)BST/平衡树动态数据

15.4 本章小结

本章要点回顾 • 顺序查找 O(n),简单但慢
• 二分查找 O(log n),要求有序
• 哈希查找 O(1),最快但无序
• 根据场景选择合适的查找方式

第十六章:分治算法

16.1 什么是分治?

分治(Divide and Conquer)的核心思想:把大问题拆成小问题,分别解决,再合并结果。

类比:分治 = 分蛋糕

一个大蛋糕不好切?先切成两半,每半再切成两半……直到切成小块。每小块很容易处理。最后把结果拼起来。

分治三步: 1. 分(Divide):把问题拆成若干子问题 2. 治(Conquer):递归解决子问题 3. 合(Combine):合并子问题的解

16.2 经典分治:归并排序

def merge_sort(arr):
    if len(arr) <= 1: return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])     # 分
    right = merge_sort(arr[mid:])    # 分
    return merge(left, right)        # 合

16.3 经典分治:快速幂

def power(base, exp):
    """快速求 base^exp O(log exp)"""
    if exp == 0: return 1
    if exp % 2 == 0:
        half = power(base, exp // 2)
        return half * half            # 分治
    else:
        return base * power(base, exp - 1)

print(power(2, 10))  # 1024

16.4 本章小结

本章要点回顾 • 分治 = 分 + 治 + 合
• 归并排序、快速排序、快速幂都是分治
• 分治常与递归结合,时间复杂度通常是 O(n log n)

第十七章:贪心算法

17.1 什么是贪心?

贪心算法的核心:每一步都选当前看起来最优的,不考虑全局,最终得到全局最优解。

类比:贪心 = 吃自助餐

吃自助餐的贪心策略:每道菜都挑最好吃的先吃。虽然不一定能吃到"全局最优组合",但在很多场景下效果很好。

17.2 经典问题:活动选择

def activity_selection(activities):
    """选择最多的不重叠活动"""
    activities.sort(key=lambda x: x[1])  # 按结束时间排序
    count = 0
    last_end = 0
    for start, end in activities:
        if start >= last_end:  # 贪心:选最早结束的
            count += 1
            last_end = end
    return count

17.3 经典问题:分糖果

def find_content_children(children, cookies):
    """每个孩子分配一块饼干,求最多满足几个孩子"""
    children.sort()
    cookies.sort()
    child = cookie = 0
    while child < len(children) and cookie < len(cookies):
        if cookies[cookie] >= children[child]:
            child += 1  # 满足了这个孩子
        cookie += 1
    return child

17.4 贪心的适用条件

贪心能用的前提 1. 贪心选择性质:局部最优能导致全局最优
2. 最优子结构:问题的最优解包含子问题的最优解

不是所有问题都能用贪心!如果局部最优不能保证全局最优,就需要动态规划。

17.5 本章小结

本章要点回顾 • 贪心:每步选当前最优,不回头
• 适用条件:贪心选择性质 + 最优子结构
• 典型应用:活动选择、哈夫曼编码、最小生成树

第十八章:回溯算法

18.1 什么是回溯?

回溯 = 试探 + 撤销。走一步试试,不行就退回来,换一条路继续试。

类比:回溯 = 走迷宫

走迷宫时:选一条路走到底。遇到死胡同?退回来,换一条路。直到找到出口或所有路都试完。

回溯模板: def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 # 把选择加入路径 backtrack(路径, 选择列表) 撤销选择 # 把选择从路径移除(回溯!)

18.2 经典问题:全排列

def permute(nums):
    """生成全排列"""
    result = []
    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return
        for i, num in enumerate(remaining):
            path.append(num)
            backtrack(path, remaining[:i] + remaining[i+1:])
            path.pop()  # 回溯:撤销选择

    backtrack([], nums)
    return result

print(permute([1, 2, 3]))
# [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

18.3 经典问题:N 皇后

def solve_n_queens(n):
    """N 皇后问题"""
    result = []
    def backtrack(row, cols, diag1, diag2, board):
        if row == n:
            result.append(["".join(r) for r in board])
            return
        for col in range(n):
            if col in cols or row-col in diag1 or row+col in diag2:
                continue  # 剪枝
            board[row][col] = 'Q'
            backtrack(row+1, cols|{col}, diag1|{row-col},
                     diag2|{row+col}, board)
            board[row][col] = '.'  # 回溯

    backtrack(0, set(), set(), set(),
              [['.']*n for _ in range(n)])
    return result

18.4 本章小结

本章要点回顾 • 回溯 = 试探 + 撤销,穷举所有可能
• 核心:做选择 → 递归 → 撤销选择
• 剪枝可以大幅减少搜索空间
• 典型应用:全排列、组合、N 皇后、数独

第十九章:动态规划——从零到精通

19.1 什么是动态规划?

动态规划(DP)的核心:把大问题拆成重叠子问题,记住子问题的解,避免重复计算。

类比:DP = 考试带笔记本

普通递归就像闭卷考试:同一道题反复做。DP 就像开卷考试:做过的题记在笔记本上,下次直接查答案。

对比贪心回溯动态规划
策略每步选最优穷举所有可能记住子问题解
是否回退不回退回退不回退
适用局部最优=全局最优需要穷举最优子结构+重叠子问题

19.2 斐波那契数列:DP 入门

# 普通递归 O(2^n) —— 大量重复计算
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

# 动态规划 O(n) —— 记住已算过的
def fib_dp(n):
    if n <= 1: return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# 空间优化 O(1)
def fib_opt(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

19.3 背包问题(DP 经典)

def knapsack(weights, values, capacity):
    """0-1 背包问题"""
    n = len(weights)
    # dp[i][w] = 前 i 个物品、容量为 w 时的最大价值
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i-1][w]  # 不选第 i 个
            if w >= weights[i-1]:
                dp[i][w] = max(dp[i][w],
                    dp[i-1][w - weights[i-1]] + values[i-1])
    return dp[n][capacity]

print(knapsack([2,3,4,5], [3,4,5,6], 8))  # 10

19.4 最长公共子序列(LCS)

def lcs(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

print(lcs("abcde", "ace"))  # 3 ("ace")

19.5 DP 解题四步法

1
定义状态——dp[i] 或 dp[i][j] 代表什么?
2
状态转移方程——dp[i] 怎么从 dp[i-1] 推导出来?
3
初始条件——dp[0] 等于什么?
4
遍历顺序——正序还是倒序?

19.6 本章小结

本章要点回顾 • DP = 记忆化搜索,避免重复计算
• 适用条件:最优子结构 + 重叠子问题
• 四步法:定义状态 → 转移方程 → 初始条件 → 遍历顺序
• 经典问题:背包、LCS、编辑距离、爬楼梯

第二十章:高级数据结构

20.1 字典树(Trie)

Trie 是一种专门处理字符串前缀的树结构,广泛用于搜索引擎自动补全、拼写检查。

Trie 结构(存储 "cat", "car", "dog"): root / | \ c d / \ a o / \ \ t r g 查找 "car":root -> c -> a -> r(存在!) 前缀 "ca" 匹配:cat, car
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True

    def search(self, word):
        node = self.root
        for c in word:
            if c not in node.children: return False
            node = node.children[c]
        return node.is_end

trie = Trie()
trie.insert("cat"); trie.insert("car")
print(trie.search("cat"))   # True
print(trie.search("ca"))    # False

20.2 并查集(Union-Find)

并查集用于处理连通性问题:判断两个元素是否属于同一集合,合并两个集合。

并查集 = 帮派系统

一群人各自为派:A 和 B 结盟 → 合并为一派。C 和 D 结盟 → 合并为一派。问"A 和 C 是一派吗?"→ 查找他们各自的"帮主"。

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        """查找根节点(带路径压缩)"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        """合并两个集合"""
        px, py = self.find(x), self.find(y)
        if px == py: return
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1

    def connected(self, x, y):
        return self.find(x) == self.find(y)

uf = UnionFind(5)
uf.union(0, 1); uf.union(2, 3)
print(uf.connected(0, 1))  # True
print(uf.connected(0, 2))  # False

20.3 线段树

线段树用于区间查询和区间修改,支持 O(log n) 的区间求和、区间最大值等操作。

class SegmentTree:
    """线段树:区间求和"""
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (4 * self.n)
        self._build(data, 1, 0, self.n - 1)

    def _build(self, data, node, start, end):
        if start == end:
            self.tree[node] = data[start]
            return
        mid = (start + end) // 2
        self._build(data, 2*node, start, mid)
        self._build(data, 2*node+1, mid+1, end)
        self.tree[node] = self.tree[2*node] + self.tree[2*node+1]

    def query(self, left, right):
        """查询区间 [left, right] 的和 O(log n)"""
        return self._query(1, 0, self.n-1, left, right)

    def _query(self, node, start, end, left, right):
        if right < start or end < left: return 0
        if left <= start and end <= right: return self.tree[node]
        mid = (start + end) // 2
        return (self._query(2*node, start, mid, left, right) +
                self._query(2*node+1, mid+1, end, left, right))

st = SegmentTree([1, 3, 5, 7, 9, 11])
print(st.query(1, 3))  # 3+5+7 = 15

20.4 布隆过滤器

布隆过滤器(Bloom Filter) 一种概率型数据结构,用于判断"某个元素是否在集合中"。可能误判存在(假阳性),但不会误判不存在。空间效率极高,广泛用于爬虫去重、缓存穿透防护。

20.4 本章小结

本章要点回顾 • Trie:字符串前缀匹配,O(m) 查找(m 为字符串长度)
• 并查集:连通性判断,接近 O(1)
• 线段树:区间查询/修改 O(log n)
• 布隆过滤器:概率型存在性判断,极省内存

第二十一章:经典面试题与实战

21.1 LRU 缓存

LRU(Least Recently Used)缓存淘汰最久没使用的数据。面试高频题!

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key):
        if key not in self.cache: return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

cache = LRUCache(2)
cache.put(1, 1); cache.put(2, 2)
print(cache.get(1))     # 1
cache.put(3, 3)          # 淘汰 key=2
print(cache.get(2))     # -1

21.2 用栈实现队列

class MyQueue:
    def __init__(self):
        self.stack_in = []
        self.stack_out = []

    def push(self, x):
        self.stack_in.append(x)

    def pop(self):
        if not self.stack_out:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
        return self.stack_out.pop()

21.3 二叉树的最近公共祖先(LCA)

def lowest_common_ancestor(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right: return root
    return left or right

21.4 滑动窗口最大值

from collections import deque

def max_sliding_window(nums, k):
    """滑动窗口最大值(单调队列)"""
    result = []
    dq = deque()  # 存下标,保持队列单调递减
    for i, num in enumerate(nums):
        while dq and nums[dq[-1]] <= num:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]

21.5 更多经典题目清单

题目数据结构难度
有效的括号栈简单
合并两个有序链表链表简单
二叉树的最大深度树 + 递归简单
反转链表链表简单
两数之和哈希表简单
三数之和排序 + 双指针中等
岛屿数量DFS/BFS中等
课程表拓扑排序中等
最长递增子序列DP / 二分中等
接雨水双指针 / 栈困难
最小覆盖子串滑动窗口困难
编辑距离DP中等

21.6 本章小结

本章要点回顾 • LRU 缓存 = 哈希表 + 双向链表
• 单调队列解决滑动窗口最值
• LCA 是树的经典问题
• 多刷题、多总结,面试就不慌

附录:速查手册

A. 各数据结构时间复杂度对比

数据结构访问查找插入删除
数组O(1)O(n)O(n)O(n)
链表O(n)O(n)O(1)O(1)
栈O(n)O(n)O(1)O(1)
队列O(n)O(n)O(1)O(1)
哈希表-O(1)O(1)O(1)
BSTO(log n)O(log n)O(log n)O(log n)
堆O(1)(堆顶)O(n)O(log n)O(log n)

B. 排序算法速查

算法平均最坏空间稳定
冒泡O(n^2)O(n^2)O(1)Yes
插入O(n^2)O(n^2)O(1)Yes
归并O(n log n)O(n log n)O(n)Yes
快排O(n log n)O(n^2)O(log n)No
堆排O(n log n)O(n log n)O(1)No

C. Python 内置数据结构速查

Python 常用数据结构
# list —— 动态数组
lst = [1, 2, 3]
lst.append(4)     # O(1)
lst.pop()          # O(1)
lst[0]             # O(1) 访问

# deque —— 双端队列
from collections import deque
dq = deque([1, 2, 3])
dq.append(4)       # 右端入 O(1)
dq.popleft()       # 左端出 O(1)

# dict —— 哈希表
d = {"a": 1}
d["a"]             # O(1) 查找
d["b"] = 2         # O(1) 插入

# set —— 集合(哈希表)
s = {1, 2, 3}
s.add(4)           # O(1)
3 in s             # O(1) 查找

# heapq —— 最小堆
import heapq
heap = [3, 1, 2]
heapq.heapify(heap)    # O(n)
heapq.heappush(heap, 0)  # O(log n)
heapq.heappop(heap)      # O(log n)

# defaultdict —— 带默认值的字典
from collections import defaultdict
dd = defaultdict(int)
dd["key"] += 1     # 自动初始化为 0

D. 推荐学习资源

推荐资源 • LeetCode:刷题必备,从 Easy 开始
• 《算法导论》:经典教材,深入理论
• 《大话数据结构》:通俗易懂,适合入门
• Visualgo.net:算法可视化网站
• Hello 算法:hello-algo.com,图解数据结构