**数据结构与算法核心知识点清单**，覆盖了本科《数据结构》《算法设计与分析》课程的主要内容，适用于考研复习、面试准备或系统性知识梳理
数据结构与算法核心知识点清单，覆盖了本科《数据结构》《算法设计与分析》课程的主要内容，适用于考研复习、面试准备或系统性知识梳理。以下是对各条目的简明归纳与关键要点提示：
- 线性表：顺序表（随机存取O(1)，插入/删除O(n)）；链表（单/双/循环，插入/删除O(1)但需定位O(n)）
- 栈：后进先出（FILO），典型应用：括号匹配、函数调用、后缀表达式求值（操作数入栈，遇运算符弹两数计算后压栈）
- 队列：先进先出（FIFO）；循环队列用
(rear+1)%MaxSize == front判满，避免假溢出 - 串：KMP算法通过预处理模式串得
next[]数组（或nextval[]），实现主串一趟扫描，时间复杂度 O(n+m) - 数组：行优先（C语言）：
addr[i][j] = base + (i×n + j)×size；列优先（Fortran）：base + (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(n+e)，遍历高效）
- 图遍历：DFS（递归/栈，解决连通性、环检测）；BFS（队列，解决单源最短路径（无权图）、层序遍历）
- 最小生成树（MST）：Prim（类似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] = -1）next[1] = 0（单字符无真前后缀）- 对
j ≥ 2，next[j]=P[0..j-1]的最长真前后缀长度
✅ 模式串P = "ababaa"，下标从 0 开始：
| j | P[j] | 子串 P[0…j] | 真前缀集合（非空、不等于全串） | 真后缀集合 | 最长相等前后缀 | next[j] |
|---|---|---|---|---|---|---|
| 0 | ‘a’ | “a” | ∅ | ∅ | — | -1 |
| 1 | ‘b’ | “ab” | {“a”} | {“b”} | 无公共 → 长度 0 | 0 |
| 2 | ‘a’ | “aba” | {“a”,“ab”} | {“a”,“ba”} | “a” → 长度1 | 1 |
| 3 | ‘b’ | “abab” | {“a”,“ab”,“aba”} | {“b”,“ab”,“bab”} | “ab” → 长度2 | 2 |
| 4 | ‘a’ | “ababa” | {“a”,“ab”,“aba”,“abab”} | {“a”,“ba”,“aba”,“baba”} | “aba” → 长度3 | 3 |
| 5 | ‘a’ | “ababaa” | {“a”,“ab”,“aba”,“abab”,“ababa”} | {“a”,“aa”,“baa”,“abaa”,“babaa”} | 公共：“a” → 长度1 | 1 |
🔍逐位详细推导（核心方法：利用已知 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 到 5）：
j = 0:next[0] = -1（约定）j = 1:k = next[0] = -1→k == -1⇒next[1] = 0
j = 2:k = next[1] = 0- 比较
P[k]=P[0]='a'与P[2]='a'→ 相等 ⇒next[2] = k+1 = 1
j = 3:k = next[2] = 1- 比较
P[1]='b'与P[3]='b'→ 相等 ⇒next[3] = 1+1 = 2
j = 4:k = next[3] = 2- 比较
P[2]='a'与P[4]='a'→ 相等 ⇒next[4] = 2+1 = 3
j = 5:k = next[4] = 3- 比较
P[3]='b'与P[5]='a'→ ❌ 不等 ⇒ 回溯：k = next[3] = 2 - 比较
P[2]='a'与P[5]='a'→ ✅ 相等 ⇒next[5] = 2+1 = 3？
⚠️ 错！注意：此时k=2，P[k]=P[2]='a'，P[5]='a'，确实相等 →next[5] = 2+1 = 3？
❌ 但前面手动枚举得next[5]=1！矛盾？→发现错误：手动枚举有误！重审j=5子串"ababaa"
✅ 重新严格分析"ababaa"（长度6，索引0~5）的真前后缀：
- 所有真前缀（长度1~5）：
"a","ab","aba","abab","ababa" - 所有真后缀（长度1~5）：
"a","aa","baa","abaa","babaa" - 公共子串：仅
"a"→ 长度 =1
（"aa"是后缀，但前缀中无"aa"；"aba"是前缀，但后缀中"aba"出现在位置2~4 →"ababaa"[2:5]="aba"，是后缀吗？后缀必须从末尾开始！"ababaa"的后缀是：- len1:
"a"（索引5） - len2:
"aa"（索引4~5） - len3:
"baa"（索引3~5） - len4:
"abaa"（索引2~5） - len5:
"babaa"（索引1~5）
→"aba"不在后缀列表中！所以最长公共只有"a"）
- len1:
✅ 回到递推：j=5时
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] = -1，next[1] = 0，next[j]（j≥1）对应P[0..j-1]的最长公共前后缀长度。
因此，计算next数组时，列标题 j 表示“前 j 个字符”，即：
| j（前j个字符） | 子串 P[0…j-1] | 长度 | 最长真前后缀长度 | next[j] |
|---|---|---|---|---|
| 0 | “”（空） | 0 | —（定义为-1） | -1 |
| 1 | “a” | 1 | 0（单字符无真前后缀） | 0 |
| 2 | “ab” | 2 | 0 | 0 |
| 3 | “aba” | 3 | “a” → 1 | 1 |
| 4 | “abab” | 4 | “ab” → 2 | 2 |
| 5 | “ababa” | 5 | “aba” → 3 | 3 |
| 6 | “ababaa” | 6 | “a” → 1 | 1 |
✅ 所以next数组共7 个值（j=0 到 6），对应模式串长度 0~6。
题目中模式串"ababaa"长度为 6 → 我们需求next[0]到next[6]。
✔️ 正确递推（j 从 0 到 6，next[0]=-1）：
next[0] = -1j=1:k=next[0]=-1→next[1]=0j=2:k=next[1]=0，P[0]=='a',P[1]=='b'→'a'≠'b'→k=next[0]=-1→next[2]=0j=3:k=next[2]=0，P[0]=='a',P[2]=='a'→ 相等 →next[3]=0+1=1j=4:k=next[3]=1，P[1]=='b',P[3]=='b'→ 相等 →next[4]=1+1=2j=5:k=next[4]=2，P[2]=='a',P[4]=='a'→ 相等 →next[5]=2+1=3j=6:k=next[5]=3，P[3]=='b',P[5]=='a'→ ❌ →k=next[3]=1，P[1]=='b'≠'a'→k=next[1]=0，P[0]=='a'==P[5]=='a'→next[6]=0+1=1
✅ 最终next数组（j=0 到 6）：[-1, 0, 0, 1, 2, 3, 1]
📌 验证：
- 主串匹配时，若
j=6处失配（即已匹配前6字符"ababaa"），则模式串右移至next[6]=1，即从P[1]='b'开始比对，跳过已知公共"a"，正确！
# Python 验证代码（标准KMP next生成）defget_next(pattern):n=len(pattern)nxt=[-1]*(n+1)# nxt[0..n]j,k=0,-1whilej<n:ifk==-1orpattern[j]==pattern[k]:j+=1k+=1nxt[j]=kelse:k=nxt[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个字符）