DS-1/2 线性结构（线性表、栈、队列、数组、串）

这一部分为什么存在？

计算机处理的数据，最朴素的组织关系是“一个挨一个”（一对一的线性关系）：学生名单、成绩序列、字符序列。要让它能被程序高效使用，必须回答：

1. 怎么衡量“高效”（DS-0）：机器有快有慢，不能直接比秒数 → 用基本操作执行次数随问题规模 $n$ 的增长趋势（时间复杂度）来度量。这是全课程的评价标尺。
2. 线性关系怎么存（DS-1）：内存只有两种基本用法——连续一片（顺序表）或分散加指针（链表）。两种存法直接决定了每种操作的代价：顺序表随机访问 O(1) 但插删要搬元素 O(n)；链表插删 O(1)（已找到位置时）但定位要顺链爬 O(n)。这是数据结构第一课的核心权衡：存储结构决定操作代价。
3. 限制操作位置会怎样（DS-2）：把线性表的操作限制在端点，就得到两个极有用的特化结构——栈（后进先出，一端操作）和队列（先进先出，两端操作）。限制不是削弱而是换取语义：栈天然匹配“最近未决”的场景（递归、括号、表达式、撤销），队列天然匹配“先来先服务”（缓冲、BFS、调度）。

flowchart TD
    A["一对一的线性关系"] --> B["顺序存储：顺序表<br/>随机访问 O(1) / 插删 O(n)"]
    A --> C["链式存储：链表<br/>定位 O(n) / 插删 O(1)"]
    C --> C1["单链表 / 双链表 / 循环链表 / 静态链表"]
    A --> D["限制操作位置"]
    D --> E["栈 LIFO：括号匹配 / 表达式求值 / 递归"]
    D --> F["队列 FIFO：循环队列 / 双端队列 / BFS"]
    A --> G["数组：特殊矩阵压缩存储"]
    A --> H["串：朴素匹配 → KMP"]

核心概念：

1. 顺序表 vs 链表的操作代价（一切比较的源头）

真题：2013-1（两升序链表合并为降序，头插法 $O(\max(m,n))$）；2016-1（静态链表：数组下标当指针，链接地址推理）；2016-2、2023-2（双向链表插删的语句顺序：先接好新结点的两侧，再断旧链——写反就断链）；2021-1（循环链表尾指针删首元素）。

2. 栈的三大应用（选择题高频）

• 括号匹配：遇左括号入栈，遇右括号弹栈比对，串空栈空则匹配。
• 中缀 → 后缀表达式：操作数直接输出；操作符与栈顶比优先级，高于则入栈、不高于则弹栈输出再比；左括号入栈，右括号弹到左括号。2012-2（转换中栈内操作符最大个数 5）、2014-2（扫描到 f 时栈的内容）——模拟一遍栈变化即可。
• 后缀表达式求值：操作数入栈，遇操作符弹两个运算再压回（2018-1：双栈模型调用 3 次 F 后的栈顶值）。
• 递归与栈：函数调用的返回地址、参数、局部变量都压在系统栈上——“用非递归重写递归程序时必须用栈”（2017-2 I 正确）；这也解释了 DS-3 中遍历递归算法的本质。

3. 循环队列的实现要点

牺牲一个存储单元区分空满（为什么不利用全部单元：若 front==rear 既表示空又表示满会歧义；替代方案是加计数器或标志位）。入队 rear=(rear+1)%n、出队 front=(front+1)%n。判空判满条件严格依赖题目对 front/rear 的定义——2011-3 与 2014-3 两题指针定义不同，答案形式完全不同，这是本模块最经典的“读题陷阱”。

4. KMP：为什么朴素匹配慢、next 怎么救

朴素匹配每次失配主串指针 i 回退到起点+1，最坏 $O(nm)$。KMP 的关键观察：失配时主串已扫描过的部分与模式串前缀是已知的，如果模式串前 $j$ 个字符存在长度 $k$ 的相等前后缀，则主串指针 i 不必回退，只需把模式串向右滑到“前缀对齐后缀”的位置（$j \leftarrow next[j]$）。i 单调不减 → $O(n+m)$。

• 2015-8：i=j=5 失配，模式串 "abaabc" 的 next[5]=2 → 下次 i=5、j=2。
• 2019-9：给定主串模式串，数总比较次数（按 i 不退、j 按 next 跳模拟）。

next 数组本身只需识别思想（近年考应用而非手算大表）；手算时记住“最长相等前后缀长度 +1”的定义约定，注意个别教材从 0 开始编号，以题面为准。

5. 特殊矩阵压缩存储

对称矩阵、三对角矩阵、稀疏矩阵（三元组表/十字链表）：把 $n \times n$ 存成约一半或对角线带，地址映射公式 $k = i(i-1)/2 + j - 1$（下三角、从 1 开始）——只需识别思想 + 会代公式。

顺序表 vs 链表（数据结构第一易混对）：为什么易混——都是“线性表”。本质区别——物理连续性决定了：随机访问 vs 顺序访问、插删搬元素 vs 插删改指针、空间紧凑 vs 指针开销。一道题的判断：操作以按下标存取为主 → 顺序表；以任意位置插删为主且规模不定 → 链表。

栈 vs 队列：为什么易混——都是操作受限线性表。本质区别——LIFO 撤销最近 vs FIFO 保持次序。判别线索：题目有“嵌套、回退、最近未配对”→ 栈；“排队、缓冲、按到达顺序”→ 队列。

单链表 vs 双链表 vs 循环链表：双链表用空间换“前驱可达”（删结点不必先找前驱）；循环链表从任意点可遍历全表（尾指针既表头又表尾）。

形态一：出栈/出队序列合法性：2009-2（栈容量至少 3）、2010-1（附加限制的不可能序列）、2011-2（以 d 开头的序列 4 个）、2013-2（$p_2=3$ 时 $p_3$ 可能个数）、2017-2、2018-2（队列+栈混合输出序列）、2022-2（in/out 可能互为倒序）。

形态二：栈应用模拟：2012-2、2014-2（中缀转后缀栈状态）、2018-1（双栈求值）。

形态三：队列判空判满与指针：2011-3、2014-3（按题面定义推条件）。

形态四：链表操作语句：2016-1/2、2021-1、2023-2。

形态五：KMP：2015-8、2019-9。

形态六（与 DS-7 衔接）：链表代码大题：2009-42（倒数第 k 个，双指针）、2012-42（共同后缀，先对齐长度再同步走）、2015-41（绝对值去重，借辅助数组标记）、2019-41（链表重排：找中点 + 反转后半 + 合并）——套路详见 DS-7。

做题触发词：看到“front/rear 指向…”→ 先把题面定义圈出来再写条件；看到“倒数第 k”→ 双指针间距 k；看到“中缀/后缀”→ 画栈；看到“删除双向链表结点”→ 四句指针赋值顺序。

来源：真题markdown/2009-2024统考真题.md 对应题号。

• 向前依赖：无（DS 起点）。
• 向后引出：
  • 栈是递归与 DFS 的引擎、队列是 BFS 与层序遍历的引擎 → DS-3 树、DS-4 图；
  • 顺序表 + 有序 → 折半查找（DS-5）；顺序表是多数排序算法的舞台（DS-6）；
  • 链表操作是代码题第一大户 → DS-7；
  • 跨学科：队列 → OS 就绪/阻塞队列、I/O 缓冲；栈 → 函数调用栈（CO-2/OS-1）；KMP/串 → 网络报文处理（X-8）。

1. 为什么用复杂度而不是秒数衡量算法？
2. 线性关系的两种存法各用什么代价换什么？
3. 顺序表插删为什么是 O(n)？链表插删 O(1) 的前提是什么？
4. 单链表为什么常设头结点？
5. 栈和队列分别限制出了什么语义？各自匹配什么场景？
6. 循环队列为什么要牺牲一个单元？判空判满为什么要看题面定义？
7. 中缀转后缀时栈里放什么？遇到右括号做什么？
8. 递归为什么等价于栈？（调用信息压栈）
9. 朴素模式匹配慢在哪？KMP 为什么 i 不用回退？next[j] 的含义？
10. 双向链表删一个结点，指针赋值顺序为什么不能乱？
11. 链表代码题的通用套路有哪些？（双指针、反转、归并——接 DS-7）