WD-L/W/R/N
搜索
T 教程 Tutorials

Python 数据结构与算法基础（带动画示意）

约 3 分钟
Python算法数据结构DSA可视化教程

中文长文：数组、链表、栈与队列、树、排序、BFS/DFS；内嵌赤霞珠配色 SVG/JS 交互演示（冒泡/插入排序、链表插入、栈、二叉树 BFS），无重依赖、Pagefind 友好。

教程

把常见结构与算法用 Python 写一遍，并配上可逐步播放的示意（静态博客里用轻量 SVG + 原生 JS，赤霞珠配色）。演示块带 data-pagefind-ignore，不污染全文搜索。

交互控件：每个示意下方有 播放 / 暂停 / 单步 / 重置（栈为 Push/Pop）。若脚本未加载，请硬刷新。

学习路径

  1. 数组与复杂度直觉
  2. 链表与指针改写
  3. 栈 / 队列
  4. 树与遍历
  5. 排序（冒泡、插入，及对比）
  6. BFS / DFS

每个专题先写「干什么」，再给最小代码，最后给动画（若适用）。

数组（Array / List）

Python list 是动态数组：按下标 $O(1)$ 读写，末尾追加摊销 $O(1)$，中间插入/删除 $O(n)$。

a = [5, 3, 8, 4]
a.append(2)       # 尾部
a.insert(1, 9)    # 下标 1 插入，后面元素后移
x = a.pop()       # 弹出尾部
y = a.pop(0)      # 弹出头部，O(n)

适用：随机访问、紧凑内存、双指针 / 滑动窗口。
慎用：头部频繁插入删除 → 看 collections.deque。

前缀和模板：

def prefix_sums(nums: list[int]) -> list[int]:
    ps = [0]
    for x in nums:
        ps.append(ps[-1] + x)
    return ps  # sum(nums[l:r]) == ps[r] - ps[l]

链表（Linked List）

节点存值与后继。插入删除在「已知前驱」时 $O(1)$，随机访问 $O(n)$。

from __future__ import annotations
from dataclasses import dataclass

@dataclass
class Node:
    val: int
    next: Node | None = None

def insert_after(prev: Node, val: int) -> Node:
    nxt = Node(val, prev.next)
    prev.next = nxt
    return nxt

哨兵头简化边界：

def remove_values(head: Node | None, target: int) -> Node | None:
    dummy = Node(0, head)
    cur = dummy
    while cur.next:
        if cur.next.val == target:
            cur.next = cur.next.next
        else:
            cur = cur.next
    return dummy.next

动画：在节点后插入

下面演示在 2 → 5 → 9 的 5 之后插入 7。

要点：改的是指针，不是「数组搬移」。找前驱仍可能 $O(n)$。

栈与队列（Stack / Queue）

栈：LIFO

用 list 即可：append / pop。

stack: list[int] = []
stack.append(3)
stack.append(1)
stack.append(4)
top = stack.pop()  # 4

经典：括号匹配、单调栈、DFS 显式化、表达式求值。

队列：FIFO

from collections import deque

q: deque[int] = deque()
q.append(1)       # enqueue
q.append(2)
x = q.popleft()   # dequeue → 1

不要用 list.pop(0) 当队列。双端队列还可 appendleft / pop。

树（Binary Tree）

@dataclass
class TreeNode:
    val: int
    left: TreeNode | None = None
    right: TreeNode | None = None

建一棵完全二叉树示例：

def demo_tree() -> TreeNode:
    #      1
    #    /   \
    #   2     3
    #  / \   / \
    # 4   5 6   7
    return TreeNode(
        1,
        TreeNode(2, TreeNode(4), TreeNode(5)),
        TreeNode(3, TreeNode(6), TreeNode(7)),
    )

深度 ≈ 递归层数；平衡时常见操作 $O(\log n)$，退化成链则 $O(n)$。

排序：冒泡与插入

先吃透「交换 / 插入」的局部不变量，再记 $O(n\log n)$ 的快排归并堆排。

冒泡排序

反复比较相邻元素，大的后移；每轮把最大值「冒」到未排序后缀。

def bubble_sort(a: list[int]) -> list[int]:
    a = a[:]
    n = len(a)
    for end in range(n, 1, -1):
        swapped = False
        for j in range(end - 1):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            break
    return a

时间 $O(n^2)$，稳定；教学友好。

插入排序

维护左侧有序前缀，将下一个元素插入正确位置。

def insertion_sort(a: list[int]) -> list[int]:
    a = a[:]
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

近乎有序时接近 $O(n)$；稳定。

怎么选

算法最好平均最坏稳定备注
冒泡$O(n)$$O(n^2)$$O(n^2)$是教学
插入$O(n)$$O(n^2)$$O(n^2)$是小数组 / 近有序
快排$O(n\log n)$$O(n\log n)$$O(n^2)$否实用默认
归并$O(n\log n)$$O(n\log n)$$O(n\log n)$是要稳定性
堆排$O(n\log n)$$O(n\log n)$$O(n\log n)$否原地

Python 的 list.sort / sorted 是 Timsort（归并+插入混合），实战优先。

BFS 与 DFS

图或树的两种基础遍历。树可看作无环图。

DFS（深度优先）

递归或显式栈。先走一条路走到底。

def dfs_preorder(root: TreeNode | None) -> list[int]:
    out: list[int] = []
    def go(n: TreeNode | None) -> None:
        if not n:
            return
        out.append(n.val)
        go(n.left)
        go(n.right)
    go(root)
    return out

BFS（广度优先 / 层序）

队列：先访问离起点近的。

from collections import deque

def bfs_level(root: TreeNode | None) -> list[int]:
    if not root:
        return []
    q: deque[TreeNode] = deque([root])
    order: list[int] = []
    while q:
        n = q.popleft()
        order.append(n.val)
        if n.left:
            q.append(n.left)
        if n.right:
            q.append(n.right)
    return order

动画：二叉树 BFS

高亮当前节点、队列与产出顺序。

层序模板（按层分组）：

def level_order(root: TreeNode | None) -> list[list[int]]:
    if not root:
        return []
    q: deque[TreeNode] = deque([root])
    ans: list[list[int]] = []
    while q:
        size = len(q)
        level: list[int] = []
        for _ in range(size):
            n = q.popleft()
            level.append(n.val)
            if n.left: q.append(n.left)
            if n.right: q.append(n.right)
        ans.append(level)
    return ans

对比

DFSBFS
结构栈 / 递归队列
擅长路径、连通、拓扑、记忆化搜索最短路（无权）、层序
空间视深度视一层宽度

复杂度速记

  • 写循环前先问：最坏会扫几遍数据？
  • 额外数组 / 哈希往往换时间。
  • 递归深度过大改迭代，或抬 sys.setrecursionlimit（治标）。
# 计时小抄
import time

def timed(fn, *args):
    t0 = time.perf_counter()
    r = fn(*args)
    print(f'{fn.__name__}: {time.perf_counter() - t0:.4f}s')
    return r

练习题建议

  1. 反转链表；检测环（快慢指针）。
  2. 用栈判括号有效；用单调栈每日温度。
  3. 二叉树最大深度；对称树；层序平均值。
  4. 手写插入排序后对比 sorted。
  5. 网格 m×n 上 BFS 最短步数（障碍物）。

本页技术说明（博客实现）

  • 示意挂载点：<div data-dsa-demo="..."></div>。
  • 样式 / 脚本：/scripts/dsa-demos.css、/scripts/dsa-demos.js（文章含 mount 时由布局注入）。
  • 无 React/D3；播放逻辑为原生 JS，颜色对齐赤霞珠变量。
  • 标记 data-pagefind-ignore，搜索仍以正文与代码为主。

算法要「看得见」：先动画建立不变量，再默写代码。

评论