模块 06: 核心数据结构

抽象数据类型规定操作与行为，数据结构实现它们。栈承诺后进先出，无论用数组还是链接。需区分操作约定与成本，按索引读取、头部删除、键查询或顺序扫描等工作负载选择，还要规定空情况、重复策略与可变值所有权。

数组把元素放入索引槽位，在通常 RAM 模型中支持常数索引访问。动态数组容量耗尽时扩容，单次追加可能复制 n 项，但几何增长让多次追加总复制线性，因此摊还 O(1)。头部插入需移动 O(n) 项。Python 列表保存对象引用，而非直接连续存放任意对象。局部性也影响实际扫描效率。

链节点保存值和下一节点引用，头部插入只改变少量引用。访问索引 i 要沿链前进，成本 O(i)。已知节点后插入 O(1)，寻找该节点却可能 O(n)。单链表删除通常需前驱。链接增加内存且可能降低局部性；栈实验展示这些引用。

栈先删除最新项，队列先删除最早项。撤销记录用栈，等待任务常用队列。链式栈在头部 O(1) 推入弹出。deque 支持两端高效操作，避免 list.pop(0) 移动引用。空删除需规定结果或异常。递归使用调用栈，广度搜索使用队列，行为顺序决定算法。

哈希函数把键映射到桶，不同键可碰撞，因此需在链中比较原键或采用其他策略。更新现有键应替换值而非重复插入。期望 O(1) 依赖合适哈希与受控负载，最坏链长可 O(n)。负载因子为项目数除桶数，必要时扩容重哈希。实验字节和哈希故意很差，变位词碰撞；Python 字典实现更复杂。

下载脚本，在终端中使用 Python 3.11 或更新版本运行：python m06_structures.py. Windows 也可使用 py -3；部分系统使用 python3。实验仅用标准库。先预测结果，再运行并完成变体。不要使用 -O，以保留断言。下方输出由构建器实际运行捕获，两种语言使用相同代码与输出。

跟踪 head、next 引用，比较相同输入的删除顺序。

下载 m06_structures.py

"""A linked stack and a FIFO queue with explicit empty behaviour."""
from collections import deque
class Node:
    def __init__(self, value, next_node=None):
        self.value, self.next = value, next_node
class Stack:
    def __init__(self):
        self.head = None
    def push(self, value):
        self.head = Node(value, self.head)
    def pop(self):
        if self.head is None:
            raise IndexError("empty stack")
        node = self.head
        self.head = node.next
        return node.value

stack, queue = Stack(), deque()
for book in ["Dune", "Foundation", "Solaris"]:
    stack.push(book); queue.append(book)
print("stack:", [stack.pop() for _ in range(3)])
print("queue:", [queue.popleft() for _ in range(3)])
try:
    stack.pop()
except IndexError:
    print("empty pop rejected")

stack: ['Solaris', 'Foundation', 'Dune']
queue: ['Dune', 'Foundation', 'Solaris']
empty pop rejected

1. 增加不删除的 peek。
2. 测试单次推入弹出与空队列。
3. 画出两次推入后的链。

ab 与 ba 同桶但键不同，更新 ab 不增加链长度。

下载 m06_hash.py

"""A deliberately small chained table makes collisions visible."""
class Table:
    def __init__(self, buckets=4):
        if buckets < 1:
            raise ValueError("positive bucket count required")
        self.buckets = [[] for _ in range(buckets)]
    def slot(self, key):
        return sum(key.encode("utf-8")) % len(self.buckets)
    def put(self, key, value):
        chain = self.buckets[self.slot(key)]
        for i, (stored, _) in enumerate(chain):
            if stored == key:
                chain[i] = (key, value); return
        chain.append((key, value))
    def get(self, key):
        for stored, value in self.buckets[self.slot(key)]:
            if stored == key:
                return value
        raise KeyError(key)

table = Table()
for key, value in [("ab", 1), ("ba", 2), ("c", 3), ("ab", 4)]:
    table.put(key, value)
print("chains:", table.buckets)
assert table.get("ab") == 4 and table.get("ba") == 2
try:
    table.get("missing")
except KeyError:
    print("missing key rejected")

chains: [[], [], [], [('ab', 4), ('ba', 2), ('c', 3)]]
missing key rejected

1. 仅用一桶，统计扫描项。
2. 增加删除并规定缺失键行为。
3. 桶数翻倍，重新插入所有项。

先尝试，再展开解答。★ 应用概念；★★ 结合概念；★★★ 进行设计或证明。

选择答案查看反馈，重置后可重做。无需 JavaScript 也可阅读答案表。

• Python deque — 比较两端操作与列表头部删除。

为每种结构说明适用负载，跟踪栈引用与碰撞更新。模块 07 将用栈和队列遍历递归结构。