简介这份北理工2020年《数据结构》课程资源包面向正在学习C数据结构的高校学生与自学者提供从理论到实践的系统性学习路径。包内共65个文件以29个cpp源码、16个doc与5个docx文档、9个ppt与1个pptx课件、5个pdf资料为主压缩包约55.42MB涵盖课件、乐学编程代码、复习资料与历年试题四大模块。课件系统讲解数组、链表、栈、队列、树、图、哈希表等核心结构编程代码覆盖约瑟夫问题、表达式求值、哈夫曼树、平衡二叉树、图遍历与关键路径等典型实验帮助在C中动手实现并理解STL的运用复习PPT与知识点归总提炼复杂度分析、排序与查找算法要点历年试题与练习题则可用于考前自测与查漏补缺。目前已有685人学习适合希望夯实数据结构基础、提升算法设计与编码能力的读者。1. 数据结构到底该怎么学从一份课程资源里拆出可复现的路径很多人学数据结构卡住的地方不是“看不懂链表”而是“看懂了却写不出、写出来又过不了编译、过了编译又不知道复杂度对不对”。一份课程资源真正的价值不在于它有多少页 PPT而在于它能不能把抽象结构落到可运行的代码、可验证的测试、可复现的调试过程上。我见过太多人把课程资料当 PDF 收藏夹翻完线性表就停在树最后连一次完整的“建表—插入—删除—遍历”都没跑通过。这篇笔记就围绕数据结构这门课的核心模块把资源里最该动手的部分拆成能照着做的步骤线性表、栈与队列、树、图、排序查找每一块都给出最小可运行代码、参数说明和排错思路。适合正在跟课但写不出代码的初学者也适合想回头补基础、把复杂度分析真正用起来的从业者。2. 线性表与链表先把顺序存储和链式存储的边界跑清楚2.1 为什么先啃线性表它是后面所有结构的底座数据结构里最容易被低估的就是线性表。栈是操作受限的线性表队列是先进先出的线性表树的遍历序列本质也是线性序列图的邻接表更是“数组链表”的组合。如果顺序表和链表的手感没建立起来后面学树和图基本就是背概念。我一般建议先用顺序表把“随机访问”这件事跑通再用单链表把“插入删除不搬移元素”这件事跑通两个对比一出来选型逻辑自然就清楚了。顺序表的核心参数只有三个存储数组、当前长度、最大容量。插入时要判断是否越界删除时要判断位置是否合法平均时间复杂度分别是 O(n) 和 O(n)但按下标访问是 O(1)。链表的核心是节点和指针插入删除是 O(1)前提是已经拿到前驱节点但访问第 k 个元素是 O(n)。这个差异在后续做缓存、做队列、做邻接表时会反复出现。2.2 单链表的最小可运行实现class Node: def __init__(self, val): self.val val self.next None class LinkedList: def __init__(self): # 带头结点能统一插入和删除的边界处理 self.head Node(None) self.size 0 def insert(self, index, val): # index 取值范围 [0, size]越界直接拒绝 if index 0 or index self.size: raise IndexError(insert index out of range) prev self.head for _ in range(index): prev prev.next node Node(val) node.next prev.next prev.next node self.size 1 def delete(self, index): if index 0 or index self.size: raise IndexError(delete index out of range) prev self.head for _ in range(index): prev prev.next prev.next prev.next.next self.size - 1 def get(self, index): if index 0 or index self.size: raise IndexError(get index out of range) cur self.head.next for _ in range(index): cur cur.next return cur.val这段代码里最关键的是头结点。没有头结点时插入到第 0 位和删除第 0 位都要单独写分支代码会变得很碎。带头结点后所有位置的操作都统一成“找到前驱改指针”。insert的 index 允许等于 size表示尾插delete和get的 index 必须小于 size。这三个边界如果搞混测试用例一跑就露馅。参数上size必须和实际节点数严格同步任何一次插入或删除后忘记更新后续所有下标操作都会错位。我习惯在每次操作后打印size和遍历结果做交叉验证比单纯看返回值可靠。2.3 顺序表和链表的选型对照维度顺序表单链表按下标访问O(1)O(n)头部插入删除O(n)O(1)尾部插入O(1)有尾指针O(n) 或 O(1)有尾指针内存连续性连续缓存友好离散指针额外开销扩容需要搬移不需要这张表不是让你背而是让你在写代码前先问一句我的场景是查得多还是改得多查得多用顺序表频繁在头部增删用链表。很多初学者一上来就用链表做“学生成绩管理”结果每次查询都要遍历性能反而更差。3. 栈与队列用数组和链表各实现一遍才算真正理解受限线性表3.1 栈的两种实现与括号匹配实战栈是后进先出核心操作只有 push、pop、top、empty。用数组实现时栈顶指针top从 -1 开始push 时先加再存pop 时先取再减。用链表实现时所有操作都在头结点后面做push 就是头插pop 就是删除第一个节点。两种实现的时间复杂度都是 O(1)区别在扩容和内存开销。括号匹配是栈最经典的入门题遇到左括号入栈遇到右括号看栈顶是否匹配最后栈必须为空。这个题能跑通说明你对栈的“后进先出”和边界判断都过关了。def is_valid(s): stack [] pairs {): (, ]: [, }: {} for ch in s: if ch in ([{: stack.append(ch) elif ch in )]}: # 栈空或栈顶不匹配直接判失败 if not stack or stack[-1] ! pairs[ch]: return False stack.pop() # 最后必须全部匹配完 return len(stack) 0这里有个容易翻车的点字符串里可能混入非括号字符。上面的写法会忽略它们如果你要求“只允许括号字符”就得在 else 分支里加判断。参数上pairs字典的键是右括号值是左括号顺序不能反否则比较逻辑就错了。3.2 循环队列用取模运算解决假溢出普通数组队列出队时不搬移元素front 一直往后走很快 rear 就到头了但前面还有空位这就是假溢出。循环队列用(rear 1) % capacity来绕回去。判断队满有两种常见做法一是牺牲一个空位(rear 1) % capacity front表示满二是额外维护 size 变量。我一般用第一种代码更简洁。class CircularQueue: def __init__(self, k): self.capacity k 1 # 多开一个位置用于判满 self.data [0] * self.capacity self.front 0 self.rear 0 def enqueue(self, val): if (self.rear 1) % self.capacity self.front: raise OverflowError(queue is full) self.data[self.rear] val self.rear (self.rear 1) % self.capacity def dequeue(self): if self.front self.rear: raise IndexError(queue is empty) val self.data[self.front] self.front (self.front 1) % self.capacity return valcapacity设为k 1是这套写法的关键如果你直接设成 k队满和队空的条件会撞在一起分不清。front rear表示空(rear 1) % capacity front表示满。这两个条件必须同时记住少一个就会在边界测试时出错。3.3 栈和队列在后续结构里的影子后面学树的层序遍历要用队列学图的广度优先搜索要用队列学深度优先搜索要用栈或递归。表达式求值、函数调用栈、撤销操作全是栈的应用。把这两个结构手写一遍后面遇到“用两个栈实现队列”“用队列实现栈”这类题你才知道边界在哪里。4. 树与二叉树遍历写不对后面全白费4.1 二叉树的链式存储与三种递归遍历二叉树每个节点最多两个子节点链式存储就是 left 和 right 两个指针。递归遍历的代码极短但短不代表简单很多人写完前序就以为中序后序只是换个顺序结果一跑就发现输出不对。核心区别在于“访问根节点”这行代码放在哪。class TreeNode: def __init__(self, val): self.val val self.left None self.right None def preorder(root, res): if not root: return res.append(root.val) # 根在前 preorder(root.left, res) preorder(root.right, res) def inorder(root, res): if not root: return inorder(root.left, res) res.append(root.val) # 根在中 inorder(root.right, res) def postorder(root, res): if not root: return postorder(root.left, res) postorder(root.right, res) res.append(root.val) # 根在后递归遍历的时间复杂度是 O(n)空间复杂度是 O(h)h 是树高。最坏情况退化成链表时 h n递归深度可能爆栈。如果你用 Python 跑一万个节点的斜树大概率会遇到递归深度限制这时候要么改迭代要么调sys.setrecursionlimit。我一般建议先用小数据验证逻辑再考虑大数据下的迭代写法。4.2 层序遍历与队列的配合层序遍历必须用队列。根节点先入队然后循环出队一个节点访问它把左右子节点依次入队。这个过程中队列里始终保存的是“当前层的下一层候选”。如果你用栈出来的就是深度优先的顺序不是一层一层。from collections import deque def level_order(root): if not root: return [] res [] q deque([root]) while q: node q.popleft() res.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) return resdeque的popleft是 O(1)如果用普通列表的pop(0)是 O(n)数据量大时差距很明显。这个细节在课程作业里经常被忽略但它是“知道”和“做到”的分界线。4.3 二叉搜索树的查找与插入边界二叉搜索树要求左子树所有节点小于根右子树所有节点大于根。查找时比较当前节点值小往左大往右。插入时找到空位挂上去。这里最容易翻车的是“相等”怎么处理有的实现允许重复值放右边有的直接拒绝。你必须先明确规则再写代码否则测试用例里出现重复值就会行为不一致。删除是 BST 里最麻烦的分三种情况叶子直接删只有一个子节点用子节点替代有两个子节点找右子树最小节点或左子树最大节点替代。很多人卡在第三种其实只要把替代节点的值复制过来然后递归删除那个替代节点就行。5. 图与排序查找从邻接矩阵到快排的落地细节5.1 图的两种存储方式与选择依据邻接矩阵用二维数组matrix[i][j]表示 i 到 j 是否有边或权值。优点是判断两点是否相邻是 O(1)缺点是空间 O(n²)稀疏图浪费严重。邻接表用数组加链表或列表每个节点存它的邻居空间 O(n e)适合稀疏图。选哪个取决于边数边接近 n² 用矩阵边远小于 n² 用邻接表。# 邻接表建图无向图 def build_graph(n, edges): graph [[] for _ in range(n)] for u, v in edges: graph[u].append(v) graph[v].append(u) # 有向图去掉这一行 return graphn是节点数edges是边列表。无向图每条边要加两次有向图只加一次。这个细节在跑连通性判断时直接影响结果少加一次就会把连通图判成不连通。5.2 快速排序的分区逻辑与递归边界快排的核心是分区选一个基准把小于它的放左边大于它的放右边然后递归两边。分区写法有很多种我习惯用双指针交换法逻辑清晰且不容易死循环。def quick_sort(arr, left, right): if left right: return pivot arr[left] i, j left, right while i j: # 先动 j找小于基准的 while i j and arr[j] pivot: j - 1 # 再动 i找大于基准的 while i j and arr[i] pivot: i 1 arr[i], arr[j] arr[j], arr[i] # 基准归位 arr[left], arr[i] arr[i], arr[left] quick_sort(arr, left, i - 1) quick_sort(arr, i 1, right)这段代码里i j的判断在两层 while 里都不能省否则指针会越界。先动 j 再动 i 是为了保证最后 i 和 j 相遇的位置一定小于等于基准。如果你反过来先动 i某些序列下会把大于基准的数换到左边排序结果就错了。这个坑我踩过不止一次后来每次写快排都先默念“先右后左”。5.3 二分查找的三种边界写法二分查找看着简单但“找目标值”“找第一个大于等于目标的位置”“找最后一个小于等于目标的位置”三种写法边界完全不同。最稳妥的方式是统一用左闭右开区间[left, right)循环条件left right这样不会死循环返回的 left 就是第一个满足条件的位置。def lower_bound(arr, target): left, right 0, len(arr) while left right: mid (left right) // 2 if arr[mid] target: left mid 1 else: right mid return left # 第一个 target 的位置mid (left right) // 2在 left 和 right 很大时可能溢出虽然 Python 不会但换成 C 或 Java 就要写成left (right - left) // 2。这个习惯最好从一开始就养成。6. 避坑与排查数据结构作业里最常见的五类翻车6.1 指针操作后忘记更新 size 或 length现象插入删除看起来正常但按下标访问时结果错位或者遍历少一个多一个。原因链表或顺序表的长度变量没有和实际元素数同步。解决每次修改结构后立刻打印 size 和完整遍历结果和预期对比。不要只看返回值返回值只能说明那一次操作没报错不能说明整体状态正确。6.2 递归遍历在大数据下爆栈现象小数据跑得好好的一上万个节点就报 RecursionError 或程序直接崩。原因递归深度等于树高斜树情况下深度等于节点数。解决先用小数据验证逻辑再改成迭代写法用显式栈模拟或者调整递归深度限制。但调限制只是临时手段真正上线要考虑迭代。6.3 循环队列的队满队空条件写反现象队列明明没满却报满或者空了还能出队。原因牺牲一个空位的写法里front rear是空(rear 1) % capacity front是满两个条件记混。解决画一个容量为 4 的循环队列手动模拟入队出队各三次把 front 和 rear 的变化写在纸上比背公式管用。6.4 快排分区时指针移动顺序搞错现象排序结果部分有序但整体不对或者某些用例死循环。原因先动了 i 再动 j导致相遇点大于基准。解决固定“先右后左”的顺序并且在两层 while 里都加上i j的判断。写完用一组包含重复元素的数组测试比如[3, 3, 3, 2, 1]。6.5 图的邻接表无向边只加了一次现象连通性判断结果和预期不符某些节点明明有边却搜不到。原因无向图每条边要在两个节点的列表里各加一次只加一次就变成了有向图。解决建图后打印每个节点的邻居列表和边列表逐条核对。这个检查花不了一分钟但能省掉半小时的调试。7. 把复杂度分析变成写代码前的习惯学数据结构到最后真正拉开差距的不是“会不会写红黑树”而是“拿到问题先估复杂度再选结构”。我现在的习惯是任何一段代码动手前先问三个问题——数据规模多大操作是查多还是改多内存有没有限制这三个问题的答案基本就决定了用数组还是链表、用哈希还是排序、用递归还是迭代。举个具体的验证方法写完一个结构后构造三组数据——空数据、单元素、大量随机数据分别跑一遍插入、删除、查找、遍历。空数据看边界判断单元素看指针和下标是否越界大量数据看性能和递归深度。这三组过了基本就能交付。如果不过优先看 size 同步、指针顺序、循环条件这三处八成问题都在那里。还有一个我踩过的坑不要一上来就追求“最优解”。先用最直白的写法把功能跑通再用复杂度分析去优化。很多人卡在“我要写一个完美的平衡树”结果连普通 BST 的删除都没写对。先跑通再跑快这个顺序不能反。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/10 12:26:09 · 阅读 1.2k 数据结构与算法实战：从线性表到图排序的代码实现与避坑指南
简介这份北理工2020年《数据结构》课程资源包面向正在学习C数据结构的高校学生与自学者提供从理论到实践的系统性学习路径。包内共65个文件以29个cpp源码、16个doc与5个docx文档、9个ppt与1个pptx课件、5个pdf资料为主压缩包约55.42MB涵盖课件、乐学编程代码、复习资料与历年试题四大模块。课件系统讲解数组、链表、栈、队列、树、图、哈希表等核心结构编程代码覆盖约瑟夫问题、表达式求值、哈夫曼树、平衡二叉树、图遍历与关键路径等典型实验帮助在C中动手实现并理解STL的运用复习PPT与知识点归总提炼复杂度分析、排序与查找算法要点历年试题与练习题则可用于考前自测与查漏补缺。目前已有685人学习适合希望夯实数据结构基础、提升算法设计与编码能力的读者。1. 数据结构到底该怎么学从一份课程资源里拆出可复现的路径很多人学数据结构卡住的地方不是“看不懂链表”而是“看懂了却写不出、写出来又过不了编译、过了编译又不知道复杂度对不对”。一份课程资源真正的价值不在于它有多少页 PPT而在于它能不能把抽象结构落到可运行的代码、可验证的测试、可复现的调试过程上。我见过太多人把课程资料当 PDF 收藏夹翻完线性表就停在树最后连一次完整的“建表—插入—删除—遍历”都没跑通过。这篇笔记就围绕数据结构这门课的核心模块把资源里最该动手的部分拆成能照着做的步骤线性表、栈与队列、树、图、排序查找每一块都给出最小可运行代码、参数说明和排错思路。适合正在跟课但写不出代码的初学者也适合想回头补基础、把复杂度分析真正用起来的从业者。2. 线性表与链表先把顺序存储和链式存储的边界跑清楚2.1 为什么先啃线性表它是后面所有结构的底座数据结构里最容易被低估的就是线性表。栈是操作受限的线性表队列是先进先出的线性表树的遍历序列本质也是线性序列图的邻接表更是“数组链表”的组合。如果顺序表和链表的手感没建立起来后面学树和图基本就是背概念。我一般建议先用顺序表把“随机访问”这件事跑通再用单链表把“插入删除不搬移元素”这件事跑通两个对比一出来选型逻辑自然就清楚了。顺序表的核心参数只有三个存储数组、当前长度、最大容量。插入时要判断是否越界删除时要判断位置是否合法平均时间复杂度分别是 O(n) 和 O(n)但按下标访问是 O(1)。链表的核心是节点和指针插入删除是 O(1)前提是已经拿到前驱节点但访问第 k 个元素是 O(n)。这个差异在后续做缓存、做队列、做邻接表时会反复出现。2.2 单链表的最小可运行实现class Node: def __init__(self, val): self.val val self.next None class LinkedList: def __init__(self): # 带头结点能统一插入和删除的边界处理 self.head Node(None) self.size 0 def insert(self, index, val): # index 取值范围 [0, size]越界直接拒绝 if index 0 or index self.size: raise IndexError(insert index out of range) prev self.head for _ in range(index): prev prev.next node Node(val) node.next prev.next prev.next node self.size 1 def delete(self, index): if index 0 or index self.size: raise IndexError(delete index out of range) prev self.head for _ in range(index): prev prev.next prev.next prev.next.next self.size - 1 def get(self, index): if index 0 or index self.size: raise IndexError(get index out of range) cur self.head.next for _ in range(index): cur cur.next return cur.val这段代码里最关键的是头结点。没有头结点时插入到第 0 位和删除第 0 位都要单独写分支代码会变得很碎。带头结点后所有位置的操作都统一成“找到前驱改指针”。insert的 index 允许等于 size表示尾插delete和get的 index 必须小于 size。这三个边界如果搞混测试用例一跑就露馅。参数上size必须和实际节点数严格同步任何一次插入或删除后忘记更新后续所有下标操作都会错位。我习惯在每次操作后打印size和遍历结果做交叉验证比单纯看返回值可靠。2.3 顺序表和链表的选型对照维度顺序表单链表按下标访问O(1)O(n)头部插入删除O(n)O(1)尾部插入O(1)有尾指针O(n) 或 O(1)有尾指针内存连续性连续缓存友好离散指针额外开销扩容需要搬移不需要这张表不是让你背而是让你在写代码前先问一句我的场景是查得多还是改得多查得多用顺序表频繁在头部增删用链表。很多初学者一上来就用链表做“学生成绩管理”结果每次查询都要遍历性能反而更差。3. 栈与队列用数组和链表各实现一遍才算真正理解受限线性表3.1 栈的两种实现与括号匹配实战栈是后进先出核心操作只有 push、pop、top、empty。用数组实现时栈顶指针top从 -1 开始push 时先加再存pop 时先取再减。用链表实现时所有操作都在头结点后面做push 就是头插pop 就是删除第一个节点。两种实现的时间复杂度都是 O(1)区别在扩容和内存开销。括号匹配是栈最经典的入门题遇到左括号入栈遇到右括号看栈顶是否匹配最后栈必须为空。这个题能跑通说明你对栈的“后进先出”和边界判断都过关了。def is_valid(s): stack [] pairs {): (, ]: [, }: {} for ch in s: if ch in ([{: stack.append(ch) elif ch in )]}: # 栈空或栈顶不匹配直接判失败 if not stack or stack[-1] ! pairs[ch]: return False stack.pop() # 最后必须全部匹配完 return len(stack) 0这里有个容易翻车的点字符串里可能混入非括号字符。上面的写法会忽略它们如果你要求“只允许括号字符”就得在 else 分支里加判断。参数上pairs字典的键是右括号值是左括号顺序不能反否则比较逻辑就错了。3.2 循环队列用取模运算解决假溢出普通数组队列出队时不搬移元素front 一直往后走很快 rear 就到头了但前面还有空位这就是假溢出。循环队列用(rear 1) % capacity来绕回去。判断队满有两种常见做法一是牺牲一个空位(rear 1) % capacity front表示满二是额外维护 size 变量。我一般用第一种代码更简洁。class CircularQueue: def __init__(self, k): self.capacity k 1 # 多开一个位置用于判满 self.data [0] * self.capacity self.front 0 self.rear 0 def enqueue(self, val): if (self.rear 1) % self.capacity self.front: raise OverflowError(queue is full) self.data[self.rear] val self.rear (self.rear 1) % self.capacity def dequeue(self): if self.front self.rear: raise IndexError(queue is empty) val self.data[self.front] self.front (self.front 1) % self.capacity return valcapacity设为k 1是这套写法的关键如果你直接设成 k队满和队空的条件会撞在一起分不清。front rear表示空(rear 1) % capacity front表示满。这两个条件必须同时记住少一个就会在边界测试时出错。3.3 栈和队列在后续结构里的影子后面学树的层序遍历要用队列学图的广度优先搜索要用队列学深度优先搜索要用栈或递归。表达式求值、函数调用栈、撤销操作全是栈的应用。把这两个结构手写一遍后面遇到“用两个栈实现队列”“用队列实现栈”这类题你才知道边界在哪里。4. 树与二叉树遍历写不对后面全白费4.1 二叉树的链式存储与三种递归遍历二叉树每个节点最多两个子节点链式存储就是 left 和 right 两个指针。递归遍历的代码极短但短不代表简单很多人写完前序就以为中序后序只是换个顺序结果一跑就发现输出不对。核心区别在于“访问根节点”这行代码放在哪。class TreeNode: def __init__(self, val): self.val val self.left None self.right None def preorder(root, res): if not root: return res.append(root.val) # 根在前 preorder(root.left, res) preorder(root.right, res) def inorder(root, res): if not root: return inorder(root.left, res) res.append(root.val) # 根在中 inorder(root.right, res) def postorder(root, res): if not root: return postorder(root.left, res) postorder(root.right, res) res.append(root.val) # 根在后递归遍历的时间复杂度是 O(n)空间复杂度是 O(h)h 是树高。最坏情况退化成链表时 h n递归深度可能爆栈。如果你用 Python 跑一万个节点的斜树大概率会遇到递归深度限制这时候要么改迭代要么调sys.setrecursionlimit。我一般建议先用小数据验证逻辑再考虑大数据下的迭代写法。4.2 层序遍历与队列的配合层序遍历必须用队列。根节点先入队然后循环出队一个节点访问它把左右子节点依次入队。这个过程中队列里始终保存的是“当前层的下一层候选”。如果你用栈出来的就是深度优先的顺序不是一层一层。from collections import deque def level_order(root): if not root: return [] res [] q deque([root]) while q: node q.popleft() res.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) return resdeque的popleft是 O(1)如果用普通列表的pop(0)是 O(n)数据量大时差距很明显。这个细节在课程作业里经常被忽略但它是“知道”和“做到”的分界线。4.3 二叉搜索树的查找与插入边界二叉搜索树要求左子树所有节点小于根右子树所有节点大于根。查找时比较当前节点值小往左大往右。插入时找到空位挂上去。这里最容易翻车的是“相等”怎么处理有的实现允许重复值放右边有的直接拒绝。你必须先明确规则再写代码否则测试用例里出现重复值就会行为不一致。删除是 BST 里最麻烦的分三种情况叶子直接删只有一个子节点用子节点替代有两个子节点找右子树最小节点或左子树最大节点替代。很多人卡在第三种其实只要把替代节点的值复制过来然后递归删除那个替代节点就行。5. 图与排序查找从邻接矩阵到快排的落地细节5.1 图的两种存储方式与选择依据邻接矩阵用二维数组matrix[i][j]表示 i 到 j 是否有边或权值。优点是判断两点是否相邻是 O(1)缺点是空间 O(n²)稀疏图浪费严重。邻接表用数组加链表或列表每个节点存它的邻居空间 O(n e)适合稀疏图。选哪个取决于边数边接近 n² 用矩阵边远小于 n² 用邻接表。# 邻接表建图无向图 def build_graph(n, edges): graph [[] for _ in range(n)] for u, v in edges: graph[u].append(v) graph[v].append(u) # 有向图去掉这一行 return graphn是节点数edges是边列表。无向图每条边要加两次有向图只加一次。这个细节在跑连通性判断时直接影响结果少加一次就会把连通图判成不连通。5.2 快速排序的分区逻辑与递归边界快排的核心是分区选一个基准把小于它的放左边大于它的放右边然后递归两边。分区写法有很多种我习惯用双指针交换法逻辑清晰且不容易死循环。def quick_sort(arr, left, right): if left right: return pivot arr[left] i, j left, right while i j: # 先动 j找小于基准的 while i j and arr[j] pivot: j - 1 # 再动 i找大于基准的 while i j and arr[i] pivot: i 1 arr[i], arr[j] arr[j], arr[i] # 基准归位 arr[left], arr[i] arr[i], arr[left] quick_sort(arr, left, i - 1) quick_sort(arr, i 1, right)这段代码里i j的判断在两层 while 里都不能省否则指针会越界。先动 j 再动 i 是为了保证最后 i 和 j 相遇的位置一定小于等于基准。如果你反过来先动 i某些序列下会把大于基准的数换到左边排序结果就错了。这个坑我踩过不止一次后来每次写快排都先默念“先右后左”。5.3 二分查找的三种边界写法二分查找看着简单但“找目标值”“找第一个大于等于目标的位置”“找最后一个小于等于目标的位置”三种写法边界完全不同。最稳妥的方式是统一用左闭右开区间[left, right)循环条件left right这样不会死循环返回的 left 就是第一个满足条件的位置。def lower_bound(arr, target): left, right 0, len(arr) while left right: mid (left right) // 2 if arr[mid] target: left mid 1 else: right mid return left # 第一个 target 的位置mid (left right) // 2在 left 和 right 很大时可能溢出虽然 Python 不会但换成 C 或 Java 就要写成left (right - left) // 2。这个习惯最好从一开始就养成。6. 避坑与排查数据结构作业里最常见的五类翻车6.1 指针操作后忘记更新 size 或 length现象插入删除看起来正常但按下标访问时结果错位或者遍历少一个多一个。原因链表或顺序表的长度变量没有和实际元素数同步。解决每次修改结构后立刻打印 size 和完整遍历结果和预期对比。不要只看返回值返回值只能说明那一次操作没报错不能说明整体状态正确。6.2 递归遍历在大数据下爆栈现象小数据跑得好好的一上万个节点就报 RecursionError 或程序直接崩。原因递归深度等于树高斜树情况下深度等于节点数。解决先用小数据验证逻辑再改成迭代写法用显式栈模拟或者调整递归深度限制。但调限制只是临时手段真正上线要考虑迭代。6.3 循环队列的队满队空条件写反现象队列明明没满却报满或者空了还能出队。原因牺牲一个空位的写法里front rear是空(rear 1) % capacity front是满两个条件记混。解决画一个容量为 4 的循环队列手动模拟入队出队各三次把 front 和 rear 的变化写在纸上比背公式管用。6.4 快排分区时指针移动顺序搞错现象排序结果部分有序但整体不对或者某些用例死循环。原因先动了 i 再动 j导致相遇点大于基准。解决固定“先右后左”的顺序并且在两层 while 里都加上i j的判断。写完用一组包含重复元素的数组测试比如[3, 3, 3, 2, 1]。6.5 图的邻接表无向边只加了一次现象连通性判断结果和预期不符某些节点明明有边却搜不到。原因无向图每条边要在两个节点的列表里各加一次只加一次就变成了有向图。解决建图后打印每个节点的邻居列表和边列表逐条核对。这个检查花不了一分钟但能省掉半小时的调试。7. 把复杂度分析变成写代码前的习惯学数据结构到最后真正拉开差距的不是“会不会写红黑树”而是“拿到问题先估复杂度再选结构”。我现在的习惯是任何一段代码动手前先问三个问题——数据规模多大操作是查多还是改多内存有没有限制这三个问题的答案基本就决定了用数组还是链表、用哈希还是排序、用递归还是迭代。举个具体的验证方法写完一个结构后构造三组数据——空数据、单元素、大量随机数据分别跑一遍插入、删除、查找、遍历。空数据看边界判断单元素看指针和下标是否越界大量数据看性能和递归深度。这三组过了基本就能交付。如果不过优先看 size 同步、指针顺序、循环条件这三处八成问题都在那里。还有一个我踩过的坑不要一上来就追求“最优解”。先用最直白的写法把功能跑通再用复杂度分析去优化。很多人卡在“我要写一个完美的平衡树”结果连普通 BST 的删除都没写对。先跑通再跑快这个顺序不能反。希望帮到你。本文还有配套的精品资源点击获取