你已经会用代码处理一些数据，但当数据越来越多、操作越来越复杂时，问题会变成：怎样保存，才能更快找到？怎样组织，才能方便插入、删除或追踪关系？同一个问题换一种结构，程序为什么会快很多？数据结构研究的正是这些问题。
这门课不是“背几个排序算法”。你需要从实际问题中抽象出数据之间的关系，选择存储方式，设计操作，并分析时间、空间代价。理解一个结构，至少要同时回答四件事：元素怎样关联、实际怎样存储、操作怎样实现、代价与限制是什么。
在 408 中，本科目的分值为 45 分，占 30%。常见题型是 11 道选择题和 2 道综合应用题；综合题的具体分值、题材和组合不能固定预测。
学之前，先准备什么？
建议先掌握 C 语言的数组、指针、结构体、函数、循环、递归，以及内存分配和释放的基本使用。需要能读懂 p->next、能区分“节点本身”与“指向节点的指针”、能跟踪函数调用时参数与局部变量的变化。
会用 C++ 容器很有帮助，但不能用“我知道调用哪个库函数”代替底层结构理解。考试大纲要求能够用 C 或 C++ 设计与实现算法；最终答题仍应遵循题目给出的接口和表达要求。
先修补课应以解决当前障碍为界：不会指针，就结合链表练；不会递归，就结合二叉树遍历练。不建议为“准备好再学数据结构”无限延长语言课程。
知识地图：先看结构，再学操作
下表按照考试大纲的七个一级模块整理；“串”单独编为一章，因此它与大纲“查找”中的字符串模式匹配形成交叉映射。
| 大纲模块 | 必须理解的主干 | 学完要能完成的任务 | 本站章节 |
|---|---|---|---|
| 基本概念 | 逻辑结构、存储结构、基本操作；算法与复杂度 | 比较同一操作在不同结构中的代价；分析循环、递归的数量级 | 基本概念 |
| 线性表 | 顺序表、单链表及相关链式结构；插入、删除、合并 | 画出指针修改前后关系，独立写出边界完整的基本操作 | 线性表 |
| 栈、队列和数组 | 后进先出、先进先出、循环队列；数组地址和特殊矩阵压缩 | 手工模拟入栈出栈；判断队空队满；推导下标与地址 | 栈、队列和数组 |
| 树与二叉树 | 性质、存储、遍历、线索、树和森林；哈夫曼、并查集、堆 | 根据遍历分析结构，写递归，说明结构约束与应用 | 树与二叉树 |
| 图 | 邻接矩阵、邻接表等；DFS、BFS、最小生成树、最短路径、拓扑、关键路径 | 手算状态变化，区分每种算法的问题前提和输出目标 | 图 |
| 查找 | 顺序、分块、折半；BST、AVL、红黑树；B/B+树、散列；模式匹配 | 判断使用条件，计算查找代价，追踪冲突处理和字符串匹配 | 查找；模式匹配见串 |
| 排序 | 插入、冒泡、选择、希尔、快速、堆、归并、基数及外部排序 | 手算一趟结果，比较稳定性、复杂度、存储和应用约束 | 排序 |
表中的模块范围来自考试大纲“数据结构”部分；具体算法实现细节与复杂度的计量前提，以教材和题目条件为准。
怎样学：每个结构做完一张“四格卡”
**第一格：结构。**画出逻辑关系和存储形式。线性表不是只能用数组，树不是只能用链式结构；逻辑关系与存储实现要分开思考。
**第二格：操作。**不用看答案，手工执行插入、删除、遍历或查找，记录关键变量。操作失败时，先检查结构不变量有没有被破坏。
**第三格：算法。**独立写出核心过程，再用空输入、单元素、重复元素、边界位置等小例子检查。算法题可以按“思路 → 实现 → 复杂度 → 边界”组织答案，不以代码长短衡量质量。
**第四格：代价。**说明复杂度是最坏、平均还是特定输入下的结果；说明空间代价有没有算入辅助数组或递归栈。不要只记一个脱离前提的 O( )。
这套练法是教学建议。MIT 6.006 中的数据结构、排序、散列和图算法相关章节可按需选读。
基础、强化、真题阶段分别做什么？
基础阶段用小规模例子建立概念：每学一个结构，先手算，再写最小实现，随后做对应章节题。开始接触综合题时不必追求一遍写出最优解，先把正确性和边界写清楚。
强化阶段按问题类型重组：线性结构操作、树与递归、图算法条件、查找与排序比较。对做错的题不只记录正确选项，要记录“我漏看了什么前提”“哪一步状态更新错了”。
真题阶段逐步加入时间限制。对算法题，先建立可行解，再检查题目对时间和空间的要求。看过解析的题可以用来复习，但不应再把重做分数当作未见题能力。
常见误区
“链表插入一定是 O(1)”缺少前提。已知插入位置的相关指针时，改链接可以很快；如果还需要从头查找位置，总代价必须包含查找过程。
“算法运行正确一个样例，就说明正确”也不成立。你还需要检查边界与结构性质，例如删除头结点、处理重复值、空树返回、图不连通等。
“看懂动画就会写算法”容易高估掌握程度。动画适合建立直觉，最终还要关掉演示，自己画状态、写步骤和检查代码。
这些是用于自检的教学例子，不是对考试原题或命题频率的统计判断。
入门自测与答案
**问题 1：**在单链表中，给定某个节点的前驱指针后插入一个新节点，与只给定待插入的位置序号，有什么代价差别？
参考思路：前者可直接进行局部链接修改；后者通常还需要遍历查找前驱。分析复杂度时，应明确是否已经得到位置。
**问题 2：**一个程序为了遍历 n 个元素额外申请了一个 n 长度数组，能否称其辅助空间为 O(1)？
参考思路：不能，该数组的空间随 n 增长，通常按 O(n) 计；输入本身和额外工作空间要区分。
**问题 3：**已知一棵树的某一种遍历结果，是否总能唯一恢复这棵树？
参考思路：不能。应结合树的类型、节点是否重复、给出了哪些遍历以及其他约束判断，不能机械套重建结论。
完成本科目的最低验收
参考资料
MIT OpenCourseWare 6.006 Introduction to Algorithms（MIT 课程团队），可选读数据结构、复杂度、排序、散列和图算法相关章节。