简介这份开源资源是《Python 中的数据结构和算法》一书的完整配套源码面向想系统掌握数据结构设计、算法复杂度分析与Python实现的开发者、考研与面试备考生及高校教学人员。资源共124个文件以123个.py源文件为主体另有.gitignore工程配置压缩包约89KB。源码按教材章节组织覆盖二叉搜索树、红黑树、链式二叉树、图、树、有序表映射、欧拉游走、位置列表、表达式树等经典抽象数据类型与算法用简洁可执行的Python代码展示设计、分析与实现过程并通过继承保持统一的面向对象视角便于对照教材逐模块运行、调试和扩展。已有732人下载学习适合用于课程实验、源码精读或面试前的算法快速复盘。1. 数据结构和算法 Python 版一套能直接跑起来的完整源码包数据结构和算法在 Python 里的实现不缺片段式教程缺的是能当工程代码直接读的完整源码包。这套资源按章节收齐了动态数组、链表、栈队列、树、堆、图和排序的源码每份都带类定义、继承关系和复杂度标注不是给背答案的是拆开看内部逻辑的。我拆第一遍最大的意外几乎不用装第三方库全部基于 Python 标准库配好环境就能跑。它同时服务两类人——刚入门想真正读懂数据结构的初学者和准备面试、要把经典结构封装成可复用类的中级开发者。如果你要的不是「看懂思路就行」而是亲手把每个抽象数据类型实现一遍、看清不同存储方式的性能差异这套源码就很合适。它整本贯穿面向对象视角继承与封装不是装饰是服务代码复用的设计骨架。2. 面向对象与继承ADT 契约、代码复用与源码阅读顺序很多人在刷题网站上看数据结构题解习惯了「一个函数写完所有逻辑」真到要把一个容器类放进工程里时反而没概念方法从哪几个入手内部状态怎么藏为什么同一套接口要写两个类这套源码的第一个价值就是正面回答这三个问题。它把数据结构当成产品来做而不是当成题来做。2.1 为什么数据结构要用面向对象实现ADT 和类的映射关系先讲抽象数据类型ADT。栈、队列、优先队列本质是一份「操作契约」push 放进去、pop 取出来、top 看一眼仅此而已。契约里不规定你用数组还是链表还是别的存储方式。面向对象恰好天生匹配这个分层——基类写契约子类写存储细节调用方拿着契约编程运行时才看到具体实现这就是多态。这套源码里几乎每个结构都有这一步。用 StackBase 撑住接口再让 ArrayStack 和 LinkedStack 各自实现调用方只依赖 StackBase。代码里用 NotImplementedError 标记「这个方法是契约不在这里实现」是 Python 里很常见的做法。# stack_base.py —— 只定义契约不写实现 class StackBase: 栈的 ADT 定义子类必须实现这些方法。 def push(self, e): raise NotImplementedError(由子类决定存储方式) def pop(self): raise NotImplementedError def top(self): raise NotImplementedError def __len__(self): raise NotImplementedError def is_empty(self): raise NotImplementedError逻辑说明五个方法的签名全部写死却不碰任何存储字段。这意味着任何实现了这五个方法的类在调用方眼里都是「能用的栈」这就是抽象带来的替换性。参数说明e 是待入栈元素类型不做限制Python 容器天然支持任意对象is_empty 单独列出来是为了让调用方避免用 len()0 做判断时频繁触碰实现细节。2.2 继承在这里不是炫技基类抽公共行为子类只写差异这套源码用了大量继承但它的继承不是为了显得面向对象而写的。以队列族为例数组队列的顺序存储、链式队列的节点存储增删语义完全一样唯独「元素存在哪」不同。把公共的 is_empty、len、异常检查放基类子类只需要实现真正的存和取。同样的模式在树章节更明显通用树先给出 children、is_root、depth 这些公共方法二叉树在它之上只补 left_child、right_child 两个语义查找树再往下覆写插入删除。每一层继承只增加「这一层该有的约束」不加多余东西。这种写法最大的好处是改 bug 只改一处多个实现类同时受益。具体到 Python 语法这三点值得在源码里对照着确认用 super() 调用父类构造器保证父子两层的初始化都执行子类只覆写需要差异的方法其余方法原样继承多个异构实现共享同一个基类接口测试里可以互相替换# queue_demo.py —— 「契约继承」的最简结构 class QueueBase: def __init__(self): self._size 0 def __len__(self): return self._size def is_empty(self): return self._size 0 class ArrayQueue(QueueBase): def __init__(self): super().__init__() # 先初始化基类的 _size self._data [] def enqueue(self, e): self._data.append(e) self._size 1 def dequeue(self): if self.is_empty(): raise IndexError(dequeue from empty queue) ans self._data.pop(0) # 注意这里是 pop(0)后面细讲它的问题 self._size - 1 return ans逻辑说明ArrayQueue 没有重写len和 is_empty直接复用基类_size 的维护全在基类字段里子类只需要在增删时正确加减计数。参数说明super().init() 不能省否则基类的 _size 不会初始化is_empty 直接抛 AttributeError。enqueue 的 append 是摊销 O(1)dequeue 的 pop(0) 是 O(n)——这个矛盾正是链式队列存在的理由取舍细节放避坑章讲。2.3 源码包怎么组织按章节读先基类再实现的顺序整套源码按书的章节组织每个数据结构一个独立 .py 文件文件名基本对上结构名。我拆包第一遍捋出的文件对照表大致是这样章节主题对应文件阅读重点栈与队列stack 系列、queue 系列同一契约下的数组/链表两个实现列表与序列动态数组、链表类扩容逻辑、getitem、迭代器树tree、binary_tree、search_tree遍历方法在基类汇总子类只加约束优先队列priority_queue、heap 系列上滤下滤、数组下标映射图graph、邻接表实现顶点边建模、DFS/BFS 的共同骨架排序与查找各排序算法文件比较器参数、原地与非原地差异如果你上手想尽快有获得感我建议的顺序先读基类文件把契约看清楚再读一个和内置类型相近的实现比如数组栈因为你能直接靠直觉验证对错然后读对应的链表实现重点对比每个方法的时间复杂度标注。顺序对了后面树和图根本不用换思路同一套「基类契约 子类差异」往里套就行。3. 动态数组、链表和迭代器容器源码的核心实现与选型参数这一章把源码里最基础的三个点单独拆开动态数组的扩容、链表的节点与迭代器、两种存储的选型判断。这三个点几乎是后面所有数据结构的地基源码里很多不起眼的细节扩容因子是多少、节点类要不要slots、迭代器怎么指向下一个节点都值得逐一确认。3.1 动态数组的扩容逻辑为什么 append 是摊销 O(1)别把 Python 内置 list 当黑匣子它底层是动态数组一块连续内存 已用元素个数 容量上限。当已用个数逼近容量时必须申请更大的内存、把旧元素全部搬过去。这套源码提供了一份用 Python 重写的动态数组实现把解释器内部动作放到了明面上读它比啃 C 源码容易得多。# dynamic_array.py —— 模拟 list 的几何扩容策略 class DynamicArray: def __init__(self): self._data [None] * 1 # 初始容量 1 self._n 0 # 已用元素数 def __len__(self): return self._n def _resize(self, cap): new_data [None] * cap for i in range(self._n): new_data[i] self._data[i] self._data new_data def append(self, e): if self._n len(self._data): self._resize(2 * len(self._data)) # 容量翻倍几何增长 self._data[self._n] e self._n 1 def __getitem__(self, i): if 0 i self._n: return self._data[i] raise IndexError(index out of range)逻辑说明核心在 append 的触发条件——只有 _n 等于当前容量才扩容容量从 1 变成 2、4、8、16。每一次扩容是 O(n) 的搬运成本但因为容量翻倍扩容发生得越来越稀疏把总成本摊到每次 append 上就是常数级。参数说明2 这个扩容因子是关键参数翻倍对应几何增长摊销复杂度 O(1)如果改成固定加 1 的算术增长摊销复杂度立刻退化到 O(n)。getitem让自定义类支持下标访问这是 Python 容器约定的一部分。提示读到树、堆这类依赖数组下标的实现时可以回来看这份动态数组它的下标映射逻辑是后面所有「数组存储树结构」的公共底座。3.2 链表实现的内存控制_Node、slots与迭代器链表实现里最容易写飞的两处是节点类和迭代器。节点类如果放任不管Python 会为每个实例保留dict字典存属性链表几万个节点内存开销立刻失控。这套源码里节点类普遍用slots声明属性白名单省掉dict代价是不能随意给实例挂新属性数据结构场景里这反而是好事。谁都见过这个技巧但真到自己写时总忘写完才发现内存涨得离谱。# linked_stack.py —— 链表栈的核心结构 class LinkedStack: class _Node: __slots__ (_element, _next) def __init__(self, element, nxt): self._element element self._next nxt def __init__(self): self._head None self._size 0 def push(self, e): self._head self._Node(e, self._head) # 新节点指旧头头指针换新 self._size 1 def pop(self): if self.is_empty(): raise IndexError(pop from empty stack) ans self._head._element self._head self._head._next # 头指针后移旧节点交给 GC self._size - 1 return ans def is_empty(self): return self._size 0 def __len__(self): return self._size逻辑说明push 的写法最容易看漏——self._Node(e, self._head) 把当前头节点作为新节点的 next再把 _head 指向新节点顺序反了就是经典的断链翻车。pop 取出头节点元素头指针后移一位旧头节点失去引用后由垃圾回收处理。参数说明_Node 的 element 和 nxt 分别是元素值和下一节点指针nxt 允许为 NoneNone 即链表尾slots的第二个好处是属性访问比走dict更快在循环里反复读写节点字段时能感受到差异。3.3 数组版和链表版怎么选看访问模式和数据规模两种实现放一起对照着读比单独读任何一个都有收获。判断维度就三个访问方式、增删位置、内存局部性。数组按下标随机访问 O(1)链表走到第 i 个节点得从头数过去 O(n)数组头部插入 O(n)链表改两个指针 O(1)数组内存连续对缓存友好链表节点分散、每个节点还搭上指针开销。对比项数组实现链表实现按下标访问O(1)O(n)头部插入/删除O(n)O(1)尾部插入摊销 O(1)有 tail 指针时 O(1)内存局部性连续缓存友好节点分散指针占额外内存实际工程里的选择逻辑很简单主要操作是「按下标读」无脑选数组主要操作是「在头部反复增删」比如广度优先遍历的辅助队列链表更合适。需要提醒的是链表的 O(1) 是有条件的——尾部删除在没维护 tail 的情况下是 O(n)你得先看实现里有没有尾指针字段。这套源码不同章节给的做法不一样读的时候别拿一个结论套所有文件这种细节差异正是它值得逐文件读的原因。4. 排序、堆与图遍历把算法源码改造成可复用工具的要点数据结构的源码读顺之后算法源码反而更好玩因为输入输出明确可以立刻跑对比实验。这一章挑排序、堆、图遍历三块排序的重点在比较器和稳定性堆的重点在下标映射图遍历的重点在队列选型。这三块的源码我都自己改过、跑过对照下面说的都是实际会遇到的点。4.1 归并排序的合并逻辑与稳定性比较条件决定先后顺序排序章节里归并排序源码很典型先对半切递归到底再合并。初学者自己写时两个问题最常见漏递归边界合并时把「先比较后放回」写成「直接拼接」要么栈溢出要么结果不对。归并排序源码真正的看点只有一个合并过程里相等元素谁先谁后。# merge_sort.py —— 归并排序的合并核心 def merge(src, left, right, mid): 把左右两段有序子序列合并进 src。 left..mid 和 mid1..right 各自有序。 i, j left, mid 1 temp [] while i mid and j right: if src[i] src[j]: # 注意是 不是 temp.append(src[i]) i 1 else: temp.append(src[j]) j 1 # 至少有一边已走完把剩下的一股脑续上 temp.extend(src[i:mid 1]) temp.extend(src[j:right 1]) src[left:right 1] temp def merge_sort(src, left0, rightNone): if right is None: right len(src) - 1 if left right: return # 只有一个元素天然有序 mid (left right) // 2 merge_sort(src, left, mid) merge_sort(src, mid 1, right) merge(src, left, right, mid)逻辑说明比较条件写成 src[i] src[j] 是稳定排序的关键。写成 的话相等元素会把右侧的先放进来等值元素的相对顺序被打乱这在按多字段排序的场景先按主键再按次键里会直接出错。参数说明left、right、mid 都是闭区间下标right 默认 None、首次调用再取 len-1是 Python 里常见的延迟初始化写法避免把可变对象放默认参数。temp 是临时列表空间代价 O(n)这是非原地算法的正常成本。4.2 二叉堆的下滤与上滤数组下标映射是堆的核心优先队列是这套源码里数学味最浓的部分。二叉堆明明是树形结构却用数组存原因是完全二叉树可以靠下标定位父子下标 i 的左孩子是 2i1右孩子是 2i2父节点是 (i-1)//2。有了这个映射上滤下滤就只是数组元素交换不涉及任何指针复杂度差异不是玄学理清下标就全通了。# min_heap.py —— 最小堆的下滤核心 def _downheap(self, i): 把 i 位置的元素往下沉直到满足堆序。 调用前提i 的子树已经满足堆序。 n len(self._data) while True: left 2 * i 1 right 2 * i 2 smallest i if left n and self._data[left] self._data[smallest]: smallest left if right n and self._data[right] self._data[smallest]: smallest right if smallest i: break # 自己就是最小的到位了 self._data[i], self._data[smallest] self._data[smallest], self._data[i] i smallest逻辑说明下滤让 i 位置的元素不断向叶子方向移动始终保持「父节点 子节点」。每次跟两个孩子里较小的比因为只有换到较小子树上才能维持堆序。删除堆顶的流程是把最后一个元素搬到堆顶再对堆顶跑一次 _downheap这样删完后树仍是完全二叉树。参数说明left/right 的边界判断用 n 而不是 len(self._data) 的别名因为这个函数会被内部其他方法复用调用前确认 i 不在叶子层否则 while 白转一圈。上滤 _upheap 是它的镜像操作插入堆尾后一路和父节点比较、必要时上移。4.3 图的邻接表与 BFS队列选型和层级记录的细节图的实现是这套源码里最复杂的部分光顶点和边的建模就有邻接矩阵、边列表、邻接表三种方案。图章节默认给的是邻接表变体。实际读的时候不建议一上来啃完整 Graph 类直接跳 BFS 或 DFS 实现拿着一个具体图手推一遍反推数据结构的需求效率高很多。# graph_bfs.py —— 邻接表上的广度优先遍历 from collections import deque def bfs(graph, start): graph 提供 neighbors(v) 方法返回 v 的所有邻居。 返回从 start 出发能到达的所有顶点及其层级。 level {start: 0} frontier deque([start]) while frontier: v frontier.popleft() for w in graph.neighbors(v): if w not in level: # 已发现的顶点不再入队 level[w] level[v] 1 frontier.append(w) return level逻辑说明BFS 的层级由 level 字典隐含维护不需要单独的 visited 集合「已发现」和「已访问」在这里可以共用同一本字典。frontier 是 deque 而不是 list因为 popleft 是 O(1)list.pop(0) 是 O(n)顶点上万时差距是毫秒级的。参数说明graph.neighbors(v) 是图对外的最小接口底层用邻接表、邻接矩阵还是别的结构对 BFS 完全透明——这正好呼应第 2 章的面向契约编程图算法的源码依赖的是 neighbors 契约不依赖具体存储。5. 避坑指南复现这套 Python 源码时最容易翻车的五个细节这一章把拆包、改包过程中踩过的坑整理出来每条按「现象 → 原因 → 解决」写你踩到相同问题时可以直接对症。这里没有理论全是实际跑出来的血泪记录。5.1 三个运行期硬坑递归深度、扩容策略与空容器现象直接跑树章节的前序遍历示例数据深度到一千多层时抛 RecursionError程序直接崩。原因Python 默认递归深度限制是 1000树的深度优先遍历、部分递归排序实现都靠递归写二叉树退化成单链时递归深度轻松超过这个值。这不是代码写错是运行环境的天花板。解决临时验证用 sys.setrecursionlimit(10000) 抬高上限注意这只是缓解要根治就把递归遍历改成显式栈的迭代版本。我一般两种都做先抬上限验证算法正确性再改迭代版做压测避免它成为线上代码的定时炸弹。判断是不是这个问题很简单——报错栈里一定带 recursion 字样而且深度正好卡在 1000 附近。注意setrecursionlimit 调得过高会导致进程栈溢出崩溃线上代码不要用它只服务于本地验证。现象在队列实现里用 list.pop(0) 出队数据量到几万时明显卡顿。原因list 是动态数组头部 pop(0) 要整体搬动后面所有元素O(n) 的代价在循环里被反复放大。源码里链式队列存在的原因之一就是这个你用数组队列跑大数据量测试自然会撞上这堵墙。解决大数据量测试改用链式队列或 collections.deque。判断标准很直接把数据量从一万加到五万观察耗时增长曲线O(n) 会让耗时接近线性上涨摊销 O(1) 几乎不变。这里想强调一点源码里数组队列刻意保留 pop(0) 不是作者没优化是为了让你亲眼看到两种存储的复杂度差异读代码时别把这种教学写法当生产建议。现象删除链表中某个节点后遍历结果缺了半条链表或者操作 tail 时抛 NoneType 属性错误。原因典型指针维护错误——删节点时没先接好前驱和后继的引用或者有 tail 指针的链表删尾节点时没让 tail 回退。链表题最常见的翻车点就是先断引用再焊引用。解决动手改之前先画图把要删的节点、它的前驱、它的后继画出来写代码严格按「先焊新的、再断旧的」来。定位这种问题最快的办法是在删除方法里临时加断言打印删除前后三个节点的对象 id一眼看出引用断在哪。这套源码里涉及删除的地方都有循环不变量注释读的时候盯注释能少犯一半错。5.2 两个理解层的坑继承误读与迭代器协议缺失现象觉得基类方法没用把几十个方法全塞进一个类写完发现没法复用两个实现类之间到处复制粘贴。原因没理解继承在这套源码里的真实作用是契约复用。基类把公共行为收在顶层子类只写差异一旦平铺到一个类里替换性和可测试性两个最大的好处就丢了。解决每读一个结构前先画一张「基类-子类」关系图标清哪些方法继承、哪些覆写。这个动作花不了两分钟但能让你读图算法时自动沿用同一套心智模型。检验标准是如果两个实现类里有超过三成代码是复制粘贴的说明基类抽得不够回看源码的继承层次把公共部分上移。遇到多继承先查 MROPython 的方法解析顺序是深度优先从左到右别靠猜。现象给自定义容器实现了 append、pop但 for 循环一跑就报 TypeErrorlen() 也不认。原因Python 容器协议靠特殊方法驱动for 循环要iterlen() 要len下标要getitem。只实现业务方法没实现协议方法在内置函数看来它就不是容器。解决对照源码里每个自定义类的协议方法清单补全最少是len配iter需要下标访问的再加getitem。补完之后立刻能配合内置的 sorted、len、for 使用这也是把源码里的类改成自己工具的关键一步。顺手验证 list(custom_obj) 和 for 循环行为一致能过这两个基本用法说明协议补全了。6. 把源码变成自己的性质测试、比较器与面试索引卡这份资源下载到本地之后先别急着从头翻到尾。我给自己定的标准是能不看原文复现核心二十行、能写测试证明实现没坏、能把它塞进标准库工具里一起工作。做到这三步源码才算真正进了你的工具箱。第一个习惯是写性质测试。不要测具体数据测不变的性质栈连续 push 再连续 pop弹出顺序一定和压入相反长度守恒排序前后元素多重集合完全一致。这种测试比对比单个样例可靠得多因为性质是算法正确性的充分体现。# test_stack_property.py —— 一个最基本的性质测试 def test_push_pop_order(): s ArrayStack() data list(range(1000)) for x in data: s.push(x) popped [s.pop() for _ in range(len(s))] assert popped data[::-1] # 后进先出 assert len(s) 0 # 长度守恒这个测试时间开销可以忽略但能在你改任何一行实现之后立刻告诉你有没有破坏栈的契约是个性价比极高的安全网。第二个习惯是给自建类实现比较器。标准库的 sorted、heapq、bisect 全都依赖lt。给自定义类补上lt和eq对象就能直接进堆、排序和二分。比如给图的边类实现按权重比较的ltKruskal 算法立刻可以写成标准库排序加并查集不用再手写堆。第三个习惯是面试前做索引卡。按数组、链表、树、堆、图五个主题各建一张卡正面写「这个结构的 ADT 契约是什么」背面写「核心二十行代码 复杂度」。不复述全文只默写核心。默写不出的地方就是你还不能声称掌握的地方回去重读对应章节源码已经会的部分直接跳过。这套源码我前后拆过两遍第二遍收获比第一遍大得多差别就在这三个习惯。从那以后我每次拿到新的源码包都强制自己先画基类关系图、再写性质测试、最后做索引卡这个流程帮我避开了好几次「读的时候全懂、写的时候全忘」的翻车。希望帮到你。本文还有配套的精品资源点击获取