简介这份文档面向Python初学者与准备算法面试的开发者系统梳理数据结构与算法的核心概念及Python实现方式帮助读者建立从数据组织到问题求解的完整认知。资源为单个docx文档压缩包约15KB内容按章节展开涵盖数组、链表等基本结构以及二叉树、二叉搜索树、图等高级结构并配有节点类定义、插入删除遍历等示例代码。文档从「什么是数据结构」「什么是算法」入手逐步讲解两者关系与Python实现的优势再深入到数组索引操作、链表节点指针、二叉树前中后序遍历、二叉搜索树的对数级查找以及图的邻接矩阵与邻接表表示知识点衔接紧密适合作为课程笔记或复习提纲。目前已有789人学习下载读者可借此快速掌握常见结构的代码写法与算法思路为后续刷题和项目开发打下基础。1. 从一份 docx 说起Python 数据结构与算法分析到底该装什么很多人第一次看到「Python数据结构与算法分析.docx」这个标题第一反应是去找一份现成的文档或者课件。但真正在一线写代码的人会告诉你这个标题背后其实对应着一条非常具体的落地路径用 Python 把线性表、栈、队列、树、图、排序、查找、递归、动态规划这些结构逐个实现一遍再配合复杂度分析验证性能。它解决的不是「考试怎么背」而是「拿到一个实际问题我知道该选哪种结构、复杂度大概多少、Python 里怎么写才不翻车」。适合谁适合刚学完 Python 基础语法、想从「会写脚本」进阶到「能设计模块」的人也适合考研 408 复习数据结构时想用 Python 验证一遍的选手。热搜里「数据结构与算法分析」「python入门」「数据结构期末复习」这几个词本质上都指向同一件事你得有一份能跑、能改、能测的代码而不是只收藏一份 docx。2. 环境与工具链把 Python 数据结构实验跑起来的最小配置2.1 安装 Python 与必装库的取舍「python安装」「python安装教程」「安装python」这几个词常年挂在热搜上说明环境问题确实是第一道坎。我一般建议直接用 Python 3.10 以上的版本语法特性够用类型注解也成熟。安装时务必勾选 Add Python to PATH否则后面在 cmd 里敲 python 会提示找不到命令。装完之后数据结构与算法分析这条线其实不需要太多第三方库标准库的collections、heapq、bisect、array已经覆盖了大部分场景。但如果你要做性能对比和画图numpy 和 matplotlib 值得装。热搜里「python安装numpy库的方法」问的人很多最稳的方式是# 先升级 pip避免旧版解析依赖失败 python -m pip install --upgrade pip # 安装数值计算和绘图库用于后续复杂度实测 python -m pip install numpy matplotlib逻辑说明第一条命令升级 pip 本身很多安装失败是因为 pip 版本太旧解析不了 wheel。第二条装 numpy 和 matplotlib前者用于构造大规模测试数据后者用于把不同算法的时间曲线画出来。参数说明如果你在国内网络环境可以加-i指定镜像源但不要写死某个源换着试。验证是否成功import numpy as np import matplotlib.pyplot as plt print(np.__version__)能打印出版本号就说明环境通了。这一步看着简单但「python下载」「python官网下载」这些热搜词背后大量新手卡在 PATH 和 pip 上先把这关过了再谈算法。2.2 用虚拟环境隔离每个实验数据结构实验报告往往要交多个版本不同实验依赖不同。我习惯每个实验目录建一个 venv# 在实验目录下创建虚拟环境 python -m venv venv # Windows 激活 venv\Scripts\activate # macOS / Linux 激活 source venv/bin/activate逻辑说明venv 会把当前项目的解释器和第三方库隔离开避免 A 实验升级了 numpy 导致 B 实验跑不起来。参数说明激活后命令行前面会出现(venv)前缀看到它就说明生效了。退出用deactivate。这一步是血泪经验很多人把所有实验塞进全局环境最后依赖冲突到想重装系统。2.3 目录结构建议一个能长期维护的结构大概是这样dsa_lab/ ├── venv/ ├── linear/ │ ├── array_list.py │ └── linked_list.py ├── tree/ │ └── binary_tree.py ├── graph/ │ └── adjacency.py ├── sort/ │ └── sorts.py └── bench/ └── benchmark.py按数据结构分目录bench 单独放性能测试。这样你写「数据结构实验报告」时每个模块对应一节代码和结论都能对上。3. 线性结构数组、链表、栈和队列的 Python 实现与复杂度验证3.1 为什么 Python 的 list 不等于数组热搜里「数据结构408 图和数组」「pandas数据结构创建」都涉及数组这个概念。Python 的 list 底层是动态数组支持 O(1) 随机访问但头部插入是 O(n)。很多人直接拿 list 当队列用pop(0)一跑大数据就慢得离谱。正确做法是用collections.deque。下面用 list 手写一个动态数组理解扩容机制import ctypes class DynamicArray: def __init__(self): self._n 0 # 实际元素个数 self._capacity 1 # 当前容量 self._A self._make_array(self._capacity) def _make_array(self, c): # 用 ctypes 申请底层连续内存 return (c * ctypes.py_object)() def __len__(self): return self._n def __getitem__(self, k): if not 0 k self._n: raise IndexError(index out of range) return self._A[k] def append(self, obj): if self._n self._capacity: self._resize(2 * self._capacity) # 容量翻倍 self._A[self._n] obj self._n 1 def _resize(self, c): B self._make_array(c) for k in range(self._n): B[k] self._A[k] self._A B self._capacity c逻辑说明_resize每次把容量翻倍均摊到每次 append 的复杂度是 O(1)。参数说明初始容量设为 1 是为了演示实际可以设 8 或 16 减少前期扩容次数。验证扩容行为da DynamicArray() for i in range(10): da.append(i) print(fn{len(da)}, capacity{da._capacity})你会看到容量按 1、2、4、8、16 增长。这就是「数据结构与算法分析」里均摊分析的经典案例比背结论直观得多。3.2 链表单链表反转与快慢指针链表是面试和考研的高频点。热搜里「leecode必刷基础算法题」很多都围绕链表。手写一个单链表并实现反转class Node: def __init__(self, val, nxtNone): self.val val self.next nxt def reverse(head): prev None cur head while cur: nxt cur.next # 先存下一个节点 cur.next prev # 反转指针 prev cur # prev 前移 cur nxt # cur 前移 return prev逻辑说明三指针法prev 记录已反转部分的头cur 是当前处理节点nxt 暂存后继防止断链。参数说明head 为 None 时直接返回 None循环不执行。时间复杂度 O(n)空间 O(1)。快慢指针找中点def middle(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next return slow逻辑说明fast 每次走两步slow 走一步fast 到头时 slow 正好在中点。这个技巧在判断环、找中点、归并排序链表版本里反复出现值得单独记牢。3.3 栈与队列用 deque 和 list 的边界栈用 list 的 append/pop 就是 O(1)队列必须用 dequefrom collections import deque # 栈 stack [] stack.append(1) stack.pop() # 队列 q deque() q.append(1) # 入队 q.popleft() # 出队O(1)逻辑说明deque 是双向链表块结构两端操作都是 O(1)。参数说明popleft拼写容易错注意是 popleft 不是 popLeft。用 list 做队列时pop(0)是 O(n)数据量上万就能感觉到卡顿这是最常见的翻车点之一。4. 树与图从二叉树遍历到邻接矩阵构建4.1 二叉树的三种遍历与递归转迭代热搜里「python构建邻接矩阵」「数据结构排序算法」都和图、树相关。先看二叉树class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def inorder(root): # 中序递归左 - 根 - 右 if not root: return [] return inorder(root.left) [root.val] inorder(root.right)逻辑说明递归写法直观但深度大时会触发 Python 递归上限。参数说明默认递归深度约 1000超过要sys.setrecursionlimit。迭代版中序def inorder_iter(root): res, stack [], [] cur root while cur or stack: while cur: stack.append(cur) cur cur.left cur stack.pop() res.append(cur.val) cur cur.right return res逻辑说明用显式栈模拟递归调用栈先一路向左压栈弹出时访问并转向右子树。这个模板稍作修改就能做前序和后序是必须掌握的套路。4.2 用邻接矩阵和邻接表表示图「python构建邻接矩阵」是热搜词说明很多人卡在图的第一步。邻接矩阵适合稠密图def build_matrix(n, edges): # n 个节点edges 是 (u, v) 列表 mat [[0] * n for _ in range(n)] for u, v in edges: mat[u][v] 1 mat[v][u] 1 # 无向图对称 return mat逻辑说明二维列表初始化必须用列表推导不能写[[0]*n]*n否则所有行是同一个对象引用改一行全变。参数说明n 是节点数edges 是边列表。邻接表更省空间from collections import defaultdict def build_adj(n, edges): adj defaultdict(list) for u, v in edges: adj[u].append(v) adj[v].append(u) return adj逻辑说明defaultdict 省去判断 key 是否存在的步骤。参数说明有向图去掉反向添加那行即可。稠密图用矩阵稀疏图用邻接表这是选型的基本判断。4.3 BFS 与 DFS 的模板from collections import deque def bfs(adj, start): visited {start} q deque([start]) order [] while q: node q.popleft() order.append(node) for nxt in adj[node]: if nxt not in visited: visited.add(nxt) q.append(nxt) return order def dfs(adj, node, visitedNone): if visited is None: visited set() visited.add(node) for nxt in adj[node]: if nxt not in visited: dfs(adj, nxt, visited) return visited逻辑说明BFS 用队列保证按层扩展DFS 用递归或栈一路深入。参数说明visited 用 set 而不是 list查找是 O(1)。这两个模板是图论题的地基最短路径、连通分量、拓扑排序都从它们长出来。5. 排序与查找复杂度实测和常见翻车点排查5.1 六种排序的 Python 实现与对比热搜里「数据结构排序算法」「冒泡排序算法c」「堆排序算法」都在问排序。用 Python 写一遍def bubble(a): n len(a) for i in range(n): 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 def quick(a): if len(a) 1: return a pivot a[len(a) // 2] left [x for x in a if x pivot] mid [x for x in a if x pivot] right [x for x in a if x pivot] return quick(left) mid quick(right)逻辑说明冒泡加了 swapped 标志最好情况 O(n)。快排用列表推导写法简洁但空间复杂度高。参数说明pivot 取中间元素避免有序数组退化。堆排序用 heapqimport heapq def heap_sort(a): heapq.heapify(a) # 原地建堆 O(n) return [heapq.heappop(a) for _ in range(len(a))]逻辑说明heapify 是原地建堆heappop 每次弹出最小值。参数说明heapq 是小顶堆要大顶堆得取负号。5.2 用 timeit 实测复杂度import timeit import random for size in [100, 1000, 5000]: data [random.randint(0, 10000) for _ in range(size)] t timeit.timeit(lambda: sorted(data), number100) print(fsize{size}, sorted time{t:.4f}s)逻辑说明timeit 重复执行取平均减少单次波动。参数说明number 是执行次数数据量大时调小。把不同算法跑一遍画成曲线比看 Big-O 公式有说服力得多。5.3 避坑与排查五个高频翻车现场现象一递归深度超限报 RecursionError。原因二叉树退化成链表递归深度等于节点数。解决改用迭代版或sys.setrecursionlimit(10000)但根本方案是换迭代。现象二[[0]*n]*n初始化矩阵后改一个值全变。原因外层乘号复制的是同一个内层列表引用。解决用[[0]*n for _ in range(n)]。现象三用 list 做队列数据上万后极慢。原因pop(0)是 O(n)。解决换collections.deque的popleft。现象四快排对已排序数组退化到 O(n²)。原因pivot 固定取首元素。解决随机选 pivot 或取中位数。现象五字典遍历时修改字典报 RuntimeError。原因迭代中改变大小。解决先list(d.keys())再遍历或用字典推导重建。6. 进阶技巧用暴力枚举加剪枝把回溯题跑进时限热搜里「暴力枚举算法」「剪枝算法」「枚举算法」经常一起出现说明很多人卡在「能写出来但超时」。以子集和问题为例给一个数组和目标值判断是否存在子集和等于目标。纯暴力是 2^n加剪枝能砍掉大量分支def subset_sum(nums, target): nums.sort(reverseTrue) # 大的先试更快逼近目标 n len(nums) def dfs(i, remain): if remain 0: return True if i n or remain 0: return False # 剪枝如果剩余所有数加起来都不够直接放弃 if sum(nums[i:]) remain: return False # 选或不选 return dfs(i 1, remain - nums[i]) or dfs(i 1, remain) return dfs(0, target)逻辑说明先降序排序让大数优先remain 0剪掉超额分支sum(nums[i:]) remain剪掉剩余不足的分支。参数说明nums.sort(reverseTrue)是启发式不改变正确性只影响速度。实测在 n20 左右、目标值适中的情况下剪枝版比纯暴力快一到两个数量级。再补一个验证方法用随机数据对拍。写一个纯暴力版本作为基准随机生成小规模输入两个函数结果必须一致跑几百轮没问题再上大规模。这个习惯救过我很多次尤其是写剪枝和动态规划时边界条件最容易错。最后一个习惯每写完一个数据结构立刻写三行测试——空输入、单元素、大规模随机。空输入暴露 None 判断单元素暴露边界大规模暴露复杂度和内存。这三行测试花不了两分钟但能省下后面几小时的调试。希望帮到你。本文还有配套的精品资源点击获取