997 字
3 分钟
考研专业课学习记录2026-06-22
考研专业课学习记录 | 2026-06-22
今日学习内容
总学习时长约3小时，核心覆盖数据结构模块的KMP字符串匹配算法、next与nextval数组优化、数组的矩阵压缩存储方法、栈与队列的经典应用场景。
AI知识点带复盘
1. KMP字符串匹配算法
考研408字符串匹配模块的核心高频考点，相较于暴力匹配的O(n*m)时间复杂度，KMP通过利用已匹配的前缀信息避免主串指针回溯，将整体复杂度优化至O(n+m)。
- next数组：用于记录模式串每个位置
j对应的最长相等前后缀长度（不同教材存在下标偏移定义差异），手工计算时需先求解各子串的最长公共前后缀长度，再按照规则推导数组值。 - nextval数组：next数组的优化版本，用于解决当模式串当前字符与匹配失败的主串字符相等时的重复无效匹配问题：若
P[j] == P[next[j]]，则nextval[j] = nextval[next[j]]，否则nextval[j] = next[j]，可进一步压缩匹配次数。
2. 数组的矩阵压缩存储
针对特殊矩阵的存储空间优化方法，是408数组模块必考考点：
- 对称矩阵：利用元素对称特性仅存储下三角（含对角线）元素，通过下标映射公式将二维数组压缩至一维数组，可节省约50%存储空间。
- 三角矩阵：分为上三角、下三角矩阵，仅存储非零三角区域元素，剩余区域可通过公式直接计算或统一赋值。
- 稀疏矩阵：非零元素远少于总元素的矩阵，主流存储方式为三元组表（存储行、列、值）和十字链表，其中三元组表适合静态存储，十字链表适合动态增删非零元素，考研常考察三元组表的转置、快速转置算法。
3. 栈与队列的应用
基于先进后出、先进先出的特性适配不同业务场景：
- 栈的经典应用：括号匹配校验、中缀转后缀表达式、后缀表达式求值、递归调用实现、函数调用上下文保存。
- 队列的经典应用：二叉树层次遍历、循环队列实现、操作系统进程调度、打印机任务队列，考研常考察表达式求值步骤、循环队列队满/队空判断条件。
问题与反思
- 手工计算nextval数组时，仍容易混淆优化条件的触发场景，需结合更多例题巩固推导逻辑；
- 稀疏矩阵十字链表的结点结构和遍历逻辑尚未完全熟练，需结合真题练习加深理解；
- 栈与队列的细分应用场景适配逻辑仍需梳理，避免在选择题中混淆数据结构选择。
收获与总结
- 完全掌握KMP算法核心原理，能够独立手工推导模式串的next与nextval数组，明确其相较于暴力匹配的优化逻辑；
- 清晰梳理特殊矩阵压缩存储的方法和下标映射公式，可准确计算不同存储方式下的元素存储位置；
- 系统梳理栈与队列的经典应用场景，能够根据问题需求快速匹配合适的数据结构；
- 明确了408数据结构模块中字符串、数组、栈与队列章节的高频考察形式和出题方向。
💡 碎碎念：踏实吃透每一个知识点！
文档内容由 AI 辅助生成
分享
如果这篇文章对你有帮助，欢迎分享给更多人！
考研专业课学习记录2026-06-22
https://elysiaweb.vercel.app/posts/408/6-22/ 部分信息可能已经过时
相关文章 智能推荐