**数据结构与算法核心知识点清单**，覆盖了本科《数据结构》《算法设计与分析》课程的主要内容，适用于考研复习、面试准备或系统性知识梳理

数据结构与算法核心知识点清单覆盖了本科《数据结构》《算法设计与分析》课程的主要内容适用于考研复习、面试准备或系统性知识梳理。以下是对各条目的简明归纳与关键要点提示线性表顺序表随机存取O(1)插入/删除O(n)链表单/双/循环插入/删除O(1)但需定位O(n)栈后进先出FILO典型应用括号匹配、函数调用、后缀表达式求值操作数入栈遇运算符弹两数计算后压栈队列先进先出FIFO循环队列用(rear1)%MaxSize front判满避免假溢出串KMP算法通过预处理模式串得next[]数组或nextval[]实现主串一趟扫描时间复杂度 O(nm)数组行优先C语言addr[i][j] base (i×n j)×size列优先Fortranbase (j×m i)×size树度 最大子节点数深度 从根到最远叶节点的边数或结点数需明确约定叶子节点数 总节点数 − 分支节点数二叉树性质如“第i层最多2^(i−1)个结点”“n个结点的完全二叉树深度为⌊log₂n⌋1”遍历先序根左右、中序左根右、后序左右根均可用递归或栈/队列迭代实现线索二叉树利用空指针域指向前驱/后继按某遍历序列标志域区分指针/线索提升遍历效率O(n)建树O(1)找前驱后继BST二叉排序树左子树所有节点 根 右子树所有节点查找/插入平均O(log n)最坏O(n)中序遍历得有序序列AVL树BST的自平衡版本平衡因子 左子树高 − 右子树高 ∈ {−1,0,1}失衡时通过LL/LR/RR/RL旋转恢复哈夫曼树带权路径长度WPL最小的二叉树构造每次选两个最小权值子树合并用于最优前缀编码无歧义、变长编码图邻接矩阵适合稠密图空间O(n²)易判断边邻接表适合稀疏图空间O(ne)遍历高效图遍历DFS递归/栈解决连通性、环检测BFS队列解决单源最短路径无权图、层序遍历最小生成树MSTPrim类似Dijkstra从一点扩展用堆优化至O(e log n)Kruskal按边权排序并查集判环O(e log e)最短路径Dijkstra单源非负权贪心O(n²)或O(e log n)Floyd多源动态规划O(n³)可处理负权但不可有负环拓扑排序针对AOV网顶点表示活动用入度数组队列Kahn算法或DFS标记状态实现判定有向无环图DAG关键路径基于AOE网边表示活动计算事件最早/最晚发生时间活动最早/最晚开始时间关键活动e[i]l[i]构成关键路径决定总工期排序算法冒泡O(n²)稳定自适应快速O(n log n)平均O(n²)最坏不稳定原地归并O(n log n)稳定需O(n)辅助空间堆排序O(n log n)不稳定原地适合海量数据查找算法顺序查找O(n)适用无序表二分查找O(log n)要求有序表顺序存储更优哈希查找平均O(1)通过哈希函数冲突处理开放定址/链地址法算法策略分治分解→求解→合并归并、快排、Strassen动态规划重叠子问题最优子结构LCS、背包、最短路径贪心局部最优→全局最优Huffman、Prim、Dijkstra、活动选择回溯深度优先剪枝N皇后、0-1背包、图着色我们来手算模式串ababaa的next数组采用最常用定义next[j]表示子串P[0..j-1]的最长相等真前后缀长度即真前缀 ≠ 全串真后缀 ≠ 全串且前后缀内容完全相同。⚠️ 注意不同教材对next定义略有差异如有的从 -1 开始、有的用nextval优化此处采用主流考研/严蔚敏风格next[0] -1或0但为统一递推设next[0] -1next[1] 0单字符无真前后缀对j ≥ 2next[j]P[0..j-1]的最长真前后缀长度✅ 模式串P ababaa下标从 0 开始jP[j]子串 P[0…j]真前缀集合非空、不等于全串真后缀集合最长相等前后缀next[j]0‘a’“a”∅∅—-11‘b’“ab”{“a”}{“b”}无公共 → 长度 002‘a’“aba”{“a”,“ab”}{“a”,“ba”}“a” → 长度113‘b’“abab”{“a”,“ab”,“aba”}{“b”,“ab”,“bab”}“ab” → 长度224‘a’“ababa”{“a”,“ab”,“aba”,“abab”}{“a”,“ba”,“aba”,“baba”}“aba” → 长度335‘a’“ababaa”{“a”,“ab”,“aba”,“abab”,“ababa”}{“a”,“aa”,“baa”,“abaa”,“babaa”}公共“a” → 长度11逐位详细推导核心方法利用已知 next 值递推我们采用递推法避免穷举公式设j从 1 开始next[0] -1已定令k next[j-1]若P[k] P[j]则next[j] k 1否则回溯k next[k]重复比较直到k -1或匹配成功若k -1则next[j] 0。步骤详解j 从 1 到 5j 0:next[0] -1约定j 1:k next[0] -1→k -1⇒next[1] 0j 2:k next[1] 0比较P[k]P[0]a与P[2]a→ 相等 ⇒next[2] k1 1j 3:k next[2] 1比较P[1]b与P[3]b→ 相等 ⇒next[3] 11 2j 4:k next[3] 2比较P[2]a与P[4]a→ 相等 ⇒next[4] 21 3j 5:k next[4] 3比较P[3]b与P[5]a→ ❌ 不等 ⇒ 回溯k next[3] 2比较P[2]a与P[5]a→ ✅ 相等 ⇒next[5] 21 3⚠️ 错注意此时k2P[k]P[2]aP[5]a确实相等 →next[5] 21 3❌ 但前面手动枚举得next[5]1矛盾→发现错误手动枚举有误重审j5子串ababaa✅ 重新严格分析ababaa长度6索引0~5的真前后缀所有真前缀长度1~5a,ab,aba,abab,ababa所有真后缀长度1~5a,aa,baa,abaa,babaa公共子串仅a→ 长度 1aa是后缀但前缀中无aaaba是前缀但后缀中aba出现在位置2~4 →ababaa[2:5]aba是后缀吗后缀必须从末尾开始ababaa的后缀是len1:a索引5len2:aa索引4~5len3:baa索引3~5len4:abaa索引2~5len5:babaa索引1~5→aba不在后缀列表中所以最长公共只有a✅ 回到递推j5时k next[4] 3P[3]b ≠ P[5]a→k next[3] 2P[2]a P[5]a→next[5] 2 1 3但实际应为1❌ 问题出在next[j]定义的是P[0..j-1]的最长公共前后缀长度而非P[0..j] 正确理解关键next[j]对应的是模式串前 j 个字符P[0..j-1]长度为 j的最长真前后缀长度。所以j是子串长度不是末尾下标标准定义严蔚敏《数据结构》next[j]表示当模式中第j个字符与主串不匹配时模式串应跳到第next[j]个字符继续匹配。其中j从 0 开始next[0] -1next[1] 0next[j]j≥1对应P[0..j-1]的最长公共前后缀长度。因此计算next数组时列标题 j 表示“前 j 个字符”即j前j个字符子串 P[0…j-1]长度最长真前后缀长度next[j]0“”空0—定义为-1-11“a”10单字符无真前后缀02“ab”2003“aba”3“a” → 114“abab”4“ab” → 225“ababa”5“aba” → 336“ababaa”6“a” → 11✅ 所以next数组共7 个值j0 到 6对应模式串长度 0~6。题目中模式串ababaa长度为 6 → 我们需求next[0]到next[6]。✔️ 正确递推j 从 0 到 6next[0]-1next[0] -1j1:knext[0]-1→next[1]0j2:knext[1]0P[0]a,P[1]b→a≠b→knext[0]-1→next[2]0j3:knext[2]0P[0]a,P[2]a→ 相等 →next[3]011j4:knext[3]1P[1]b,P[3]b→ 相等 →next[4]112j5:knext[4]2P[2]a,P[4]a→ 相等 →next[5]213j6:knext[5]3P[3]b,P[5]a→ ❌ →knext[3]1P[1]b≠a→knext[1]0P[0]aP[5]a→next[6]011✅ 最终next数组j0 到 6[-1, 0, 0, 1, 2, 3, 1] 验证主串匹配时若j6处失配即已匹配前6字符ababaa则模式串右移至next[6]1即从P[1]b开始比对跳过已知公共a正确# Python 验证代码标准KMP next生成defget_next(pattern):nlen(pattern)nxt[-1]*(n1)# nxt[0..n]j,k0,-1whilejn:ifk-1orpattern[j]pattern[k]:j1k1nxt[j]kelse:knxt[k]returnnxtprint(get_next(ababaa))# 输出[-1, 0, 0, 1, 2, 3, 1]✅ 结论模式串ababaa的next数组为next [-1, 0, 0, 1, 2, 3, 1]共7个元素下标06对应前06个字符