速成 · 数据结构与程序设计

选数据结构，就是在为不同操作分配成本。复习时先问一句：为了让最常用的操作更容易，数据应该怎样摆放？ C 语言负责把这个选择真正落到内存和指针上。

例如，数组把元素连续摆放，所以按下标访问很快；链表把元素分散摆放并用指针相连，所以插入、删除更灵活；栈限制只能从一端进出，正好保存“尚未完成的现场”；队列按先来后到取数据，适合排队和分层搜索。树和图不是额外背出来的名词，而是对“一对多”和“多对多”关系的直接表达。

结构选择表

问题形态	常用结构	核心操作	常见复杂度
已知位置取元素	顺序表、数组	按下标访问	$O(1)$
频繁局部插入、删除	链表	改相邻指针	已知位置时 $O(1)$
后进先出、嵌套过程	栈	push / pop	$O(1)$
先进先出、逐层扩展	队列	enqueue / dequeue	$O(1)$
层级关系	树、二叉树	遍历、查找、插入	与树高有关
网络关系	图	DFS、BFS、路径、生成树	与顶点数和边数有关
静态有序表查找	折半查找	每次排除一半	$O(\log n)$
关键字直接定位	散列表	散列与冲突处理	平均接近 $O(1)$
整理无序数据	各类排序	比较、移动、划分或归并	通常 $O(n^2)$ 或 $O(n\log n)$

做题先抓三个层次

1. 逻辑结构：元素之间究竟是线性、一对多，还是多对多？
2. 存储结构：这些关系在内存里用连续地址、指针、索引还是散列地址表达？
3. 操作不变量：算法每走一步，什么性质始终成立？

第三点最重要。链表插入时要保证旧链不断；循环队列要始终说清 front、rear 各指哪里；二叉搜索树要保持“左小右大”；Dijkstra 算法每轮确定的点，其最短距离以后不再改变；插入排序每一趟结束后，前缀已经有序。能说出不变量，就不必死背代码。

复杂度的最短复习法

• 顺序执行的语句取较大项；嵌套循环通常相乘。
• 循环变量每次乘或除一个常数，通常是 $O(\log n)$。
• 递归既要看调用次数，也要看每层额外工作。
• 图的邻接矩阵遍历通常是 $O(|V|^2)$；邻接表遍历通常是 $O(|V|+|E|)$。
• 二叉搜索树、堆等树结构的操作与树高 $h$ 有关；平衡时 $h=O(\log n)$，退化时可能是 $O(n)$。

必须会手推的过程

线性表、栈与队列

• 单链表插入先接后半段，再接前半段：q->next = p->next; p->next = q;。
• 中缀转后缀时，操作数直接输出；运算符按优先级弹栈；右括号弹到左括号为止。
• 循环队列若牺牲一个单元区分空和满，则满的条件常写成 (rear + 1) % M == front。

树

• 前序：根、左、右；中序：左、根、右；后序：左、右、根；层序用队列。
• 已知前序和中序：前序首元素定根，中序把左右子树分开，再递归。
• 二叉搜索树删除有三个情况：叶结点、只有一个孩子、两个孩子；最后一种通常用中序前驱或后继替换。
• 哈夫曼树每次取权值最小的两棵树合并，得到带权路径长度最小的前缀编码树。

图

• DFS 一条路走到底，天然适合递归或栈；BFS 一层层扩展，必须用队列。
• Prim 每次从“已选顶点集合”向外挑最轻的边；Kruskal 按边权从小到大尝试，不能形成环。
• Dijkstra 每轮确定一个当前距离最小的未确定顶点，再用它松弛邻边；不能直接处理负权边。
• 拓扑排序反复删除入度为零的顶点；最后还有顶点却没有入度为零的点，说明有环。

查找与排序

• 折半查找只适用于有序、可随机访问的数据。
• 散列题先算地址，再按题目指定的开放地址法或链地址法处理冲突。
• 插入、冒泡是稳定排序；简单选择、快速、堆、希尔通常不稳定。
• 插入、选择、冒泡最坏为 $O(n^2)$；归并、堆为 $O(n\log n)$；快速排序平均 $O(n\log n)$、最坏 $O(n^2)$。

程序题怎么下手

先写清输入、输出和边界，再选结构。不要一看到题就敲代码。

1. 用一个很小的例子手推目标过程。
2. 写下结构中每个字段的含义，尤其是指针和下标。
3. 明确空结构、单元素、头尾位置和重复关键字怎样处理。
4. 把重复动作封装成函数，再写主流程。
5. 用断点或打印检查“不变量第一次被破坏”的位置，而不是只看最终错误结果。

源材料中的期中提醒特别强调：链表指针顺序不确定时应在草稿纸上画图；出现 SIGSEGV 时先查野指针和越界，出现 SIGFPE 时先查除数是否为零，出现 SIGABRT 时先查错误释放和堆越界。这些不是调试技巧的边角料，而是本课程序题能否做完的基本功。

最后五分钟检查

• 指针使用前是否初始化？申请的内存是否判空？
• 字符串是否保留 \0？数组下标是否越界？
• 链表头结点、空表、首尾结点是否单独处理？
• 栈、队列的空满条件是否与下标约定一致？
• 递归是否有终止条件，而且问题规模真的在缩小？
• 图是否可能不连通？最短路径是否存在负权边？
• 排序题问的是过程、复杂度、空间，还是稳定性？

如果这些问题都能回答，这门课就不再是一堆零散代码，而是一套“结构约束操作、操作决定代价”的方法。