← 返回学习中心ARC LAB / LEARNING NOTES

建立共同基础

数据结构与算法基础

容器、复杂度、查找排序与图遍历，用边界测试理解算法。

面向新成员 · 示例与练习
展开本篇目录

一、为什么学习数据结构与算法？

同样是“在成绩中查找一个人”，顺着列表逐个找、按学号查字典、在有序列表中二分查找，需要的前提和代价不同。数据结构负责组织数据，算法负责处理数据；先理解问题，再选择工具。

学习目标： 能解释常见容器的用途，估算操作次数，写出并验证查找、遍历和简单排序。先修知识为 Python 变量、循环、函数；本篇不要求先学高等数学。

建议路线：容器与复杂度 → 查找与排序 → 栈和队列 → 树与图 → 一个完整小实验。每一步先手画过程，再写代码，最后检查空输入和边界。

二、一张图认识数据结构

列表、字典、栈和队列的读取方式对照

结构 组织方式 适合的任务 Python 示例
列表 list 按位置排列，可重复 保存成绩、顺序遍历 [80, 90, 70]
字典 dict 键映射到值，键唯一 按学号查询 {"001": 80}
集合 set 元素唯一 去重、判断是否出现过 {"001", "002"}
栈 后进先出 撤销、括号匹配 list.append/pop
队列 先进先出 排队、广度优先搜索 collections.deque
树 父子层级，没有环 文件目录、表达式 嵌套节点
图 节点和边，可有环 路线、依赖与关系 邻接表字典

tuple 适合固定的一组值，例如坐标 (x, y)；不可修改元组元素，但元组内部引用的可变对象仍可能改变。

2.1 列表和字典怎样选择？

scores = [80, 90, 70]
print(scores[1])                 # 90，按位置取值
by_id = {"001": 80, "002": 90}
print(by_id.get("003"))          # None，缺失不等于 0 分

学号保存为字符串，避免 001 变成 1。字典的键必须可哈希，例如字符串、整数；列表不能直接作为字典键。对学号重复的输入，后写入字典的值会覆盖先前的值，需要先定义冲突策略。

三、时间复杂度：输入变大时会怎样？

线性查找与二分查找在不同输入规模下的理论比较次数

图中表示的是最坏情况下的理论比较次数，不是电脑运行时间。这里线性查找按 n 次、二分查找按 ceil(log2(n+1)) 次示意；不同具体实现可能相差常数。

复杂度 输入翻倍后的趋势 例子
O(1) 操作数量大致不随 n 增长 列表按下标读取
O(log n) 增长很慢 有序数组二分查找
O(n) 大约翻倍 扫描全部成绩
O(n log n) 高于线性、低于平方 常见高效排序的量级
O(n²) 大约变为四倍 双层循环比较所有配对

Big-O 描述增长上界的量级，不是精确秒数，也不意味着小数据上 O(log n) 一定更快。字典查找通常是平均 O(1)，极端碰撞情况不能按绝对常数保证。

空间复杂度关注额外内存。复制一个长度 n 的列表需要 O(n) 额外空间；算法快但复制大量数据，仍可能不适合内存受限的设备。

四、线性查找与二分查找

4.1 线性查找

def linear_search(values, target):
    for index, value in enumerate(values):
        if value == target:
            return index
    return -1

找到即返回第一个位置；没找到返回 -1。检查结果之前不要直接使用 values[result]，因为 Python 的 -1 是最后一个元素，并不会自动报错。

4.2 二分查找：输入必须有序

以 [55, 68, 72, 81, 81, 95] 查找 81 为例：每轮排除不可能的区间。下面用左闭右开区间 [left, right)，返回第一个等于目标的下标。

def binary_search(values, target):
    left, right = 0, len(values)
    while left < right:
        mid = (left + right) // 2
        if values[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left if left < len(values) and values[left] == target else -1

assert binary_search([55, 68, 72, 81, 81, 95], 81) == 3
assert binary_search([], 81) == -1

循环保持“第一个不小于目标的位置仍可能在边界收缩后的位置”的条件；退出时 left == right，再判断是否真的相等。更新为 left = mid 可能导致区间不缩小，从而死循环。

代价陷阱： 只查询一次就先排序，需要算上排序的 O(n log n)；二分得到的是排序后的下标，不是原始位置。标准库 bisect_left 提供类似的插入点查找，但要自己验证目标是否存在。

五、排序：先明确排序规则

students = [{"id": "002", "score": 90}, {"id": "001", "score": 90},
            {"id": "003", "score": 70}]
ranked = sorted(students, key=lambda row: (-row["score"], row["id"]))
print([row["id"] for row in ranked])   # ['001', '002', '003']

sorted 返回新列表；list.sort() 原地修改并返回 None。Python 排序是稳定的，相同排序键会保留原有先后顺序。上例额外规定同分时按学号升序，不依赖输入顺序碰巧正确。

5.1 用插入排序理解不变量

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

每轮结束后，前 i+1 项有序；最坏 O(n²)。适合学习过程，日常工程通常直接使用标准排序，而不是为了“手写算法”替换成熟实现。

六、栈与队列

from collections import deque
stack = []
stack.append("编辑标题")
stack.append("插入图片")
assert stack.pop() == "插入图片"  # 最近的动作先撤销

queue = deque(["任务A", "任务B"])
queue.append("任务C")
assert queue.popleft() == "任务A"

列表头部 pop(0) 会移动后续元素，是 O(n)；队列常用 deque.popleft()，避免每次搬移。空栈或空队列弹出会抛出 IndexError，调用前应检查或定义错误处理。

七、树、图、递归与 BFS

递归是函数调用自身，需要终止条件和向终止条件靠近的过程。递归调用会占用调用栈；很深的目录或图可能超过递归深度，不能把“提高递归上限”作为默认解决办法。

def factorial(n):
    if n < 0:
        raise ValueError("n 必须非负")
    return 1 if n <= 1 else n * factorial(n - 1)

图不一定连通，也可能有环。用邻接表记录“能走到谁”，BFS 用队列逐层访问：

from collections import deque

def bfs(graph, start):
    queue, seen, order = deque([start]), {start}, []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in seen:
                seen.add(neighbor)  # 入队时标记，避免重复入队
                queue.append(neighbor)
    return order

从 A→B、A→C、B→D、C→D、D→A 出发，结果为 A B C D。邻居顺序改变时，同层顺序可能改变。邻接表 BFS 的复杂度为 O(V+E)，只覆盖起点可达的节点。BFS 在无权图中可以扩展求最少边数路径；带权最短路需要其他方法。

八、完整实验与检查

下载 algorithms.py，执行：

python algorithms.py

预期结果：

first 81: 3
BFS: ['A', 'B', 'C', 'D']
counts: {'pass': 2, 'fail': 1}

脚本验证空数组、重复值、首尾值、缺失目标和有环图。继续补测试时，可将二分结果与 list.index 的结果对比；不要仅用同一段算法再写一遍当作“标准答案”。

九、常见错误排查

现象 常见原因 排查方式
二分找错 输入没排序、边界规则混用 写出每轮 left/right/mid
队列越来越大 没标记访问过的节点 检查入队时的 seen
排序后原列表变了 用了原地 sort 改用 sorted 或先复制
去重后顺序变化 用 set 当有序序列 明确是否需要保留首次顺序
有测试仍然失败 只测正常值 加空、重复、极值与不存在项

十、练习与参考思路

  1. 用字典统计学号出现次数，输出重复学号；不能简单用集合丢掉冲突证据。
  2. 写括号匹配函数：([]) 为真、([)] 为假、空串为真。思路：左括号入栈，右括号与栈顶匹配，结束后栈必须为空。
  3. 让 BFS 返回从 A 到 D 的一条最短路径。思路：首次访问时记录父节点，再从终点反向回溯。
  4. 给插入排序补 5 组测试，并验证原输入未被修改。
  5. 小项目：读取成绩记录，按学号检查冲突，按成绩排序；提交复杂度说明和至少 6 个边界案例。

完成标准： 能解释选择列表还是字典的原因，画出一次二分过程，说明复杂度和前提，代码在空输入时有明确行为。

十一、学习资料

← 继续探索学习路径反馈问题 ↗