简介Python数据结构和算法开源学习包面向渴望深入理解数据结构与算法底层实现的Python开发者适合作为算法入门和进阶的伴读资料。资源以简洁可读的Python源码为主体通过继承等面向对象技巧统一多类抽象数据类型与算法既强调代码复用也便于对照比较不同实现的异同。压缩包内共一百二十四个文件除一个gitignore外全部为.py源码文件包体仅八十九千字节目录简洁轻量。源码覆盖二叉搜索树、链表二叉树、图、树、排序表映射、欧拉遍历、位置链表、表达式树以及红黑树等经典主题每份代码结构清晰均可独立运行便于调试观察。已有七百三十二人学习下载适合配合算法课程进行课后练习也可作为面试手写代码、考前突击的实用参考直接运行脚本就能看到数据结构如何生长、旋转或搜索快速内化原理。1. 从“Python 中的数据结构和算法”这套源码说起它到底在教什么如果你跟我一样先被严蔚敏那本 C 语言版数据结构虐过一遍再转过来写 Python大概率会撞上同一个尴尬python 入门教程看了一堆刷题网站也刷了但真要自己动手实现一个栈、一棵树、一个图脑子里还是 C 语言那套指针和结构体。搜“python 数据结构与算法”出来的要么是 LeetCode 题解要么是把 C 代码生硬翻成 Python 的零散片段根本看不出设计意图。这个标题指向的项目我做了一个比较完整的通读它把数据结构与算法全部用 Python 重新实现而且从头到尾强调面向对象——用继承来组织抽象数据类型ADT让接口和实现分离代码能直接执行。书名后挂的“Python source code analysis”按我的理解不是去剖析 Python 解释器而是把这些数据结构的 Python 源码逐段拆开讲。换句话说它解决的是“看得懂算法思路、写不出 Python 实现”的断层。适合三类人刚入门 Python 想补算法课的学生、准备数据结构与算法面试的求职者、以及写业务代码想提升抽象能力的工程师。我这边按它的思路把整条落地路径拆成六步先讲为什么用继承组织数据再手写核心结构与排序然后用 timeit 验证复杂度最后给出一套排查和对照验证的方法。每一步都有能直接抄的代码。2. 面向对象视角的数据结构设计为什么继承是这套源码的主线2.1 ADT 与具体实现分离先定接口再谈实现数据结构教科书都会先讲 ADT抽象数据类型但 C 语言讲 ADT 靠的是函数指针和结构体绕得很。Python 里表达 ADT 最自然的方式就是类而这个项目比一般教程多做了一件事它先把数据结构的公共行为定义成父类接口再让数组实现、链表实现去继承和覆写。这样做的好处是算法层只依赖接口不关心底下存的是数组还是链表。看标题里“设计、分析和实现”这三个词设计排在最前头。接口先行就是这个“设计”的核心。我一般会用 Python 自带的 abc 模块把接口钉死让子类漏实现方法时在实例化阶段直接报错而不是运行到一半才炸from abc import ABC, abstractmethod class Bag(ABC): abstractmethod def add(self, item): 向集合中添加一个元素 abstractmethod def remove(self, item): 从集合中移除一个元素不存在时抛 ValueError abstractmethod def __len__(self): 返回集合元素个数 abstractmethod def __iter__(self): 返回迭代器支持 for item in bag 遍历这里的len不是可有可无的Python 里对象的布尔值会回退到len所以实现了它if not bag 这种判断就能直接工作。iter是容器协议的关键后面所有算法遍历集合都靠它。把这两个方法钉在接口里等于强制所有实现类都满足 Python 的容器协议后续写遍历逻辑时不用关心具体类型。2.2 从基类到子类数组实现的 Bag 怎么落地接口定义好之后第一个实现我选数组版本因为 Python 的 list 就是动态数组逻辑最直白。注意一个细节add 用 append 是摊还 O(1)remove 我选择先定位再弹出避免一次 remove 内部又做一遍线性查找class ArrayBag(Bag): def __init__(self): self._items [] def add(self, item): self._items.append(item) def remove(self, item): for i, value in enumerate(self._items): if value item: self._items.pop(i) return raise ValueError(item not in bag) def __len__(self): return len(self._items) def __iter__(self): return iter(self._items)几个值得说清的点。第一为什么用 enumerate 而不是 index() 加 pop()index() 本身又是一次 O(n) 扫描等于一次删除做了两遍遍历enumerate 在同一个循环里完成定位和弹出省一遍。第二为什么 pop(i) 而不是 remove(item)remove 内部同样要遍历查找而且它是从头部开始找第一个匹配行为上跟这里一样但因为你已经定位到了下标直接用下标 pop 是确定性的。第三_items 前面的下划线是这本书一贯的约定它告诉调用者这是私有属性别在外面直接改要改就通过公开方法。2.3 继承复用逻辑一个 UniqueBag 讲清多态面向对象的最直观价值在于父类已经把 remove、len、iter都实现好了子类只需要覆写自己不同的那一个方法剩下的全部复用。我用一个不重复集合的案例来验证这条链路是否真的通class UniqueBag(ArrayBag): def add(self, item): if item not in self: super().add(item)这个类只有 add 一个方法remove 和遍历全是继承来的。in 操作会触发containsArrayBag 没实现它所以 Python 回退到iter做线性扫描。对于教学代码这个复杂度能接受如果你真要在大数据量下用 UniqueBag把内部存储换成 set 再重写 add 就行调用方代码一行都不用改——这就是接口与实现分离的红利。跑一下验证bag UniqueBag() bag.add(1) bag.add(1) bag.add(2) print(len(bag)) # 输出 2而不是 3 print(list(bag)) # 输出 [1, 2]这里要提醒的是super().add(item) 必须调用否则这个覆写就变成了完全替换父类里 append 的逻辑就丢了。Python 的 super() 不是 C 那种机械的“调用父类同名函数”它是沿着 MRO方法解析顺序找下一个实现这在多继承场景下尤其关键写的时候心里要有这根弦。2.4 从源码分析里学到的三个习惯把标题里“Python source code analysis”落到实处我读完这套设计之后最大的收获不是某个算法怎么写而是三个写代码的习惯。第一个文件组织按 ADT 分模块。一个抽象数据类型一个模块抽象基类放上层包具体实现当下层包。这样新加一种实现不用改调用方代码加一个文件就完事。第二个命名约定非常克制私有属性一律 _ 开头内部节点类叫 _Node外部不可见。这个习惯能防住大量随手 .next 乱改结构的低级错误。第三个几乎所有的遍历都走iter算法层不直接操作下标或指针。很多 python 爬虫工程里数据清洗代码写得乱本质就是到处直接操作内部结构缺少这一层封装。这套设计思路学下来你再去看别的 Python 源码会习惯性先画类图再读方法而不是一头扎进函数堆里。3. 用 Python 实现核心数据结构与排序算法可直接运行的代码片段3.1 单链表无头结点版本的两个边界条件链表是理解指针和递归的基础Python 里没有指针但可以用嵌套引用模拟。这个项目里的链表实现通常会有一个内部 _Node 类存值和 next 引用。我给的版本不带头结点代码更短但边界条件也更阴险class LinkedList: class _Node: def __init__(self, value, next_nodeNone): self.value value self.next next_node def __init__(self): self._head None self._size 0 def _node_at(self, index): cur self._head for _ in range(index): cur cur.next return cur def insert(self, index, value): if index 0 or index self._size: raise IndexError(index out of range) if index 0: self._head self._Node(value, self._head) else: prev self._node_at(index - 1) prev.next self._Node(value, prev.next) self._size 1 def remove(self, value): prev, cur None, self._head while cur is not None: if cur.value value: if prev is None: self._head cur.next else: prev.next cur.next self._size - 1 return prev, cur cur, cur.next raise ValueError(value not in linked list)不带头结点的写法第一个坑在 insert(0, ...) 必须单独处理 head 的更新否则新节点丢失。第二个坑在 remove 删除头结点时prev 是 None不能走 prev.next cur.next 这条分支。教科书里加一个不存数据的哨兵头结点就是为了把这两个分支统一成一种写法但我建议初学阶段先写无头结点版本因为它逼你直面边界条件这个能力在刷 python 算法题时特别值钱。_node_at 是 O(n) 的所以 insert 在任意位置是 O(n)这是链表和数组的根本差异。如果你追求 O(1) 插入那需要同时持有前驱节点引用典型场景是 LRU 缓存里的双向链表。3.2 队列为什么 list.pop(0) 是一个假 O(1)栈用 list 就能很好实现append 和 pop() 都是尾部操作摊还 O(1)。队列不行因为先进先出要求从头部弹出list.pop(0) 会把后面所有元素前移一位单次 O(n)。很多老教程拿 list 实现队列数据量小感觉不出来一上生产就翻车。这个项目里队列的默认实现应该用 collections.deque它是双向队列头尾操作都是 O(1)from collections import deque class Queue: def __init__(self): self._items deque() def enqueue(self, item): self._items.append(item) def dequeue(self): if not self._items: raise IndexError(dequeue from empty queue) return self._items.popleft() def __len__(self): return len(self._items)注意 dequeue 前先判空Python 里空 deque 的布尔值是 False直接 if not self._items 就能用。deque 的 popleft() 是 O(1)这是它和 list 最本质的区别。如果你要实现优先队列那 deque 也不够用得用 heapq 模块或者自己实现二叉堆这个项目里堆排序和优先队列是单独成章的我后面在复杂度验证部分会讲怎么看它们的时间表现。3.3 归并排序与快速排序递归写法和 pivot 选择排序是数据结构与算法里最值得手写一遍的内容。归并排序的思路稳定分到不能再分然后两两合并。Python 写递归版非常简洁但要注意切片 a[:mid] 会复制数组所以这个版本的空间复杂度是 O(n)不是教科书说的 O(1) 原地def merge_sort(a): if len(a) 1: return a mid len(a) // 2 left merge_sort(a[:mid]) right merge_sort(a[mid:]) i j 0 result [] 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这里一定要用 而不是 否则两个相等的元素会来回交换虽然结果还是有序但破坏了稳定性。归并排序的稳定性来自合并时相等元素先取左半部分这个细节在面试里常考。快速排序的难点在 partition 和 pivot 的选择。最朴素的写法永远取最后一个元素当 pivot遇到已经有序的数组会退化成 O(n^2)。三数取中是工程上最常用的改良取首、中、尾三个元素的中位数当 pivotdef quick_sort(a, low0, highNone): if high is None: high len(a) - 1 if low high: return pivot_index partition(a, low, high) quick_sort(a, low, pivot_index - 1) quick_sort(a, pivot_index 1, high) def partition(a, low, high): mid (low high) // 2 pivot sorted([a[low], a[mid], a[high]])[1] pivot_index a.index(pivot, low, high 1) a[pivot_index], a[high] a[high], a[pivot_index] i low - 1 for j in range(low, high): if a[j] pivot: i 1 a[i], a[j] a[j], a[i] a[i 1], a[high] a[high], a[i 1] return i 1partition 里有个细节把 pivot 先换到 high 位置然后遍历 [low, high-1]所有 pivot 的值换到左边最后把 pivot 放到 i1 这个分界点。循环里 j 不能取到 high因为 high 位置是 pivot 本身拿它跟自己比没有意义。三数取中解决的是有序数组的退化问题但还有一个极端场景数组里全是同一个数。这时 partition 每次都会把整个数组分成一边空一边全递归深度变成 n直接击穿 Python 默认的递归上限。要处理这种情况得用三路快排把等于 pivot 的元素单独放中间一块。这也是为什么我后面会专门讲递归深度排查。3.4 KMP 字符串匹配前缀函数是核心字符串匹配是数据结构里的常客。暴力匹配在文本串长度 n、模式串长度 m 时是 O(n*m)KMP 能压到 O(nm)。KMP 的核心是 next 数组也叫前缀函数它记录模式串每个位置之前的子串中最长的相等前后缀长度。这个数组让文本串指针永远不回退def build_next(pattern): next_arr [0] * len(pattern) for i in range(1, len(pattern)): j next_arr[i - 1] while j 0 and pattern[i] ! pattern[j]: j next_arr[j - 1] if pattern[i] pattern[j]: j 1 next_arr[i] j return next_arr def kmp_match(text, pattern): if not pattern: return 0 next_arr build_next(pattern) j 0 for i, ch in enumerate(text): while j 0 and ch ! pattern[j]: j next_arr[j - 1] if ch pattern[j]: j 1 if j len(pattern): return i - j 1 return -1这个 next 数组的定义是常见的一种next[i] 表示 pattern[:i1] 中前缀等于后缀的最大长度next[0] 恒为 0。构建时的 while 循环是 KMP 最容易写错的地方它的含义是当前后缀匹配不上时回退到更短的前缀继续尝试。这里回退目标是 next[j-1]而不是 j-1原因在于你已经知道 pattern[:j] 的后缀和前缀是同一个串直接用它的最长前后缀长度跳转能省掉无效比较。验证一下kmp_match(ababac, bac) 返回 3kmp_match(hello, ll) 返回 2模式串为空时返回 0。3.5 图的邻接表与 BFSvisited 是关键图的存储最常见的是邻接表Python 里用字典套列表最顺手键是节点值是这个节点能到达的邻居列表。BFS 用队列DFS 用栈或递归我给一个 BFS 模板from collections import deque def bfs(graph, start): visited {start} queue deque([start]) path [] while queue: node queue.popleft() path.append(node) for neighbor in graph.get(node, []): if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) return pathvisited 集合是整个 BFS 不出死循环的命根子。没有它图里有环时你会无限重复入队同一个节点。graph.get(node, []) 这个写法要留意如果 node 不存在于字典中返回空列表而不是抛 KeyError避免了链式访问时的类型错误。这个模板能直接用在 python 爬虫的链接去重场景里把每个页面当成节点页面里的外链当成邻居visited 保证同一个 URL 不会被抓两遍。数据结构和业务代码之间的边界其实没有你想的那么远。4. 把算法分析落到执行时间上用 timeit 验证复杂度结论4.1 先看 Python 容器隐藏的复杂度表分析算法的第一步是背熟 Python 内置容器的操作复杂度这是后面所有结论的地基。很多复杂度结论只看教科书是没感觉的比如 list 的 pop(0) 到底是 O(n) 还是 O(1)写代码的人心里要有数。我常用这张表建议你把它存下来操作listdequedict / set尾部插入/删除摊还 O(1)摊还 O(1)—头部插入/删除O(n)O(1)—随机访问 a[i]O(1)O(n)O(1) 按键成员判断 item in containerO(n)O(n)平均 O(1)遍历全部元素O(n)O(n)O(n)这个表里最容易出问题的两行一是 list 头部操作二是 dict 的成员判断。很多 python 数据分析脚本在处理百万级数据时慢到怀疑人生原因往往就是在一个大数据量的 list 里反复用 in 做成员判断O(n) 乘上 n 次调用直接变成 O(n^2)。同样的逻辑换成 set立刻变成摊还 O(1)。4.2 用 timeit 量化 list 和 deque 的头部操作差距光背结论不算数我习惯用 timeit 把差距量出来。timeit 模块会自动处理垃圾回收和重复计时比手动 time.time() 靠谱得多。下面这段对比 list.pop(0) 和 deque.popleft()数据规模 10000、重复 2000 次import timeit setup from collections import deque; l list(range(10000)); d deque(range(10000)) list_time timeit.timeit(l.pop(0), setupsetup, number2000) deque_time timeit.timeit(d.popleft(), setupsetup, number2000) print(flist.pop(0): {list_time:.4f} s) print(fdeque.popleft: {deque_time:.4f} s)在主流机器上list 的耗时通常是 deque 的几十倍到上百倍而且差距会随着数据规模线性拉大。number 参数是重复次数设太小抖动大设太大浪费时间2000 到 5000 之间比较平衡。timeit 的 setup 参数只在进程初始化时执行一次真正的计时不包含 setup 的构造开销这是它能测得准的关键原理。如果你想测一个函数整体耗时把它放进 setup 之外直接用 timeit.timeit(lambda: my_func()) 也是可以的。4.3 验证归并、快排、堆排序的增长趋势复杂度的“理论值”和“实测值”能不能对上我建议自己做一次规模扫描。下面这个测量函数自动生成随机数组记录排序耗时你可以拿它对比归并排序、快排和内置 sortedimport random import time def measure(func, size): data [random.randint(0, 10000) for _ in range(size)] t0 time.perf_counter() func(data) return time.perf_counter() - t0 for size in [1000, 2000, 4000, 8000]: t measure(sorted, size) print(fsize {size:5d} sorted() 耗时 {t:.4f} s)注意 measure 接收的 func 必须能原地处理列表或者返回新列表。内置 sorted 返回新列表而你自己的 quick_sort 是原地修改传参时要传 data.copy() 而不是 data 本身否则第二次测量时数据已经有序测出来的是最好情况不是平均情况。试完以后你会看到规模从 1000 加到 8000也就是数据量变成 8 倍O(n log n) 的排序耗时大约只增长 10 到 12 倍而如果某个排序实现是 O(n^2)耗时会长 64 倍。这个 64 倍和 12 倍的差别就是你判断一个算法复杂度有没有写错的依据。4.4 空间复杂度与 Python 内存的模糊地带算法分析的另一个维度是空间。这里有一个 Python 特有的坑列表里存的是对象的引用不是对象本身。list(range(10000)) 在 64 位 Python 里列表本身是 8 万字节的指针数组但每个整数对象还占 28 字节一万个整数对象近 28 万字节总共 36 万字节上下。如果你只是用数组存一百万个数实际内存开销可能是你预期的三四倍。所以评估空间复杂度时除了算法本身的辅助空间还要把 Python 对象头开销算进去。归并排序的切片版本是 O(n) 辅助空间但每个切片里都是引用真正的对象没有被复制如果你用 deepcopy 复制整个数组那才是真正的 O(n) 对象复制内存直接翻倍。分析空间复杂度时先问自己一句我在复制引用还是复制对象本身这两个情况的真实内存差一个数量级。5. 源码级实现避坑指南写 Python 数据结构与算法时的几个典型翻车现场5.1 可变默认参数两个实例共享了同一个 list现象定义 ArrayBag 时用 definit(self, items[])然后创建两个 Bag 实例往第一个里加元素第二个居然也有。原因Python 的函数默认参数在定义时只求值一次可变的列表对象被所有没传 items 的实例共享。这是 Python 入门阶段最经典的陷阱之一但在写数据结构代码时尤其危险因为你天天在跟容器打交道。解决默认参数一律写 None在函数体内新建对象。class ArrayBag: def __init__(self, itemsNone): self._items [] if items is None else list(items)注意这里用了 list(items) 而不是直接 self._items items。直接赋值会让两个 Bag 共享同一个外部列表外部一改Bag 跟着变用 list() 构造一份拷贝隔离外界。5.2 用 list 当队列数据量上去后性能断崖现象自己实现一个队列类内部用 list 存数据enqueue 用 append、dequeue 用 pop(0)。单元测试数据量小跑得飞起一放到 python 爬虫里抓几万个 URL速度突然慢到没法看。原因list.pop(0) 每次把头部元素弹出后后面所有元素都要前移一位单次 O(n)。数据量小时 n 只有几十察觉不到当 n 到几万甚至几十万每次出队都是几万次内存搬移累积成 O(n^2)。解决内部存储换成 collections.deque用 popleft() 出队。判断一个实现是不是有这个问题看数据量翻倍后耗时是否近似变成原来的四倍如果是基本可以断定哪一步操作退化成了 O(n)。5.3 递归深度击穿 Python 默认栈限制现象自己实现的快速排序或二叉搜索树插入数据量到十万左右时抛出 RecursionError: maximum recursion depth exceeded。归并排序不会因为它的递归深度恒为 log2(n)但快排在最坏情况下递归深度能达到 n。原因Python 默认递归上限约 1000 层。快速排序如果 pivot 选择不好比如每次都选到当前区间的最小值或最大值递归深度会拉满到 n。三数取中能把这种情况压制到很少见但全等元素数组依然能触发。解决先调高递归上限再考虑改迭代。import sys sys.setrecursionlimit(1000000)注意 sys.setrecursionlimit 不是无限后悔药。调太高会让 C 语言栈先于 Python 递归限制耗尽程序直接段错误Segmentation Fault连异常都不给你抛。我的习惯是算法课的作业和本地实验可以调高到默认值的上百倍但生产环境绝不依赖递归深度大的算法该改迭代就改迭代该用内置函数就用内置函数。5.4 深拷贝把链表复制出一堆共享节点现象用 copy.deepcopy 复制一个链表实例然后修改副本里的某一个节点值原链表也跟着变了或者复制直接报 RecursionError。原因链表节点对象存在循环引用或重复引用。deepcopy 会逐个对象复制遇到循环引用时虽然它有记忆机制能处理环但遇到节点被多处引用的复杂结构时结果可能不是你预期的深拷贝语义浅拷贝更直接只复制了头节点的引用两个链表共享同一串节点。解决对链表、树这种有内部链接的结构自己写迭代式复制方法不要依赖 deepcopy。def copy_list(self): new_head None tail None cur self._head while cur is not None: new_node LinkedList._Node(cur.value) if new_head is None: new_head new_node tail new_node else: tail.next new_node tail new_node cur cur.next result LinkedList() result._head new_head result._size self._size return result这个写法核心是维护一个 tail 指针让新链表的构建是迭代的内存占用 O(n) 且不会引入任何共享引用。5.5 自定义对象比较接口缺失导致排序报错现象定义了一个 Student 类放进列表里跑 sorted()Python 直接抛 TypeError: not supported between instances of Student and Student。原因sorted() 默认用 运算符比较元素你的类没有实现比较方法。解决实现lt方法这是让对象可排序的最小接口。只实现lt就够 sorted 用但如果你还想要全比较运算符可以加 functools.total_ordering 装饰器自动补全。from functools import total_ordering total_ordering class Student: def __init__(self, name, score): self.name name self.score score def __lt__(self, other): return self.score other.score def __eq__(self, other): return self.score other.score加 total_ordering 装饰器后只要实现lt和eq、、 都会自动推导出来。排序场景还有一个更灵活的方案sorted(students, keylambda s: s.score)不修改类定义直接指定排序键这在对象来自第三方库时是唯一出路。6. 验证你的实现用随机样本加暴力法做对照测试最后一公里不是性能是正确性。我所有自己写的数据结构实现都要过一个随机对照测试拿你的实现和 Python 内置的、或者一个写得很慢但绝对正确的暴力解法对拍。暴力法写错了还能靠人工检查救回来你的实现就算错了也能通过输入输出差异快速定位。下面是一个排序算法的正确性验证函数import random def check_sort(func, size50, rounds200): for _ in range(rounds): data [random.randint(-1000, 1000) for _ in range(size)] expected sorted(data) got func(data.copy()) if got ! expected: return False, data, expected, got return True, None, None, None ok, data, expected, got check_sort(quick_sort) if not ok: print(出错了) print(原数据: , data) print(预期结果:, expected) print(实际结果:, got) else: print(200 轮随机数据全部通过)这里 data.copy() 是必须的因为原地排序会修改传入的列表不复制的话第二轮测试的数据就全是排好序的测不出问题。rounds 设 200、size 设 50单次运行不到一秒但已经能覆盖绝大多数边界情况。你别只跑有序数据和随机数据还要手动补几个极端用例空列表、单元素、全相等、倒序数组。全相等数组能快速暴露快排死循环的问题——如果每次 partition 都把数组切成一边空一边全递归深度直接爆掉。这套随机对照方法不仅适用于排序任何数据结构实现都能套写一个栈就生成随机 push/pop 序列跟 list 模拟的结果对拍写一个图遍历就用小图手工画一遍预期路径再对比输出。正确性验证挂在手边以后改成更快的版本、调参调边界永远有一条退路。我现在拿到一个新算法第一件事是写暴力对照测试先保证对再谈快。这个习惯是读这类源码书培养出来的我建议你也保持住。希望帮到你。本文还有配套的精品资源点击获取
