简介这是一份以Python为编程语言讲解数据结构与算法基础知识的Word文档适合正在学习编程入门、准备面试或希望系统梳理算法概念的读者。内容从数据结构与算法的基本概念和相互关系切入系统覆盖数组、链表、二叉树、二叉搜索树、图等常见数据结构并用Python代码示例演示插入、删除、更新、遍历、搜索等核心操作同时涉及排序、搜索、图算法等经典算法场景。文档共1个docx文件整个资源包约15KB属于轻量级学习笔记方便随时查阅和重点复习。目前已有787人学习下载可作为Python学习道路上的简明参考资料。借助这份材料读者不仅能理解数据组织方式与算法执行流程之间的对应关系还能掌握二叉树前序、中序、后序遍历以及二叉搜索树操作的具体代码写法为后续深入算法分析与实战打下清晰基础。1. 什么是“Python数据结构与算法分析”一份能跑、能对照、能验证的算法手稿很多搞 408 考研或刚开始刷 LeetCode 的朋友手边都有一本《数据结构与算法分析——C语言描述第四版》或者严蔚敏的 C 语言版。书读完了节点、指针、AVL 旋转都懂了一打开编辑器还是写不出能跑的代码。这份标题为Python数据结构与算法分析的 docx做的不是把教材翻译成 Python而是把每个数据结构、每个算法分析点变成一组你能直接运行、能改参数、能对照复杂度结论的实验脚本。它解决的是“看书会背、上机卡壳”的断层问题适合三类人准备 408 数据结构考研题的考生想补算法基础的转码新手以及刷题时反复被“这个操作为什么是 O(n)”卡住的 Python 用户。下面这套内容就是在说你拿到这份文档之后怎么把它变成本地可复现的一套训练流程。2. 跑通这套分析的最小环境Python 版本选择、工程目录与第一份实验脚本2.1 Python 环境里最稳的组合3.10 以上的解释器加纯标准库做数据结构和算法分析不需要第一时间上 Pandas、NumPy 这些重型库。原因很简单算法实验要复现教材结论越少的外部依赖越不容易被环境差异干扰。我一般建议装 Python 3.10 或更高版本理由不是追求新语法而是 3.10 之后match、zip(strictTrue)、更好的类型注解支持让代码在表达“结构”和“约束”时更清楚。如果是 Linux 系统直接sudo apt install python3.11Windows 去官网下载安装包记得勾选“Add Python to PATH”macOS 用 Homebrew 装也行。安装完成后先确认解释器版本顺手把 pip 升一下级。很多“环境跑不起来”的问题其实是装了多个 Python 版本命令行里python指向的和你 IDE 里选定的不是同一个。python --version pip --version which pythonwhich python这条命令最实用它能直接告诉你当前 shell 用的是哪个路径下的解释器。如果你同时在用 VS Code 和 PyCharm务必让两个工具的 Python 解释器指向同一个路径否则会出现“命令行能 import编辑器里 import 报错”的灵异事件。2.2 目录怎么组织把 docx 手稿拆成三个文件夹和一张入口页拿到《Python数据结构与算法分析.docx》这类文档不建议从头到尾线性读。更实用的做法是把它当成一份实验指导书每个章节对应一组脚本。按我自己的习惯工程目录长这样algorithm_playground/ ├── data_structures/ # 链表、栈、队列、树、图 │ ├── linked_list.py │ ├── stack_queue.py │ └── binary_tree.py ├── algorithm_analysis/ # 排序、查找、复杂度验证 │ ├── sort_algorithms.py │ ├── timing_utils.py │ └── complexity_check.py ├── experiments/ # 每次实验的记录脚本 │ ├── exp01_linked_vs_list.py │ └── exp02_sort_compare.py这样拆有三个好处。第一手稿里的“代码片段”变成了有名字的模块可以被反复 import第二实验结果单独放在experiments里不污染原实现第三复习 408 的时候你按data_structures下的文件名就能找到所有代码必背结构的 Python 版本。有人喜欢把所有函数塞进一个.py文件前期省事后面改一处就全局报警血泪教训。2.3 第一份能验证“链表到底怎么存”的实验脚本大多数数据结构教材第一个代码块都是链表节点。看似简单但很多人其实是靠背的没想过节点对象在内存里怎么互相引用。下面是一份最小可运行的链表脚本我用它来验证“头插”和“尾插”两种构建方式的差异。# data_structures/linked_list.py class Node: __slots__ (value, next) # 限制属性省内存也防止手滑加错字段 def __init__(self, value): self.value value self.next None def build_by_head(values): 头插法每次把新节点放到头部注意这样得到的链表是逆序的 head None for v in values: node Node(v) node.next head head node return head def build_by_tail(values): 尾插法保留 tail 指针新节点接在尾部顺序不变 head Node(values[0]) tail head for v in values[1:]: node Node(v) tail.next node tail node return head def show(head): cur head result [] while cur is not None: result.append(str(cur.value)) cur cur.next return - .join(result) if __name__ __main__: values [1, 2, 3, 4] print(head insert:, show(build_by_head(values))) print(tail insert:, show(build_by_tail(values)))运行后head insert: 4 - 3 - 2 - 1tail insert: 1 - 2 - 3 - 4。这里的逻辑说明很关键头插法之所以得到逆序是因为每个新节点都“压”在旧头之上尾插法必须维护tail指针否则每次都要遍历到链表末尾构建复杂度从 O(n) 恶化到 O(n²)。我建议你改一下build_by_head的循环故意不加node.next head那行观察输出变化——你会立刻看到链表变成只有最后一个节点可见前面的节点全部丢失。这种“少写一行 next 指针”的错位比看十遍书都记得牢。参数说明Node.__slots__不是必须的但对考研党理解“对象内存布局”有启发show函数用while cur is not None比while cur更明确因为节点对象没有布尔歧义但写清楚边界条件能减少 debug 时间。3. 用 Python 亲手实现核心数据结构从链表到二叉树的三个落点3.1 链表、栈、队列为什么列表模拟够了你还得手写一遍Python 的list太强了append、pop、insert一把梭以至于很多人没真正理解栈和队列的约束。在分析《Python数据结构与算法分析》这份手稿时一个值得做的练习是用列表模拟栈再用collections.deque模拟队列最后别急着扔掉再手写一个基于链表节点的版本。对比三种写法的内存与时间特征比单纯背“栈是后进先出”有说服力。# data_structures/stack_queue.py from collections import deque class Stack: 手写栈用 list 作为底层存储只开放 push/pop/peek def __init__(self): self._items [] def push(self, item): self._items.append(item) # 尾部追加摊还 O(1) def pop(self): if self.is_empty(): raise IndexError(pop from empty stack) return self._items.pop() # 尾部弹出O(1) def peek(self): return self._items[-1] def is_empty(self): return len(self._items) 0 class Queue: 手写队列链表实现避免 list.pop(0) 的 O(n) 开销 class _Node: __slots__ (value, next) def __init__(self, value): self.value value self.next None def __init__(self): self._head None self._tail None self._size 0 def enqueue(self, item): node self._Node(item) if self._tail is None: self._head node else: self._tail.next node self._tail node self._size 1 def dequeue(self): if self._head is None: raise IndexError(dequeue from empty queue) value self._head.value self._head self._head.next if self._head is None: self._tail None self._size - 1 return value def __len__(self): return self._size逻辑说明Queue不用list.pop(0)是因为列表头删需要移动所有后续元素复杂度 O(n)而用_head和_tail两个节点引用入队在尾部 O(1)出队在头部 O(1)。你可以在实验里向队列入 10 万条数据分别用list.append/pop(0)和这个Queue跑一遍前者会慢到让人怀疑人生后者近乎瞬时。这个对比本身就是最好的“算法分析”。参数说明__len__方法让len(queue)可用也方便调试断言_Node藏在Queue内部避免外部误用。手写栈用 list 模拟就够因为 Python 的 list 本身就是动态数组尾部增删摊还 O(1)再包一层纯粹是为了约束接口。3.2 二叉树的层序构建与遍历把递归改写成显式栈二叉树是 408 的重头戏也是 “数据结构与算法知识点归纳” 里最容易被“看明白但写不出”的部分。难点不在遍历本身而在构建——怎么把一个列表[1, 2, 3, None, 5, 6]变成一棵真树。下面给出一套层序构建方法配合非递归的前序遍历把你对“树”的理解从递归黑匣子里解放出来。# data_structures/binary_tree.py class TreeNode: def __init__(self, val): self.val val self.left None self.right None def build_tree_from_level_order(values): 层序构建二叉树values 里 None 表示空节点按满二叉树的下标关系填充 if not values or values[0] is None: return None root TreeNode(values[0]) queue [root] # 用 list 模拟队列配合 pop(0) 只用于教学 idx 1 while idx len(values): node queue.pop(0) # 取父节点教学写法生产可用 deque if idx len(values) and values[idx] is not None: node.left TreeNode(values[idx]) queue.append(node.left) idx 1 if idx len(values) and values[idx] is not None: node.right TreeNode(values[idx]) queue.append(node.right) idx 1 return root def preorder_iterative(root): 非递归前序遍历显式栈模拟系统递归栈每个节点先右后左入栈 if root is None: return [] result [] stack [root] while stack: node stack.pop() result.append(node.val) if node.right: stack.append(node.right) # 右子树先压栈左子树后压栈 if node.left: stack.append(node.left) return result if __name__ __main__: arr [1, 2, 3, None, 4, 5, 6] root build_tree_from_level_order(arr) print(preorder_iterative(root))输出为[1, 2, 4, 3, 5, 6]。构建逻辑的核心是“父节点按顺序出队子节点按顺序入队”idx每处理一个父节点消耗两个子节点位。这里的参数说明values[0] is None必须单独判断否则根节点为 None 时后续逻辑全崩pop(0)是 O(n) 操作只用于教学演示生产环境换成collections.deque。非递归前序遍历的要点在入栈顺序栈是后进先出想让“左子树先被访问”就必须先把右子树压进栈再把左子树压进栈。很多人写反结果输出顺序变成根、右、左一对比教材就懵。建议你改一次这个顺序亲眼看看输出变化比背“右入栈、左入栈”可靠得多。3.3 dict 和 set 的哈希结构数据结构“分析”在哪个环节写 Python 的人天天用dict但真到了算法分析题里很少意识到dict本质是一个哈希表。手稿里如果讲到哈希冲突、装载因子、开放寻址别直接跳过。最常见的分析考题是“用 dict 统计词频”为什么比“用 list 存再遍历”快。我自己会在 examples 里放一个小实验随机生成 10 万个整数分别用 list 的in和 dict 的in做查询看耗时差异。这里的“分析”环节不在查询本身而在于你能否解释清楚dict 查找的平均复杂度是 O(1)list 的in是 O(n)。这份《Python数据结构与算法分析》的价值就是把 C 语言版的哈希表实现思想映射到 Python 的 dict / set 上——你不用手写哈希表但要能说出写入、扩容、冲突时 Python 做了什么。这也是 408 数据结构代码必背之外最有迁移价值的部分。4. 算法分析怎么落地时间测量、复杂度核对和结果可视化4.1 用 timeit 测排序不靠经验靠三次取最小值很多初学者判断算法快慢靠“体感”这是最大的坑。体感会骗人因为一次运行包含了解释器启动、垃圾回收、CPU 频率波动等噪声。正确做法是用timeit模块重复执行并取最小值。# algorithm_analysis/timing_utils.py import timeit def bench(func, data, repeat3, number10): 对同一个函数计时多次返回最小耗时秒避免 GC 噪声 timer timeit.Timer(lambda: func(data.copy())) times timer.repeat(repeatrepeat, numbernumber) return min(times) / number # 单次平均耗时取三次最小值 # experiments/exp02_list_vs_deque.py from collections import deque def list_head_insert(n): lst [] for i in range(n): lst.insert(0, i) # 每次头插 O(n) def deque_head_insert(n): dq deque() for i in range(n): dq.appendleft(i) # 头插 O(1) if __name__ __main__: for n in [1000, 2000, 4000, 8000]: t1 bench(list_head_insert, list(range(n)), number5) t2 bench(deque_head_insert, list(range(n)), number5) print(fn{n}: list{t1:.6f}s deque{t2:.6f}s)逻辑说明bench里每次调用func(data.copy())为的是让函数每次都面对相同初始数据的独立副本避免某个算法原地修改数据后影响后续测试。timer.repeat返回三次运行的最短时间而不是平均因为最短时间最接近“无干扰”的真实执行。运行这段脚本你会看到当 n 翻倍时list 头插耗时约翻倍——符合 O(n²) 的预期轨迹deque 头插几乎平稳——O(1) 摊还。参数说明number10表示每次计时循环执行 10 次repeat3表示整组重复 3 次。数据规模从 1000 涨到 8000list 的曲线平滑上升但不会精确四倍因为插入操作本身常数级开销和内存分配混在里面。做实验时不要因为数字不完美就怀疑复杂度结论要看趋势。4.2 写一个复杂度拟合脚本用数据集增长曲线验证 O(n) 还是 O(n²)比跑单个 benchmark 更有说服力的做法是跑出一整条“n → 时间”曲线然后对比其增长形态。常见做法是把运行时间对 n 取 log-log 坐标斜率接近 1 是线性接近 2 是平方。这个技巧能直接验证你在手稿里读到的复杂度结论也是回答“为什么说这个算法是 O(n log n)”最有力的证据。# algorithm_analysis/complexity_check.py import timeit, math def measure(func, n): t timeit.Timer(lambda: func(list(range(n)))) times t.repeat(repeat3, number5) return min(times) / 5 def complexity_guess(ns, times): 用最后两个点的双对数斜率粗略判断复杂度阶数 (x1, y1), (x2, y2) zip(*[(math.log(n), math.log(t)) for n, t in zip(ns, times)][-2:]) slope (y2 - y1) / (x2 - x1) if slope 1.2: return fO(n) 附近实测斜率 {slope:.2f} if slope 1.8: return fO(n log n) 附近实测斜率 {slope:.2f} return fO(n^2) 附近实测斜率 {slope:.2f} def bubble_sort(arr): n len(arr) for i in range(n): for j in range(n - i - 1): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] if __name__ __main__: ns [200, 400, 800, 1600, 3200] times [measure(bubble_sort, n) for n in ns] for n, t in zip(ns, times): print(fn{n:5d} time{t:.6f}s) print(complexity_guess(ns, times))逻辑说明冒泡排序是 O(n²)数据规模每次翻倍理论耗时翻四倍。但在 3200 这个量级单次排序已经在秒级所以number5不能设太大否则跑一次实验要等半天。complexity_guess取最后两个点算斜率是为了避开小数据量时固定开销对斜率的污染。如果你把数据换成list.sort()同样的脚本会输出 O(n log n) 附近的斜率。参数说明math.log默认自然对数这里只关心斜率所以底数无所谓[-2:]取最后两个点如果实验数据前面几个点在 1e-5 秒量级计时器误差会很大舍掉前段更稳妥。这个脚本可以作为手稿的“验证台”每读到一个复杂度结论就写个measure进去跑一遍。4.3 统计基本操作次数比计时更稳定的分析方式计时受机器影响大而“基本操作次数”是机器无关的。分析排序算法时我习惯在关键循环里放计数器比如比较次数、交换次数。这是数据结构与算法分析里被很多自学者跳过但面试和考研手写推导时极其有用的方法。# algorithm_analysis/sort_algorithms.py def insertion_sort_with_counter(arr): compare_cnt 0 move_cnt 0 n len(arr) for i in range(1, n): key arr[i] j i - 1 while j 0 and arr[j] key: compare_cnt 1 arr[j 1] arr[j] move_cnt 1 j - 1 compare_cnt 1 # 最后一次不满足条件的比较 arr[j 1] key return arr, compare_cnt, move_cnt if __name__ __main__: data [5, 2, 4, 6, 1, 3] sorted_data, cmp, mv insertion_sort_with_counter(data.copy()) print(f排序结果: {sorted_data}) print(f比较次数: {cmp}, 移动次数: {mv})输出为比较次数 10、移动次数 6。你也可以构造一个完全逆序的数组再跑一次比较次数会明显上升。这里的逻辑是插入排序的最坏情况是逆序输入每个新元素都要和前面所有元素比较最好情况是已排序输入每轮只比较一次。用计数器比用秒表更能揭示“为什么同一个算法输入顺序不同复杂度不同”——这正是算法分析的核心视角。参数说明compare_cnt 1在 while 外部多计一次是因为循环退出时还有一次“比较失败”的判断不计入 while 条件如果不补这一下计数结果会和教材推导对不上。这个细节也是初学者最容易漏掉的地方。5. 避坑与排查数据结构与算法分析过程中最容易翻车的五处5.1 翻车现场一递归树高过大直接 RecursionError现象写二叉树前序遍历时用了递归结果数据规模一大程序直接报RecursionError: maximum recursion depth exceeded。原因Python 默认递归深度限制约 1000。树高超过这个值递归栈就爆了。不是你的算法写错是语言的运行机制限制。解决一是把递归改成显式栈就像前面 3.2 里的迭代版本二是非不得已要用递归时调用sys.setrecursionlimit(10000)并把递归函数写对退出条件。我一般建议养成“先想清楚递归深度”的习惯尤其是复习 408 数据结构代码必背时看到递归先问一句最坏情况下会调多少层。5.2 翻车现场二把 O(1) 的哈希查找误写成 O(n) 的 in 列表现象写“判断元素是否存在”的逻辑在 10 万元素级别的循环里跑了几十秒代码看起来没毛病。原因用if x in list_var判断存在性Python 会对整个 list 做线性扫描每次 O(n)。而用if x in dict_var或if x in set_var底层哈希查找平均 O(1)。解决先明确手稿里每个数据结构的查找复杂度再决定用哪个容器。排查时把list改成set问题立刻消失。这个坑几乎每个人都踩过也是算法分析从“纸面”落到“实际”的第一个信号。5.3 翻车现场三可变默认参数和全局变量污染了算法结果现象同样的函数调用两次第二次结果和第一次不一样甚至报错。原因Python 的函数默认参数如果是可变对象只会在定义时初始化一次。常见的错误写法是def func(n, lst[])第二次调用时lst里还残留着第一次的数据。全局变量同理比如某段代码修改了全局的计数器下一轮实验没重置。解决默认参数一律写None再内部初始化比如def func(n, lstNone): lst [] if lst is None else lst实验脚本里每轮循环都显式重新赋值。这类问题在写算法实验脚本时特别容易发生因为你会反复调用同一个函数对比不同数据规模。5.4 翻车现场四深拷贝与浅拷贝导致结构被无意修改现象把一份链表或树作为参数传进算法函数函数跑完原来的结构变了后面没法复用。原因Python 的传递的是引用copy.copy只复制顶层对象嵌套节点还是同一批。树、链表这类嵌套结构必须深拷贝否则函数里的改写直接落到原对象上。解决测试算法时对输入数据显式调用copy.deepcopy或者干脆在函数内部不对输入做破坏性修改而是先复制再操作。我自己的规矩是凡是需要保留原结构的实验一律用deepcopy宁可多花点内存也不赌“这个函数应该不会改原数据”。5.5 翻车现场五数据规模太小测量误差淹没了复杂度差异现象用 100 个元素测插入排序发现它比快排还快于是怀疑算法分析结论是错的。原因数据规模太小时函数调用开销、循环启动时间、计时精度波动占主导。O(n²) 算法在小 n 下常数小反而可能胜过大常数但复杂度低的算法。解决测试规模至少从 1000 起步并且做梯度测试比如 1000、2000、4000、8000观察时间随规模的增长率而不是看单点绝对值。这也是我在 4.2 写 log-log 斜率判断的原因——单点看不出趋势一组点才能排除噪声。这个坑本质上是“统计思维”缺失建议每次计时都保留原始数据别只记最后结论。6. 进阶把这套分析用到排序对比与刷题复盘上当你能熟练运行手稿里的实验脚本时下一步是搭建自己的常用算法排障工具组合。我强烈建议做一份“个人排序对照表”从冒泡、插入、快排、归并里各选一个实现挂到同一个测试框架下分别用随机数据、有序数据、逆序数据跑一遍记录比较次数和交换次数。这一步能同时验证手稿结论和你对代码的理解也能在准备面试时直接拿出数据说事。例如把 3.1 里的链表计时和 4.3 里的排序计数器组合起来写一个experiments/exp03_sort_matrix.py对同一份n2000的随机数组输出四组数据。之后再读 LeetCode 题解时我会先看它的复杂度分析再回到自己的实验台验证一遍“这个答案为什么快”比盲目刷题有效得多。数据结构和算法分析的真正价值不在于背下红黑树旋转次数而在于你拿到一个陌生问题能迅速判断瓶颈是“结构选错了”还是“算法阶数太高”。我自己的习惯是每排掉一个坑就把触发条件写进对应脚本的 docstring 里下次复习时一眼看到“不要用 list 做头插”“递归前先估算树高”。这份《Python数据结构与算法分析》不再是躺在磁盘里的 docx而是变成一台你自己搭起来的实验台——所有结论都能验证所有坑都有记录这才是投入时间学算法最值得的产出。希望帮到你。本文还有配套的精品资源点击获取