简介《Python数据结构与算法》配套源码包以124个Python文件系统呈现常见抽象数据类型与算法实现适合正在学习数据结构课程、准备算法面试或希望提升Python工程落地能力的开发者。代码遵循一致的面向对象设计通过继承最大化复用清晰展示二叉搜索树、红黑树、表达式树、图、链表、位置列表、排序映射等经典结构的建模与操作同时包含欧拉遍历等算法细节可配合原书章节逐模块研读或直接运行验证。资源包仅89KB全部为.py源文件结构简洁、无冗余依赖便于导入IDE分析也契合开源共享的学习理念。目前已有729人学习下载对希望从原理迈向代码实现、以简洁可执行示例理解抽象数据类型的读者是一份高效且值得收藏的参考。 有个现象挺常见Python刷题刷到一定量人容易进入一种“能过但不懂”的状态。代码能跑时间和空间也达标但你要真问一句这个栈为什么用list实现append和pop为什么都是O(1)换成heapq之后堆内部怎么保证父节点小于子节点——很多人一下就卡住了。我最近把《data-structures-and-algorithms-in-python》这本书的源码从头过了一遍越看越觉得它不像传统教材更像一套把ADT设计、复杂度分析和可执行代码拧在一起的设计图纸。这篇博文就从源代码分析的角度挑几处最值得琢磨的实现细节拆开讲顺便说说哪些经验是文字里没写、但代码里写得很明白的。这本书最能抓住我的地方是它坚持用一致的面向对象观点组织算法代码。它不是丢给你一堆散装函数而是从抽象数据类型出发通过继承把不同结构的相似性摊开给你看在完成代码复用的同时也让栈、队列、优先队列、二叉搜索树之间的异同一目了然。下面按这个思路往下拆。1. 学数据结构绕不开“读源码”Python让这件事更容易1.1 可读性不等于可理解性源码才是最终解释Python确实是一门适合表达算法的语言循环怎么写都像伪代码list自带append、pop、index等操作字典天然就是哈希表的入门示范。但便利的另一面是很多人学数据结构时只停留在“调用层”。你知道list的append均摊是O(1)但不一定清楚它背后是动态数组扩容你知道dict的查找接近O(1)但未必想过哈希冲突和装填因子的问题。源码的作用就是把“知道”变成“看见”。这本书的写法很聪明它给每个抽象数据类型都给出完整类定义构造方法、私有成员、公开接口一目了然。我个人的阅读习惯是每读一个算法模块先不看方法主体只看__init__里初始化了什么字段。看到self._items []就知道后面要讲顺序存储看到self._root None就知道是链式节点组织看到self._top -1就知道栈是以下标方式维护的。这个习惯帮我把一整套源码快速串成了知识地图。1.2 一致的面向对象视角解决了算法书最头疼的问题很多算法书的最大缺点是章节之间彼此孤立前五章的数据结构和后五章的算法毫无联系读完全书留不下一个统一的思维框架。这本书全程坚持面向对象好处非常实在把公共行为收拢到基类。比如is_empty()、len()这些方法在代码里通常只写一遍所有子类继承即可。用类关系表达ADT关系。Stack和Queue都继承自线性集合但一个后进先出、一个先进先出代码差异被压缩到极小范围天然让人抓住相似点与分歧点。方便替换底层实现。同一个接口可以换成数组、链表甚至Python内建类型实现而调用方代码完全不用改。把算法写成类的另一个隐性好处是会逼你在动手前先做设计数据放哪、操作暴露什么、哪些字段设为私有、哪个操作决定了复杂度。这个习惯一旦养成再读别人工程代码时会顺很多。2. 抽象数据类型是地图继承是减少重复的利器2.1 定义ADT时你其实在定义三件事不少初学者听到“抽象数据类型”这个名词就绕道走其实它没那么玄乎。定义任何ADT都是在回答三个问题数据是什么支持哪些操作规则是什么拿栈来说数据是一个线性有序的元素集合操作是push、pop、peek规则是后进先出。只要满足这三个条件底层用什么存储方式都可以这就是抽象的价值。书里的代码会先让你看到“数据放在哪”然后再逐层填充方法。一个典型的线性结构基类可能是这样的class AbstractCollection: def __init__(self): self._size 0 def __len__(self): return self._size def is_empty(self): return len(self) 0 class Stack(AbstractCollection): def __init__(self): super().__init__() self._items [] def push(self, item): self._items.append(item) self._size 1 def pop(self): if self.is_empty(): raise KeyError(pop from empty stack) self._size - 1 return self._items.pop() def peek(self): if self.is_empty(): raise KeyError(peek from empty stack) return self._items[-1]这段代码的核心不是append和pop那几行而是AbstractCollection把size管理和空判断收拢到一起Stack只负责自己的数据结构。这样做的好处是当你要给所有容器增加统一日志、统一校验或统一迭代接口时只改基类就够了。这才叫代码复用而不是把几十个类写成彼此无关的复制粘贴。2.2 继承不是炫技而是让相似结构变得可直接比较很多人反对继承的原因是容易写出烂代码但在算法源码里继承的收益相当明确。Stack和Queue如果都从同一个线性集合基类派生读者会自动开始比较两者初始化几乎一样入队和出队就差在选取哪一端。一旦产生这个比较你就理解了线性ADT的本质而不是机械地背“栈是后进先出”。再看二叉搜索树它继承自二叉树代码上往往只需要重写插入和查找规则树的遍历、高度计算、删除节点等通用逻辑全部复用。这样的组织方式会让读者慢慢形成一种直觉所谓算法很多时候是在基本结构之上叠加约束条件。约束变了复杂度也变约束相同代码就能大量复用。3. 从栈到优先队列同一套基类下的三种结构推演3.1 数组栈与链式栈复杂度一样气质不一样书里清晰展现了同一个Stack接口可以用list实现也可以用单向链表实现。这两种实现的复杂度其实差不多但看到源码后你会发现它们的气质完全不同实现方式入栈出栈取栈顶额外空间适用场景基于list的动态数组均摊O(1)O(1)O(1)少量指针 预分配实现简单日常够用基于节点的单链表O(1)O(1)O(1)每元素一个节点与指针需要稳定对象引用节点复用这张表最值得琢磨的是第一行。Python的list底层是动态数组append触发扩容时要把原有元素整体搬一次严格说是O(n)但因为扩容是倍增策略平摊到每次append上仍然是O(1)这就是“均摊O(1)”含义。它解释了为什么Python内置的list在绝大多数场景下比手写链表更好用连续内存的缓存命中率高短对象遍历速度快。如果你把collections.deque也拿进来对比会看到Python标准库里的双向队列在两端都能O(1)进出。到这一步对数据结构的认识就不该再停留在“栈用数组、队列用链表”的单点匹配上而是应该形成一张更完整的图谱栈和队列本质是限制操作顺序的容器数组、链表、双向队列都是底层实现工具。3.2 优先队列的堆实现用列表画一棵完全二叉树优先队列是理解堆的最好入口。书里用二叉堆实现优先队列Python标准库heapq的思路也几乎一致。我第一次读这种实现时最惊讶的是堆完全不需要TreeNode它把一棵完全二叉树直接塞进普通列表靠下标维持父子关系——下标i的左右孩子分别是2i1和2i2父节点是(i-1)//2。def _sift_up(heap, pos): while pos 0: parent (pos - 1) // 2 if heap[parent] heap[pos]: break heap[parent], heap[pos] heap[pos], heap[parent] pos parent插入新元素时先放到列表末尾然后向上做sift_up删除堆顶时把末尾元素搬到根再向下做sift_down。两个操作都是O(log n)而且全程不需要指针只用下标移动。把这段代码和heapq对照着读你会突然理解以前看不进去的“堆化”过程到底是怎么回事。很多初学者会把堆误解成某种树形控件其实它只是“逻辑上是一棵完全二叉树、物理上是一个数组”。任务调度、TopK问题、Dijkstra算法里的优先队列本质上都是在一个数组上反复做sift_up和sift_down。书里把实现类命名为ArrayHeap而不是Heap就是在暗示这一点底层是数组逻辑是树二者靠下标公式连接。4. 排序与二分查找复杂度不是背出来的是写出来的4.1 三种排序的Python实现差异排序章节是这本书“设计和实现”价值最集中的地方。它把冒泡、插入、选择、归并、快排全部用相同风格重写了一遍对比着读特别有意思同样一份数据不同算法的循环组织方式完全不一样复杂度差异也直接体现在代码结构里。冒泡排序的经典写法长这样def bubble_sort(a): n len(a) for i in range(n - 1): swapped False for j in range(n - 1 - i): if a[j] a[j 1]: a[j], a[j 1] a[j 1], a[j] swapped True if not swapped: break return a带swapped标志位之后最好情况可以提前退出复杂度降到O(n)。插入排序则因为内层循环是“往前找位置并搬动元素”在近乎有序的数据上表现极好。快速排序用分治思维选pivot后把数组切成两段递归处理平均O(n log n)但对pivot选择很敏感。算法最好平均最坏额外空间稳定性冒泡排序O(n)O(n^2)O(n^2)O(1)稳定插入排序O(n)O(n^2)O(n^2)O(1)稳定快速排序O(n log n)O(n log n)O(n^2)O(log n)不稳定读完三份源码你会发现它们不只是三组循环而是三种不同策略相邻交换、局部搬移、分治分割。理解这一点比记住结论重要得多。4.2 二分查找的边界问题二分查找是排序之后最值得手写一遍的算法。它代码很短但特别容易在边界上翻车。书里给了递归和迭代两种版本迭代版是最实用的模板def binary_search(a, target): low, high 0, len(a) - 1 while low high: mid (low high) // 2 if a[mid] target: return mid elif a[mid] target: low mid 1 else: high mid - 1 return -1这里有几个容易踩的坑while条件是low high不是low highmid更新后必须写low mid 1或high mid - 1不能写low mid否则最后两个元素会死循环起始high是len(a)-1而不是len(a)配合闭区间写法才不容易越界。复杂度推理很简单每次比较都能把搜索区间砍半最好O(1)最坏O(log n)。把这个推导想透之后再回头理解平衡二叉树为什么要求左右子树高度差不超1你会更清楚树高就是搜索路径长度一旦退化O(log n)就会掉成O(n)。5. 贪心算法正确性证明往往藏在实现之外5.1 活动选择问题源码拆解数据结构章节通常用贪心算法做收尾因为它很考验“设计算法”的能力。经典的活动选择问题核心是先按结束时间排序再依次选择不冲突的活动def activity_selection(starts, finishes): n len(starts) activities sorted(zip(starts, finishes), keylambda x: x[1]) selected [] last_finish float(-inf) for start, finish in activities: if start last_finish: selected.append((start, finish)) last_finish finish return selected代码只有六七行但包含两个重要设计。一是排序预处理贪心选择建立在“有序”的基础上排序本身就是把问题的优先级显式化。二是不回退线性扫描一旦选中某个活动就永远不回头。我第一次看这段源码时没反应过来后来才发现排序键本身就是贪心策略的一部分。如果按开始时间排序这个算法就是错的只有按结束时间排序才能保证每次选出的活动给后续留下最大余量。所以看书时不能只背代码顺序还要问一句为什么这里要这样排序很多算法决策都藏在这种不起眼的细节里。5.2 什么情况下不能贪心换一个约束就翻车更有价值的分析是把同样的问题换一个约束贪心策略会立刻失效。最典型的是0-1背包问题。如果只按单位价值从高到低取物品可能因为剩余容量的碎片化而得不到最优解。但如果物品可以分割问题就变成分数背包按单位价值贪心立即可用。两者只差“是否可分”一个属性却是两种完全不同的算法场景。我在实践里会先用两步检查判断能不能贪心第一每个子问题的最优解是不是能独立选出不需要回退第二选了局部最优之后剩余问题是否保持与原问题相同的结构。活动选择满足这两条0-1背包不满足因为放入某件物品会改变剩余空间结构后续决策不再是独立子问题。这个判定过程比记住任何算法模板都重要。6. 把源码一行行敲过之后我记住的三条经验6.1 没有断言保护的算法代码不值得信任书中很多测试代码都用了assert。后来我在自己写算法练习时也养成习惯在每个ADT的公开方法入口先想清楚前置条件再决定用assert兜底还是用显式raise拦住非法操作。比如栈的pop对空栈抛KeyError比返回None安全得多二分查找对传入数组先做类型和有序性校验能在源头上减少很多诡异bug。我在重写栈和队列时特意把pop、dequeue的空容器情况全部补齐了异常处理结果写二叉搜索树删除时很多边缘情况不用再猜直接看异常信息就定位了。断言和异常是写给未来调试的人看的包括三个月后的自己。6.2 复杂度表只能当参考实测才能定结论读完源码之后我做了个小实验分别用list、deque和自写链表队列执行100万次入队出队。复杂度表上说三种实现的入队出队都是O(1)但实际耗时list最慢、deque最快、链表居中。原因是内存局部性、动态扩容和Python对象分配开销叠加起来比纸面上的渐近复杂度影响更大。复杂度和实测有差别不是因为复杂度理论错了而是渐近记号描述的是规模趋近无穷时的增长趋势常数项、内存布局、对象头开销都被省略了。所以我现在的方法是先读源码理解复杂度推导再用timeit做基准测试两者结合才是完整的数据结构分析。6.3 面向对象不是最终目标接口稳定才是书里用继承组织了大量代码但重写几遍之后我发现继承层级不是越深越好。如果你只是想复用is_empty、__len__这类方法用Python的鸭子类型也能达到类似效果语言本身并不强制你构建复杂的类树。真正有价值的是先把公开接口定义稳定push/pop/peek是什么语义insert/search/delete怎么约定然后才考虑代码怎么复用。这本书的真正用意不是让所有代码都套进同一个类家族而是用继承来帮助你观察相似结构、看清差异约束。把这句话想通才算真正读懂了整本源码。本文还有配套的精品资源点击获取