简介《Python中的数据结构和算法》配套源码包面向Python开发者、计算机专业学生及算法备考者系统展示常见数据结构与算法的设计、分析与实现。作者借助Python简洁优雅的语法提供可执行源码并全程沿用面向对象思路利用继承提升代码复用便于观察各类抽象数据类型与算法间的异同。压缩包共124个文件其中123个为py源码文件另含1个gitignore总大小仅89KB轻量易读。源码覆盖二叉搜索树、链式二叉树、红黑树、表达式树、图、树、有序表映射、欧拉遍历、位置表等典型实现模块划分清楚适合逐一对照学习。已有732人学习下载无论用于课堂实践、面试复习还是日常查阅都能帮助读者快速理解经典结构的实现细节与设计精髓。1. 用 Python 学数据结构与算法为什么“面向对象视角”比抄源码更值得投入刷算法题和数据结构期末复习的时候最常见的做法是把书里的伪代码“翻译”成 Python 函数跑通两个用例就觉得自己会了。可换一道同类型题目、换一种底层存储立刻卡住。这份以>from abc import ABC, abstractmethod from typing import Generic, TypeVar T TypeVar(T) class StackBase(ABC, Generic[T]): 栈的抽象基类只约定操作与行为不约定存储方式。 abstractmethod def push(self, item: T) - None: 把 item 压到栈顶。 abstractmethod def pop(self) - T: 弹出栈顶元素空栈时抛 IndexError。 abstractmethod def peek(self) - T: 返回栈顶元素但不弹出空栈时抛 IndexError。 abstractmethod def is_empty(self) - bool: 栈是否为空。 abstractmethod def __len__(self) - int: 栈内元素个数。这段代码有几个刻意的设计。每个方法都标了abstractmethod子类漏实现任何一个实例化时都会失败这是“实现服从契约”的强制手段。pop和peek在空栈时抛IndexError而不是返回None因为None本身可能是合法元素用None做哨兵会让调用方分不清“栈空”和“元素就是 None”。Generic[T]让栈能标元素类型静态检查工具能帮你抓住类型错配。用__len__而不是size()是主动对齐 Python 内置协议之后可以直接写len(stack)。2.3 继承两个实现数组栈与链式栈共用同一套行为测试契约定完实现可以随便换。先看基于 Python 列表的数组栈class ArrayStack(StackBase[T]): 基于 Python 列表的栈append/pop 都是摊还 O(1)。 def __init__(self) - None: self._data: list[T] [] def push(self, item: T) - None: self._data.append(item) def pop(self) - T: if not self._data: raise IndexError(pop from empty stack) return self._data.pop() def peek(self) - T: if not self._data: raise IndexError(peek from empty stack) return self._data[-1] def is_empty(self) - bool: return not self._data def __len__(self) - int: return len(self._data)再写一个基于单向链表的版本。链表节点的__slots__声明有两个作用限制实例只能有value和next两个属性顺便省掉每个对象默认的__dict__在大规模数据下内存差得很明显class _LinkedNode(Generic[T]): __slots__ (value, next) def __init__(self, value: T) - None: self.value value self.next: _LinkedNode[T] | None None class LinkedStack(StackBase[T]): 基于单向链表的栈push/pop 严格 O(1)但有指针开销。 def __init__(self) - None: self._head: _LinkedNode[T] | None None self._count 0 def push(self, item: T) - None: node _LinkedNode(item) node.next self._head self._head node self._count 1 def pop(self) - T: if self._head is None: raise IndexError(pop from empty stack) value self._head.value self._head self._head.next self._count - 1 return value def peek(self) - T: if self._head is None: raise IndexError(peek from empty stack) return self._head.value def is_empty(self) - bool: return self._head is None def __len__(self) - int: return self._count继承在这里最大的收益是测试复用。下面这个函数只依赖StackBase的契约不关心具体是哪种栈def exercise_stack(stack: StackBase[int]) - None: assert stack.is_empty() stack.push(1) stack.push(2) assert len(stack) 2 assert stack.peek() 2 assert stack.pop() 2 assert stack.pop() 1 try: stack.pop() except IndexError: pass else: raise AssertionError(空栈 pop 应该抛 IndexError) exercise_stack(ArrayStack()) exercise_stack(LinkedStack())ArrayStack的peek和pop依赖列表的尾部索引LinkedStack依赖指针移动两者内部实现完全不同但外部行为被同一份exercise_stack验证。这正是项目里反复出现的主题继承让公共部分只写一次让差异部分被对比着看。数组栈缓存局部性好、内存连续链式栈插入删除的复杂度不受扩容影响但每个节点多存一个指针实际内存占用更高。知道这些差异才能在不同场景做对选择。3. 拆 Python 源码分析列表扩容再手写动态数组与双链表标题里的 “Python source code analysis” 在这个章节落点最实在。Python 的list并不是链表而是一个动态数组。很多人用了一年list都说不清为什么append快、insert(0, x)慢这节直接从 CPython 的列表实现讲起再按同样的扩容策略手写一个精简版最后补一个双向链表做对比。3.1 CPython list 的内存布局ob_item 指针数组与整体扩容在 CPython 的 listobject 定义里PyListObject的核心是一个指向PyObject*数组的指针ob_item同时维护两个长度已经使用的元素个数和已分配的容量。append时如果容量不够就会调用list_resize重新分配内存。关键在这里——它不是“用多少扩多少”而是提前多分配下次 append 就不用再触发分配。CPython 的list_resize里有一个著名的整体扩容公式大致是new_allocated newsize (newsize 3) (3 if newsize 9 else 6)其中newsize是扩容后的逻辑长度。翻译成人话容量比实际长度多出约 1/8小列表额外再多补几个槽位。这个“多分配”的策略换来的是 append 的摊还 O(1)——大部分 append 只是写一个指针偶尔才触发一次整体复制。反过来看insert(0, x)它要把所有元素往后挪一位不管容量够不够这一步就是 O(n)数据一多立刻看得出来。提示不同小版本的分配公式略有出入但“约 1/8 超量分配 小表保底”这个思想是稳定的。3.2 照着 CPython 的扩容策略手写一个 DynamicArray理解了 resize 策略就能手写一个最小可用的动态数组把黑匣子打开from typing import Generic, Optional, TypeVar T TypeVar(T) class DynamicArray(Generic[T]): 用固定容量列表模拟底层数组模仿 CPython 的 list_resize 扩容节奏。 def __init__(self) - None: self._size 0 self._capacity 0 self._store: list[Optional[T]] [] def _resize(self, capacity: int) - None: new_store: list[Optional[T]] [None] * capacity for i in range(self._size): new_store[i] self._store[i] self._store new_store self._capacity capacity def append(self, value: T) - None: if self._size self._capacity: newsize self._size 1 capacity newsize (newsize 3) (3 if newsize 9 else 6) self._resize(capacity) self._store[self._size] value self._size 1 def insert(self, index: int, value: T) - None: if index 0 or index self._size: raise IndexError(index out of range) if self._size self._capacity: newsize self._size 1 capacity newsize (newsize 3) (3 if newsize 9 else 6) self._resize(capacity) for i in range(self._size, index, -1): self._store[i] self._store[i - 1] self._store[index] value self._size 1 def __getitem__(self, index: int) - T: if index 0 or index self._size: raise IndexError(index out of range) return self._store[index] def __len__(self) - int: return self._sizeappend里只有在_size _capacity时才扩容容量计算直接复刻 CPython 的公式避免频繁触发_resize。insert先保证容量足够再从尾部往前挪元素——循环顺序必须是倒序否则后面的元素会被前面的覆盖。这两个方法写完后可以打印每次append后的_size和_capacity观察容量增长序列9 个元素以内容量按 4、7、9、10 这样的节奏走过了 9 后进入“加 1/8”的稳态。这是验证扩容策略是否正确的最直观办法比背结论有用得多。3.3 双向链表哨兵节点让插入删除不用判空动态数组的痛点是头部插入要整体挪动。双向链表用指针把元素串起来头部插入只需要改两个指针和表长无关。但直接写头插/尾插要频繁判空代码丑且容易漏。常见做法是加一对哨兵节点头尾各一个真正的数据挂在中间class _DNode: __slots__ (value, prev, next) def __init__(self, valueNone): self.value value self.prev None self.next None class DoubleLinkedList: 带头尾哨兵的双向链表插入删除无需判空。 def __init__(self): self._head _DNode() self._tail _DNode() self._head.next self._tail self._tail.prev self._head self._size 0 def _link(self, prev_node, new_node, next_node): new_node.prev prev_node new_node.next next_node prev_node.next new_node next_node.prev new_node self._size 1 def push_front(self, value): self._link(self._head, _DNode(value), self._head.next) def push_back(self, value): self._link(self._tail.prev, _DNode(value), self._tail) def remove(self, node): node.prev.next node.next node.next.prev node.prev self._size - 1 def __len__(self): return self._size哨兵的核心价值是消除边界分支push_front永远插在_head和_head.next之间即使链表为空_head.next也是_tail操作逻辑完全一致。remove只需要改相邻节点的指针不需要知道被删节点在哪。用__slots__限制节点属性同样是为了在大规模链表下控制内存。这里有一个常见的认知偏差把 Python 的collections.deque当成“链表”。实际上它是由多个块组成的双向链表每个块存一批元素兼顾了 O(1) 两端插入和缓存局部性。理解这个差异后选择结构就有依据了。操作DynamicArrayDoubleLinkedList按下标访问O(1)O(n)尾部插入摊还 O(1)O(1)头部插入O(n)O(1)中部插入/删除O(n)先找到位置再挪动O(n)找位置是瓶颈之后 O(1)额外内存有预留容量浪费每个节点多两个指针实际选型时如果场景以下标访问为主动态数组是压倒性优势如果场景是两端频繁插入删除链表或 deque 更合适。这个对比表就是项目里“分析”环节的产物——复杂度不是背出来的是推演出来的。4. 排序与搜索归并、快排和贪心的递归实现与复杂度核对这章进入算法部分。选择归并排序、快速排序和贪心算法是因为它们代表了三类最典型的算法思路分治、原地分区、贪心选择。项目里对每个算法的处理方式一致先讲设计思路再给可执行源码最后用复杂度分析核对实现是否真的达到了设计预期。4.1 归并排序递归切分与合并的代码骨架归并排序是分治思想的教科书案例。递归地把数组切成两半各自排好再合并def merge_sort(items: list[int]) - list[int]: 归并排序递归切分排好左半和右半再合并。 if len(items) 1: return items mid len(items) // 2 left merge_sort(items[:mid]) right merge_sort(items[mid:]) return _merge(left, right) def _merge(left: list[int], right: list[int]) - list[int]: 把两个有序列表合并成一个有序列表。 result: list[int] [] 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递归的基准条件是len(items) 1这是递归能停下来的保证。items[:mid]和items[mid:]每次递归都会产生新列表因此总空间复杂度是 O(n)并且每层合并都要额外开一个result。_merge里的保证了稳定性——相等元素的相对顺序在合并后不会颠倒。这个实现在数据和代码上都清晰但注意切片拷贝的成本处理超大数组时可以考虑原地归并版本代价是代码可读性明显下降通常没必要。4.2 快速排序三数取中与小区间插入排序的阈值朴素快速排序有一个著名翻车场景对已经有序的数据每次选的基准都是最大值或最小值分区极度不均递归深度变成 O(n)复杂度退化到 O(n²)。常规修复手段是两个三数取中选基准以及小区间内改用插入排序。def insertion_sort(items, left, right): for i in range(left 1, right 1): key items[i] j i - 1 while j left and items[j] key: items[j 1] items[j] j - 1 items[j 1] key def median_of_three(items, left, right): mid (left right) // 2 if items[left] items[mid]: items[left], items[mid] items[mid], items[left] if items[left] items[right]: items[left], items[right] items[right], items[left] if items[mid] items[right]: items[mid], items[right] items[right], items[mid] return mid def quicksort(items, left, right): if right - left 1: return if right - left 16: insertion_sort(items, left, right) return pivot_index median_of_three(items, left, right) pivot_value items[pivot_index] items[pivot_index], items[right] items[right], items[pivot_index] store left for i in range(left, right): if items[i] pivot_value: items[store], items[i] items[i], items[store] store 1 items[store], items[right] items[right], items[store] quicksort(items, left, store - 1) quicksort(items, store 1, right)median_of_three把左、中、右三个位置的元素排序后返回中间位置的下标这个值作为基准能有效避开“最值当基准”的最坏情况。right - left 16是小区间阈值小于等于 16 个元素时直接插入排序插入排序在小规模数据上常数极小而且局部性好比继续递归快。这个阈值不是玄学CPython 的 Timsort 里也有类似思路只是常数不同。分区用的是 Lomuto 方案逻辑简单store指针划出“已小于基准”的区域最后把基准放到它最终的位置。参数常见取值作用基准选择三数取中缓解有序输入导致的 O(n²)小区间阈值832小于阈值改用插入排序减少递归开销分区方案Lomuto / HoareLomuto 好写Hoare 交换次数少4.3 贪心算法活动选择与“按结束时间排序”的不可逆性贪心算法在面试里出现频率很高归并和快排是“先全部算完再做决定”贪心则是“每一步都选当下最优”。经典的活动选择问题是理解贪心正确性的最佳入口def activity_selection(activities): activities: 列表的 (开始, 结束)返回选中的活动下标。 ordered sorted( enumerate(activities), keylambda item: item[1][1], # 按结束时间排序 ) selected [] last_end 0 for index, (start, end) in ordered: if start last_end: selected.append(index) last_end end return selected贪心策略是“每次选结束时间最早且与已选活动不冲突的活动”。这里的排序是关键如果不按结束时间排贪心选择就无从谈起。选择一旦做出就不可逆这就是贪心和回溯、动态规划的本质区别——后者允许你后悔前者必须证明“局部最优能推导出全局最优”。活动选择问题的正确性可以用交换论证证明任何最优解里结束时间最早的活动一定可以替换进去而不减少总数量。反过来0-1 背包问题里“先选性价比最高的”就可能翻车因为物品不可分割局部最优拼不出全局最优。贪心虽然简单却是很多搜索和强化学习算法的地基组件值得花时间弄清楚它的适用边界。4.4 用 Sorter 抽象基类统一三种排序入口回到面向对象主线。归并和快排是两种不同的策略但调用方只关心“把列表排好”。用继承把这个契约固定下来class Sorter(ABC): abstractmethod def sort(self, items: list[int]) - None: 原地排序。 class MergeSorter(Sorter): def sort(self, items: list[int]) - None: items[:] merge_sort(items) class QuickSorter(Sorter): def sort(self, items: list[int]) - None: quicksort(items, 0, len(items) - 1)items[:] ...是 Python 里“原地替换列表内容”的标准写法直接赋值items ...只会改局部引用调用方拿到的还是旧列表。Sorter抽象基类再次体现了继承的复用价值外部代码只依赖sort方法要切换排序策略就替换一个对象不需要改调用逻辑。这和前面StackBase的思路完全一致——项目一直强调的“算法方法的相似之处和不同之处”就是通过这种接口统一暴露出来的。5. Python 算法实现避坑指南五个翻车现场与修复方法前四章照做下来代码大概率能跑通。但照着教程写和自己在真实数据上跑中间隔着一堆坑。这章列五个最常踩的每条按“现象 → 原因 → 解决”讲清楚。5.1 默认参数被“记住”算法函数的结果莫名叠加现象同一个函数调用两次第二次的结果里混着第一次的数据。比如写一个“把元素追加到结果列表”的函数连续调用时结果越攒越多。原因默认参数在函数定义时只求值一次。def f(x, acc[])里这个[]是同一个列表对象后续调用如果不显式传acc用的还是它。def append_result(x, acc[]): # 反例 acc.append(x) return acc print(append_result(1)) # [1] print(append_result(2)) # [1, 2] ← 不是 [2]解决默认值用None函数体内再创建新列表def append_result(x, accNone): if acc is None: acc [] acc.append(x) return acc这个坑在递归算法里尤其隐蔽因为递归调用往往不传第三个参数结果中间状态被默认参数意外共享。5.2 RecursionError归并在上万元素上直接崩溃现象本地测试 100 个元素没问题数据量涨到一万程序抛RecursionError: maximum recursion depth exceeded。原因CPython 默认递归上限是 1000 层。归并排序递归深度是 O(log n) 没问题但某些实现或快速排序退化后深度可能接近 n直接撞墙。另外即使归并深度只有约 20 层如果函数调用链上还有其他递归逻辑也可能叠加超限。解决先确认算法本身的递归深度是否可控然后按需设置import sys sys.setrecursionlimit(100_000)注意setrecursionlimit只是放宽 Python 层的限制底层 C 调用栈仍然有限设置过大的值可能导致进程直接段错误。遇到这种情况优先考虑改写为迭代版本而不是一味调大上限。5.3 子类不调 super().init()继承树上的状态静默丢失现象子类实例一调用继承来的方法就报AttributeError报错信息指向父类里明明存在的属性。原因Python 不会自动调用父类的__init__。子类如果重写了__init__又忘了super().__init__()父类里初始化的内部状态就没有建立。class BaseStack: def __init__(self): self._data [] class SubStack(BaseStack): def __init__(self): self._extra [] # 忘了 super().__init__() s SubStack() s.push(1) # AttributeError: SubStack object has no attribute _data解决在子类__init__的第一行调用super().__init__()。多继承场景下super()走的是 MRO方法解析顺序不是简单地“调用父类”所以不要用BaseStack.__init__(self)这种硬编码写法。5.4 自定义节点放进 set/dict哈希与相等性契约被破坏现象把自定义类实例放进set()做去重要么直接TypeError: unhashable type要么去重结果不符合预期。原因Python 对哈希和相等有强约定两个对象相等则哈希值必须相等。一旦你定义了__eq__Python 会把默认的__hash__置为None实例就变成不可哈希如果没定义__eq__默认哈希基于 id两个“内容相同”的节点会被当成不同对象。class Node: def __init__(self, value): self.value value def __eq__(self, other): return self.value other.value node_set {Node(1), Node(1)} # TypeError: unhashable type解决同时实现__eq__和__hash__并且哈希值必须基于参与相等比较的字段class Node: def __init__(self, value): self.value value def __eq__(self, other): if not isinstance(other, Node): return NotImplemented return self.value other.value def __hash__(self): return hash(self.value)如果节点在放进哈希表后会被修改那就不要拿可变字段做 key否则哈希值一变再也查不到原来的位置。5.5 用 list.pop(0) 当队列逻辑对但慢到怀疑人生现象用list模拟队列append入队、pop(0)出队小数据量一切正常数据量到十万级后程序明显卡顿。原因pop(0)要删除头部元素并把后面所有元素往前挪一位单次 O(n)。用列表当队列整体复杂度退化成 O(n²)。解决换collections.deque左右两端操作都是 O(1)from collections import deque queue deque() queue.append(1) # 入队 value queue.popleft() # 出队这种坑特别容易漏掉因为结果是对的只是慢。性能问题不会报错只能靠基准测试暴露。6. 验证你的数据结构实现从 unittest 到复杂度基准测试代码写完不叫完成验证才是最后一道工序。这里给两个最实用的验证手段用测试基类约束所有实现的行为用 timeit 量化复杂度。6.1 测试基类继承让每个实现都跑同一份契约前面exercise_stack是函数式验证规模大了之后不如unittest顺手。更妙的是测试类本身也可以继承——把契约测试写成基类每个实现只需要补一个工厂方法import unittest class StackContractTest(unittest.TestCase): def make_stack(self): raise NotImplementedError def test_lifo_order(self): stack self.make_stack() for v in (1, 2, 3): stack.push(v) self.assertEqual(stack.pop(), 3) self.assertEqual(stack.pop(), 2) self.assertEqual(stack.pop(), 1) def test_empty_pop_raises(self): stack self.make_stack() with self.assertRaises(IndexError): stack.pop() class TestArrayStack(StackContractTest): def make_stack(self): return ArrayStack() class TestLinkedStack(StackContractTest): def make_stack(self): return LinkedStack()StackContractTest里的测试方法写一次两个子类各只提供一个工厂方法所有断言自动对两个实现生效。后续如果新增一个DequeStack只需要再继承一次写工厂方法。这是项目里“继承最大化代码复用”思想在测试代码上的直接体现。6.2 用 timeit 量化复杂度而不是背结论复杂度分析表背得再熟也不如自己跑一组数据有说服力。下面这段基准对比list.insert(0, 1)和deque.appendleft(1)在不同长度下的耗时import timeit for n in (100, 1_000, 10_000, 100_000): setup flst list(range({n})) cost timeit.timeit(lst.insert(0, 1), setupsetup, number1000) print(flist 长度 {n}insert(0, 1) 千次耗时 {cost:.4f} 秒) for n in (100, 1_000, 10_000, 100_000): setup ffrom collections import deque; dq deque(range({n})) cost timeit.timeit(dq.appendleft(1), setupsetup, number1000) print(fdeque 长度 {n}appendleft 千次耗时 {cost:.4f} 秒)判断方法很简单数据规模翻倍耗时也近似翻倍说明是 O(n)耗时基本平稳说明是 O(1)。list.insert(0, 1)的结果会随 n 增长明显变慢而deque.appendleft(1)几乎纹丝不动。这就是把复杂度从纸面变成可观测证据的方式。我现在的个人习惯是拿到一个数据结构或算法需求先写抽象基类把契约钉死再给两个不同实现然后用测试基类跑契约最后用 timeit 验证复杂度假设。顺序可以调整但这三步一步都不能省。性能优化从来不是玄学先量化再动手结构设计也不是炫技接口清晰了后面所有实现都只是填空。希望帮到你。本文还有配套的精品资源点击获取
