数据结构 · 2027 考研计算机 408

第 3 章　栈、队列和数组（含压缩存储）

目标院校：四川大学 / 电子科技大学　|　建议用时：概念 3 小时 + 例题练习 4 小时

本章地位：栈、队列和数组是 408 数据结构的选择题高发区，历年稳定贡献 2～4 道小题，且套路极其固定：出栈序列合法性、循环队列判满与元素计数、矩阵压缩存储下标换算三大件反复出现。本章把每个套路都配上「充要条件 + 具体数值验证」，所有地址公式一律代入小数值核对，例题覆盖 2009—2021 年真题的全部题型变体。学完标准：任给一个出栈序列 10 秒内判定、任给 front/rear 5 秒内报出元素个数、任给矩阵元素 30 秒内算出压缩地址。

3.1　栈：操作受限的线性表

定义栈（Stack）是只允许在一端（称为栈顶，top）进行插入和删除操作的线性表。插入称为进栈 / 入栈（push），删除称为出栈 / 弹栈（pop）；另一端称栈底。特点：后进先出（LIFO，Last In First Out）。
一句话记忆栈 = 运算受限的线性表（限制的是「位置」，不是「元素类型」）。n 个不同元素依次进栈，并非只有一种出栈序列——因为「进栈 / 出栈可以交替进行」，某元素进栈后可以停留，等后面元素进完再出。

3.1.1 顺序栈：top 的两种约定

用一维数组 data[0..MaxSize-1] 存栈，附整型 top 指示栈顶位置：

// 顺序栈的存储结构与进栈 / 出栈（top 指向栈顶元素，初始 top = -1）

#define MaxSize 50
typedef struct {
    int data[MaxSize];
    int top;                        // 栈顶指针
} SqStack;

void InitStack(SqStack &S) { S.top = -1; }

bool Push(SqStack &S, int x) {
    if (S.top == MaxSize - 1)       // 栈满，上溢 overflow
        return false;
    S.data[++S.top] = x;            // 指针先加 1，再存入元素
    return true;
}

bool Pop(SqStack &S, int &x) {
    if (S.top == -1)                // 栈空，下溢 underflow
        return false;
    x = S.data[S.top--];            // 先取元素，指针再减 1
    return true;
}
易错不同教材对 top 的初始值有两种约定，判断题第一步先看清题目用哪一种：
  1. 约定一（严蔚敏教材、本页代码）：top 指向栈顶元素，初始 \(-1\)（或指向 \(-1\) 处）；栈空 top == -1，栈满 top == MaxSize-1；进栈「先 ++ 再存」，出栈「先取再 −−」。
  2. 约定二（部分教材）：top 指向下一个空位，初始 \(0\)；栈空 top == 0；进栈「先存再 ++」，出栈「先 −− 再取」。
两种约定只差 1 的平移，做题时先统一翻译成约定一再动笔；题目问「栈中元素个数」，约定一下答案恰为 top+1。

3.1.2 共享栈与链栈

共享栈让两个栈共享一个数组 data[0..MaxSize-1]：栈 1 的栈底在数组低端，top1 初始 \(-1\)，向高地址生长；栈 2 的栈底在数组高端，top2 初始 \(MaxSize\)，向低地址生长。只有当 top1 + 1 == top2（两端相遇）才真溢出——两个栈的空间需求可以互补余缺。
链栈采用链式存储的栈：入栈即头插法建单链表（新结点成为新的表头），表头指针就是栈顶指针；出栈即从表头删除。优点：不存在栈满上溢（只要内存够），多个栈共享存储空间时链式最灵活；代价是每个结点多一个指针域。
① 顺序栈（约定一：top 指向栈顶元素，空栈 top = −1） a b c top = 2 栈底 data[0] 进栈：S.data[++S.top] = x 出栈：x = S.data[S.top--] ② 共享栈（两端向中间生长，top1 + 1 == top2 时栈满） p q u v top1 = 1 top2 = 6 栈 1 向中间生长 栈 2 向中间生长
图 3-1　顺序栈与共享栈：top 的指向决定判空判满条件；共享栈只有「中间无空格」（top1+1==top2）才溢出
考点对比顺序栈 vs 链栈：入栈 / 出栈时间都是 \(O(1)\)；顺序栈可能上溢但存取快、无指针开销，链栈不会上溢但每元素多耗一个指针域。「栈的插入删除只能在栈顶进行」对两种存储都成立；共享栈的判满条件（top1+1==top2）是选择题常客。

3.1.3 出栈序列：Catalan 数与合法性判断 高频考点

计数公式\(n\) 个不同元素按确定顺序进栈、进栈出栈交替进行，可能的出栈序列数为Catalan 数： \[ C_n=\frac{1}{n+1}\binom{2n}{n} \] 代入验证：\(C_1=\frac{1}{2}\binom{2}{1}=1\) ✓；\(C_2=\frac{1}{3}\binom{4}{2}=2\) ✓（12、21）；\(C_3=\frac{1}{4}\binom{6}{3}=5\) ✓；\(C_4=\frac{1}{5}\binom{8}{4}=\frac{70}{5}=14\) ✓；\(C_5=\frac{1}{6}\binom{10}{5}=42\) ✓。

n = 3 全枚举（进栈顺序 1、2、3）：合法 5 种——123（进 1 出 1，进 2 出 2，进 3 出 3）、132（出 1 后进 2、3 先出 3 再出 2）、213（进 1、2 先出 2 再出 1，再进 3 出 3）、231（出 2 后进 3 出 3、出 1）、321（全进完依次全出）；唯一不合法的是 312：3 先出说明 1、2 都还在栈中且 2 在 1 上方，接下来轮到 1 时栈顶是 2，矛盾。\(n=4\) 时 24 个排列中恰 14 个合法、10 个不合法，与 \(C_4\) 吻合 ✓。

充要条件出栈序列 \(p_1p_2\cdots p_n\) 合法 \(\Longleftrightarrow\) 序列中不存在下标 \(i\lt j\lt k\) 使得 \[ p_j\lt p_k\lt p_i \] （即不含「大—小—中」跨越反序）。直觉：值大者 \(p_i\) 反而先出，说明 \(p_j\)、\(p_k\) 当时都被压在 \(p_i\) 之下且 \(p_k\) 在 \(p_j\) 上方，轮到出 \(p_j\) 时必然先撞上 \(p_k\)，矛盾。
实战套路判断给定序列：模拟法最稳——按序列逐个要元素，需要的元素还没进栈就依次进栈到目标元素为止，再看栈顶是否恰是要出的元素；栈顶不是且目标已进过 → 不合法。检查 312 型反序只适合快速排除选择题选项。
例 1 真题风格　出栈序列合法性（2010 年真题原型）

元素 a、b、c、d、e、f 依次进栈，允许进栈与出栈交替进行，下列不可能的出栈序列是（　）
A. c b d a e f　B. a c e d b f　C. d c b a e f　D. e d c a b f

查看解答

D。逐项模拟：

A：进 a、b、c，出 c、b；进 d，出 d；出 a；进 e 出 e；进 f 出 f——得 c b d a e f ✓；

B：进 a 出 a；进 b、c 出 c；进 d、e 出 e、d、b；进 f 出 f ✓；

C：进 a、b、c、d，出 d、c、b、a；进 e 出 e；进 f 出 f ✓；

D：e 先出说明 a、b、c、d 已全部在栈中（d 在 c 上、c 在 b 上、b 在 a 上），出 e、d、c 之后栈顶是 b，下一个要出 a——栈顶不是 a 且 a 已进栈，不可能。

易错：D 中的反序「e、d、c、a、b」正含 312 型模式（取 e、a、b 三个位置：\(a\lt b\lt e\) 且 e 先出、a 后出、b 夹中间）。

例 2　出栈序列计数 + 合法性综合

1、2、3、4 依次进栈。(1) 可能的出栈序列共有多少种？(2) 序列 4 1 3 2 是否合法？(3) 若出栈序列的第一个元素是 4，这样的序列有多少种？

查看解答

(1) \(C_4=\frac{1}{5}\binom{8}{4}=14\) 种。

(2) 4 第一个出 ⇒ 1、2、3 全在栈中（3 在栈顶）；下一个要出 1，但栈顶是 3，不合法。

(3) 4 先出 ⇒ 1、2、3 已全部进栈，之后只能依次弹 3、2、1，序列唯一：4 3 2 1，共 1 种。验证：首元素为 n 时后续必递减，一般地首元素为 \(n\) 的合法序列恰 \(1=C_0\) 种（对应 Catalan 数递推的边界项）✓。

练习 1 高频考点

1、2、3、4 依次进栈，判断下列出栈序列是否合法：① 2 4 3 1；② 3 1 4 2；③ 1 4 3 2。

查看答案

① 合法：进 1、2 出 2；进 3、4 出 4、3、1。

② 不合法：出 3 后栈内自底向上为 1、2，下一个要出 1 而栈顶是 2（含 3、1、2 型反序：\(1\lt2\lt3\)，3 先出、1 后出、2 夹中间）。

③ 合法：进 1 出 1；进 2、3、4 出 4、3、2。

练习 2

(1) 5 个元素依次进栈，出栈序列共多少种？(2) n 个元素依次进栈，出栈序列的第一个元素恰为 \(n\) 的序列有多少种？

查看答案

(1) \(C_5=\frac{1}{6}\binom{10}{5}=\frac{252}{6}=42\) 种。

(2) 1 种：首出 \(n\) 意味着前 \(n-1\) 个全部压在栈中，此后只能按 \(n-1,n-2,\cdots,1\) 逆序弹出。

3.2　栈的应用：表达式

三种表达式按运算符与操作数的相对位置分：
  1. 中缀表达式：运算符在两个操作数中间（如 A+B*C），符合人的习惯，但依赖优先级与括号；
  2. 后缀表达式（逆波兰式）：运算符在两个操作数之后（如 ABC*+），无括号、无优先级歧义，求值只需一个操作数栈；
  3. 前缀表达式（波兰式）：运算符在两个操作数之前（如 +A*BC），从右往左扫描求值。

3.2.1 中缀 / 后缀 / 前缀互转（手算法）

例 3 方法　加括号法转换 A+B*(C-D)-E/F

将中缀表达式 A+B*(C-D)-E/F 分别转换为后缀式与前缀式。

查看解答
步骤操作结果
①按优先级完全加括号（先 \(-\) 括号内，再 \(\times\)，再 \(\div\)，最后最外层 \(-\)）\(\big((A+(B\times(C-D)))-(E\div F)\big)\)
②每个运算符移到本层括号之后，再删去所有括号后缀：ABCD-*+EF/-
③每个运算符移到本层括号之前，再删去所有括号前缀：-+A*B-CD/EF

以后缀为例逐层展开验证：\((C-D)\to CD-\)；\((B\times(C-D))\to BCD-*\)；\((A+\cdots)\to ABCD-*+\)；\((E\div F)\to EF/\)；最外层减号最后出现 → ABCD-*+EF/- ✓（前缀同理，运算符提前）。

套路总结：手算用「完全加括号 → 移运算符」；机算（下节）用运算符栈。后缀式看谁先算谁在前，前缀式相反。

3.2.2 后缀表达式求值（栈模拟）

例 4 高频考点　后缀表达式求值

求后缀表达式 3 4 5 * + 6 - 的值。

查看解答

规则：从左到右扫描，操作数进栈；遇运算符弹出栈顶两个数——先弹出的是右操作数——计算后把结果压回栈。

扫描项动作栈（底 → 顶）
3、4、5依次进栈3、4、5
*弹 5、4，算 \(4\times5=20\) 入栈3、20
+弹 20、3，算 \(3+20=23\) 入栈23
6进栈23、6
-弹 6、23，算 \(23-6=17\) 入栈17

最终栈中唯一元素 17 即结果。对照中缀验证：\((3+4\times5)-6=17\) ✓。

易错：减法、除法不满足交换律，「后弹的是左操作数」——若把 \(23-6\) 算成 \(6-23\) 全盘皆错。

3.2.3 中缀转后缀：运算符栈法（机算）

转换规则设一个运算符栈，从左到右扫描中缀式：① 操作数直接输出；② ( 进栈；③ ) 则依次弹栈输出直到遇 (（括号本身丢弃）；④ 运算符：把栈顶优先级不低于当前的运算符依次弹出输出（左结合时同级也弹），再将当前运算符进栈；⑤ 扫描完后把栈内剩余运算符全部弹出。优先级：\(\times\ \div\) 高于 \(+\ -\)，( 在栈内视为最低。
例 5 方法　A+B*(C-D)-E/F 全程栈状态表

用运算符栈法把 A+B*(C-D)-E/F 转为后缀式。

查看解答
读入动作运算符栈（底 → 顶）输出
A输出—A
+栈空，入栈+A
B输出+A B
*栈顶 + 低于 *，入栈+ *A B
(入栈+ * (A B
C输出+ * (A B C
-栈顶 ( 视为最低，入栈+ * ( -A B C
D输出+ * ( -A B C D
)弹 - 输出，弹 ( 丢弃+ *A B C D -
-弹 *、弹 + 输出，再入栈-A B C D - * +
E输出-A B C D - * + E
/栈顶 - 低于 /，入栈- /A B C D - * + E
F输出- /A B C D - * + E F
结束全部弹出—A B C D - * + E F / -

与例 3 手算结果一致 ✓。

易错① 同级运算符也要「先弹后压」（左结合）：第 10 步 - 之所以能把 + 弹出，就是因为 \(+\) 与 \(-\) 同级；若不弹，A+B-… 会错成 A+B…- 的乱序。② ( 入栈后优先级「降到最低」，保证括号内运算符不被提前弹出。③ 后缀转中缀反向操作：从左扫，遇运算符就把栈顶两个子式合并并加括号。
练习 3 易错

将中缀表达式 \((a+b)\times c-d\div(e+f)\) 转为后缀式与前缀式；并求 \(a=1\)、\(b=2\)、\(c=3\)、\(d=6\)、\(e=2\)、\(f=1\) 时的值。

查看答案

完全加括号：\(\big((a+b)\times c\big)-\big(d\div(e+f)\big)\)。后缀：ab+c*def+/-；前缀：-*+abc/d+ef。

求值：\((1+2)\times3=9\)，\(6\div(2+1)=2\)，结果 \(9-2=\)7。用后缀式复算：1、2、+ → 3；3、3、* → 9；6、2、1、+ → 3；6、3、\(\div\) → 2；9、2、− → 7 ✓。

练习 4 真题风格

（2009 年真题原型）中缀表达式 a*(b+c)-d 的后缀表达式是（　）
A. abc+*d-　B. abcd+*-　C. ab+c*d-　D. abc*+d-

查看答案

A。加括号 \(\big(a\times(b+c)\big)-d\)：\(b+c\to bc+\)，\(a\times\ \to abc*\)，最外层 \(-d\) 接在最后 → abc+*d-。用数值 \(a=2,b=1,c=3,d=4\) 验证：中缀 \(2\times4-4=4\)；后缀 2 1 3 + * 4 -：1+3=4，2×4=8，8−4=4 ✓。

3.3　队列：先进先出

定义队列（Queue）是只允许在表的一端（队尾，rear）插入、另一端（队头，front）删除的线性表，特点先进先出（FIFO）。队列的顺序存储直接用数组会出现假溢出：元素不断从队头出、队尾进，rear 很快顶到 MaxSize，但数组前部因出队空出的单元无法复用——此时队列实际元素并不多，却再也进不了队。

3.3.1 循环队列：判空判满三方案 高频考点

循环队列把一维数组逻辑上看成环：front、rear 到达数组末端后用取模绕回（\((Q.rear+1)\%M\)），从而消除假溢出。约定 front 指向队头元素、rear 指向队尾元素的下一空位。此时「front==rear」既可能是空也可能是满，必须用以下三方案之一区分：
方案队空条件队满条件备注
牺牲一个存储单元front==rear(rear+1)%M==front最常用；最多存 \(M-1\) 个元素
增设 size 变量size==0size==M不牺牲单元，元素个数直接读 size
增设 tag 标志front==rear 且 tag==0front==rear 且 tag==1tag 记录最近一次操作：出队置 0、进队置 1
元素个数公式循环队列中元素个数为 \[ (rear-front+M)\ \%\ M \] 代入 \(M=5\) 验证：front=0、rear=3 → \((3-0+5)\%5=3\) 个（位于 0、1、2）✓；front=3、rear=0（rear 已绕回）→ \((0-3+5)\%5=2\) 个（位于 3、4）✓；front==rear → 0 个（空）✓；牺牲单元方案队满时恰 \((M-1)\) 个 ✓。
例 6 真题风格　循环队列全过程计算

循环队列存于数组 A[0..4]（\(M=5\)），采用牺牲单元方案，初始 front=rear=0。① a、b、c、d 依次入队后的 front、rear 与元素个数？② 接着 a、b 出队、e、f 入队后又如何？③ 若某时刻 front=3、rear=0，队列中有几个元素？

查看解答

① 入队只动 rear：rear 依次 1、2、3、4。front=0、rear=4，个数 \((4-0+5)\%5=4\)；此时 \((4+1)\%5=0=front\) → 队满（该方案最多 \(M-1=4\) 个，e 无法再入）。

② 出队只动 front：front=1、2。再入 e：存入 A[4]，rear=\((4+1)\%5=0\)（绕回）；入 f：存入 A[0]，rear=1。front=2、rear=1，个数 \((1-2+5)\%5=4\)，\((1+1)\%5=2=front\) → 再次队满（见图 3-2）✓。

③ \((0-3+5)\%5=2\) 个（位于 3、4，rear 在位置 0 等待写入）✓。

状态①：a、b、c、d 入队后　front = 0，rear = 4 → (4+1)%5==front，队满 a b c d front=0 rear=4 01234 rear 取模绕回：rear=(rear+1)%5 状态②：a、b 出队，e、f 再入队后　front = 2，rear = 1 → (1+1)%5==front，仍队满 f c d e front=2 rear=1 rear 从 4 绕回 0 再到 1， 数组前部空间被复用，无假溢出
图 3-2　循环队列的取模绕回与判满（牺牲单元方案）：rear 追到 front 前一格（(rear+1)%M==front）即满

// 循环队列入队 / 出队（牺牲一个单元判满）

#define MaxSize 5
typedef struct {
    int data[MaxSize];
    int front, rear;              // rear 指队尾元素的下一空位
} SqQueue;

bool EnQueue(SqQueue &Q, int x) {
    if ((Q.rear + 1) % MaxSize == Q.front)   // 队满
        return false;
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MaxSize;         // 取模推进，逻辑成环
    return true;
}

bool DeQueue(SqQueue &Q, int &x) {
    if (Q.front == Q.rear)                   // 队空
        return false;
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;
    return true;
}

3.3.2 链队与双端队列

链队用带头结点的单链表表示队列：front 指向头结点、rear 指向尾结点；队空条件 front==rear（二者都指向头结点）。入队在 rear 后插入、出队删 front 的下一结点；最后一个元素出队后必须把 rear 重新指向头结点，否则rear 悬空——这是链队最经典的填空考点。
双端队列两端均可进行进队和出队操作的队列。两个受限变体（辨析高频）：
输出受限双端队列：两端均可入队，仅一端可出队；
输入受限双端队列：仅一端可入队，两端均可出队。
例 7 易错　受限双端队列的输出序列

输入序列为 1、2、3、4，经过一个输出受限双端队列（两端进、一端出），不可能得到的输出序列是（　）
A. 1 4 2 3　B. 4 1 3 2　C. 4 3 2 1　D. 4 2 1 3

查看解答

B。逐项模拟（设左端出）：

A：1 入左即出；2、3 从右入，4 从左入 → 队列左起 [4, 2, 3]，依次出 → 1 4 2 3 ✓；

B：4 先出 ⇒ 1、2、3 已全部入队且 4 从左入后队形为 [4 | 1、2、3 的某个排列]。1、2、3 只经两端插入可排成 [1,2,3]、[3,1,2]、[2,1,3]、[3,2,1]（排不出 [1,3,2] 与 [2,3,1]），4 出后需接 1 3 2，即要求排列 [1,3,2]——不存在，不可能；

C：全部从左入 → [4,3,2,1]，依次出 ✓；D：1 从右入、2 从左入、3 从右入 → [2,1,3]，4 从左入 → [4,2,1,3]，出 → 4 2 1 3 ✓。

对比记忆：同一序列 4 2 1 3 在「输入受限」双端队列（一端进、两端出）中不可能——4 先出则 1、2、3 已全部入队，此后只能从两端取，2 夹在 1、3 中间永远取不到；而 4 1 3 2 在输入受限中恰好可能（右出 4、左出 1、右出 3、再出 2）。

练习 5 高频考点

判断正误：① 牺牲单元判满的循环队列最多能存 MaxSize 个元素；② tag 方案中若 front==rear 且最近一次操作是入队，则队满；③ 带头结点的链队删除最后一个结点后，rear 应重新指向头结点。

查看答案

① 错：最多 \(MaxSize-1\) 个，必须留一个空位区分队空队满；② 对：入队后追平说明是「满导致的重合」，tag==1；③ 对：否则 rear 指向已删除结点，下次入队出错。

3.4　数组与压缩存储

数组数组是线性表的推广（二维数组的每个元素本身是一个一维线性表）。数组一旦定义，维数与上下界不再改变，因此都采用顺序存储，可按公式直接算出任一元素地址——随机存取，存取任一元素均为 \(O(1)\)。设每个元素占 \(L\) 个存储单元。

3.4.1 数组地址计算：行优先与列优先

一维数组 a[0..n-1] 首地址 base：LOC(aᵢ) = base + i×L（下标从 1 起则为 base+(i-1)×L）。

n 维行优先通式设第 \(k\) 维下界 \(c_k\)、上界 \(d_k\)，则 \[ \mathrm{LOC}(a_{i_1,\cdots,i_n})=\mathrm{LOC}(a_{c_1,\cdots,c_n})+L\sum_{k=1}^{n}\Big[(i_k-c_k)\prod_{j=k+1}^{n}(d_j-c_j+1)\Big] \] 「行优先」= 最右边的下标先走完（变化最快）。「列优先」相反，最左边的下标变化最快。

二维（\(m\) 行 \(n\) 列，下标从 0 起，首地址 base）：行优先 \(\mathrm{LOC}(i,j)=base+(i\times n+j)\times L\)；列优先 \(\mathrm{LOC}(i,j)=base+(j\times m+i)\times L\)。

例 8 高频考点　二维数组地址计算

数组 A[0..3][0..4]（4 行 5 列），每个元素占 \(L=4\) 字节，首地址 base=1000。分别按行优先与列优先求 A[3][4] 与 A[2][3] 的地址。

查看解答

A[3][4]：行优先 \((3\times5+4)\times4=19\times4=76\) → 1076；列优先 \((4\times4+3)\times4=19\times4=76\) → 1076。两者相同并非巧合：A[3][4] 是全数组最后一个元素，偏移 = 总元素数 − 1 = 20 − 1 = 19，与存放顺序无关 ✓。

A[2][3]：行优先 \((2\times5+3)\times4=52\) → 1052；列优先 \((3\times4+2)\times4=56\) → 1056。一般位置两种顺序结果不同 ✓。

套路总结：先数「前面的元素个数」再乘 L。行优先时 A[i][j] 前面有 i 整行加 j 个；列优先时前面有 j 整列加 i 个。

3.4.2 对称矩阵与特殊矩阵压缩 高频考点

对称矩阵满足 \(a_{ij}=a_{ji}\) 的 \(n\) 阶方阵：只需存下三角（含对角线）共 \(\dfrac{n(n+1)}{2}\) 个元素，按行优先存入一维数组 sa，上三角元素对称访问。设 \(i,j\) 从 1 起、sa 下标 \(k\) 从 0 起： \[ k=\begin{cases}\dfrac{i(i-1)}{2}+j-1, & i\ge j\\ \dfrac{j(j-1)}{2}+i-1, & i\lt j\ \text{（借用 } a_{ji}\text{ 的位置）}\end{cases} \] 验证（按行枚举）：a₁₁→0，a₂₁→1，a₂₂→2，a₃₁→3，a₃₂→4，a₃₃→5——第 \(i\) 行前共 \(1+2+\cdots+(i-1)=\frac{i(i-1)}{2}\) 个元素，\(a_{ij}\) 是本行第 \(j\) 个 ✓。
例 9　对称矩阵映射计算

将 5 阶对称矩阵 A 压缩存入 sa（下标从 0 起），求 a₃₂ 与 a₂₅ 的存储位置 k。

查看解答

a₃₂：\(i=3\ge j=2\)，\(k=\dfrac{3\times2}{2}+2-1=4\)。数一数核对：前两行共 \(1+2=3\) 个元素，第三行 a₃₁ 落在 k=3，a₃₂ 落在 k=4 ✓（见图 3-3）。

a₂₅：\(i\lt j\)，借用 a₅₂ 的位置，\(k=\dfrac{5\times4}{2}+2-1=11\)。核对：前四行共 \(1+2+3+4=10\) 个，第五行 a₅₁ 在 k=10，a₅₂ 在 k=11 ✓。

易错：题目给的是 C 语言的 a[i][j]（下标从 0 起）时，公式里的 i、j 要先加 1；sa 从 1 起编号时 \(k=\frac{i(i-1)}{2}+j\)。先统一约定再套公式。

① 5 阶对称矩阵：只需存下三角（含对角） 12345 12345 a₃₂ ② 按行优先压入一维数组 sa（共 15 个单元） a₁₁a₂₁a₂₂a₃₁ a₃₂a₃₃a₄₁a₄₂ a₄₃a₄₄a₅₁a₅₂ 01234567891011 a₃₂ 前面已有 1+2+1=4 个元素 → k = 4；n=5 共存 5×6/2 = 15 个 ✓
图 3-3　对称矩阵下三角按行优先映射（n=5）：\(k=\frac{i(i-1)}{2}+j-1\)（\(i\ge j\)）
三角矩阵与三对角矩阵下三角矩阵（上三角全为同一常数 \(c\)）：下三角部分映射公式同对称矩阵，上三角的常数只存一份，放最后（sa 从 0 起时 \(k=\frac{n(n+1)}{2}\)）。上三角矩阵按行优先存（\(i\le j\)）：\(k=\frac{(i-1)(2n-i+2)}{2}+(j-i)\)。验证 \(n=3\) 上三角：a₁₁→0、a₁₂→1、a₁₃→2、a₂₂→3、a₂₃→4、a₃₃→5，公式 \(a_{13}=\frac{0\times7}{2}+2=2\) ✓。
三对角矩阵（带状矩阵）：仅 \(|i-j|\le1\) 的元素非零，共 \(3n-2\) 个（验证 \(n=4\)：3×4−2=10 ✓）。按行优先存（\(i,j\) 从 1 起，\(k\) 从 0 起）： \[ k=2i+j-3\qquad(|i-j|\le1) \] 验证：a₁₁→0、a₂₁→2、a₃₂→5、a₃₄→7、a₄₄→9，与逐个数格一致 ✓。

3.4.3 稀疏矩阵：三元组与十字链表

稀疏矩阵非零元个数远小于矩阵元素总数的矩阵。
  1. 三元组表：每个非零元存 (行下标, 列下标, 值)，按行优先排成顺序表。压缩率高，但失去了随机存取特性，按元素访问需顺序查找；适合非零元数目、位置稳定的场景（如转置）；
  2. 十字链表：每个非零元为一个结点，含 row、col、value 与 right（同一行的下一个非零元）、down（同一列的下一个非零元）两个指针，同时挂在行链表与列链表上。适合矩阵运算中非零元个数或位置变化剧烈的场景（如矩阵相加）。
练习 6

① 5 阶对称矩阵压缩存储，求 a₄₂ 与 a₂₅ 的 k 值；② n=5 的三对角矩阵压缩后共多少个元素？a₄₃ 的 k 值是多少？

查看答案

① a₄₂：\(i\ge j\)，\(k=\frac{4\times3}{2}+2-1=7\)；a₂₅：\(i\lt j\) 借 a₅₂ 位置，\(k=\frac{5\times4}{2}+2-1=11\)（核对：前四行共 10 个，第五行 a₅₂ 在 k=11 ✓）。

② 共 \(3\times5-2=13\) 个；a₄₃：\(k=2\times4+3-3=8\)（核对：前三行 2+3+3=8 个元素占 k=0..7，a₄₃ 接在 k=8 ✓）。

3.5　章末自测 真题风格

限时 45 分钟，先做后看答案。难度：★★ 基础 / ★★★ 强化 / ★★★★ 冲刺。所有计数与地址结果，代入小数值核对一遍再交卷。

自测 1（选择 · ★★★ 高频考点）

1、2、3、4 依次进栈（进栈出栈可交替），不可能的出栈序列是（　）
A. 2 3 4 1　B. 4 3 2 1　C. 3 1 4 2　D. 1 4 3 2

查看答案

C。3 出栈后栈内自底向上为 1、2，下一个要出 1 而栈顶是 2，不可能（3、1、2 构成 \(1\lt2\lt3\) 的跨越反序）。A：出 2、3、4 后再出 1 ✓；B：全进完逆序全出 ✓；D：出 1 后进 2、3、4 出 4、3、2 ✓。

自测 2（选择 · ★★）

两个栈共享数组空间 data[0..MaxSize-1]，top1 初值 −1，top2 初值 MaxSize，下列说法正确的是（　）
A. 进栈时 top1、top2 向数组两端移动　B. 栈满条件是 top1==top2　C. top1+1==top2 时不能再进栈　D. 两栈栈底设在数组同一端

查看答案

C。两栈都向中间生长（A 错），相遇即 top1+1==top2 为满（B 错），栈底分别在数组两端（D 错）。

自测 3（选择 · ★★★）

中缀表达式 (a+b)*c-d 的后缀表达式是（　）
A. abc+*d-　B. ab+c*d-　C. abcd*+-　D. abc*+d-

查看答案

B。\(\big((a+b)\times c\big)-d\)：a b + c * d -。A 是 a*(b+c)-d 的后缀（对比练习 4，先括号后乘的结构别混）；数值验证 \(a=1,b=2,c=3,d=4\)：中缀 \((1+2)\times3-4=5\)，后缀 1 2 + 3 * 4 - 依次得 3、9、5 ✓。

自测 4（选择 · ★★★★ 冲刺）

中缀表达式 c-a*b+d 的前缀表达式是（　）
A. +-c*abd　B. c-a*b+d 直接去掉括号　C. +c-*abd　D. -+c*abd

查看答案

A。完全加括号 \(\big(c-(a\times b)\big)+d\)：先 \(ab\times\)，再 \(c-ab\times-\)，最外层 \(+\) 提最前 → + - c * a b d。验证（\(a=2,b=3,c=10,d=4\)）：前缀从右往左扫：d、a、b 进栈，遇 * 算 2×3=6，遇 - 算 10−6=4，遇 + 算 4+4=8；中缀 \(10-2\times3+4=8\) ✓。

自测 5（选择 · ★★★ 真题风格）

循环队列存于数组 A[0..9]，front 指向队头元素、rear 指向队尾元素的下一空位。某时刻 front=4、rear=1，则队列中元素个数为（　）
A. 6　B. 7　C. 8　D. 9

查看答案

B。\((1-4+10)\%10=7\)，元素位于 4、5、6、7、8、9、0 ✓。套路口诀「个数为负就加 M 再取模」。

自测 6（选择 · ★★★ 易错）

容量 M=5 的循环队列采用 tag 方案（出队后 tag=0，入队后 tag=1），初始 front=rear=0。从空队开始连续入队 a、b、c、d、e 后，下列判断正确的是（　）
A. 队列未满，可再入 1 个元素　B. front=rear=0 且 tag=1，队列已满　C. 元素个数为 \((0-0+5)\%5=0\)　D. 队满条件 \((1+0)\%5==0\) 不成立

查看答案

B。5 次入队后 rear 绕回 0 与 front 重合，且最近一次是入队（tag=1）→ 满。C 提醒：front==rear 时个数公式 \((rear-front+M)\%M\) 算出 0，该公式此时失效，真实个数 5 个（tag/size 方案可存满 M 个，这是它与「牺牲单元」方案的本质区别）。

自测 7（选择 · ★★★）

输入受限双端队列（一端进队、两端出队）的输入序列为 1、2、3、4，不可能得到的输出序列是（　）
A. 4 1 3 2　B. 4 2 1 3　C. 1 4 3 2　D. 3 4 1 2

查看答案

B。4 先出 ⇒ 1、2、3 已全部入队成 [1,2,3]，此后只能从两端取，2 夹在中间取不到（注意与例 7 输出受限对比：4 2 1 3 在输出受限中可能，而 4 1 3 2 在输出受限中不可能）。A：右出 4、左出 1、右出 3、再出 2 ✓；C：左出 1 后右出 4、3、2 ✓；D：右出 3 后 4 入队右出，再左出 1、2 ✓。

自测 8（填空 · ★★★）

数组 A[0..4][0..5]（5 行 6 列）每元素占 4 字节，首地址 2000：①列优先时 A[3][4] 的地址为 \(\underline{\hspace{1.5cm}}\)；②n 阶对称矩阵压缩存储需 \(\underline{\hspace{1.5cm}}\) 个单元，6 阶三对角矩阵需 \(\underline{\hspace{1.5cm}}\) 个单元。

查看答案

① \(2000+(4\times5+3)\times4=2000+92=\)2092（列优先 A[i][j] 前面有 j 整列加 i 个；行优先则为 2088）。② \(\frac{n(n+1)}{2}\)；\(3\times6-2=\)16。

自测 9（解答 · ★★★★ 冲刺）

用运算符栈法将中缀表达式 8-3*2+6/3 转换为后缀表达式，并对后缀式用栈求值。

查看解答

转换（同级先弹后压）：8 输出；- 入栈；3 输出；* 优先于栈顶 - 入栈；2 输出；+ 到来，弹出 \(\times\)、\(-\) 输出后 + 入栈（输出 8 3 2 * -）；6 输出；/ 优先于 + 入栈；3 输出；结束弹出全部。

后缀式：8 3 2 * - 6 3 / +

求值：3、2 进栈遇 \(*\) → \(3\times2=6\)；8、6 遇 \(-\) → \(8-6=2\)；6、3 遇 \(/\) → \(6\div3=2\)；2、2 遇 \(+\) → 4。核对中缀 \(8-3\times2+6\div3=8-6+2=4\) ✓。

易错：第二个 + 进栈前必须把栈内同级与更高级的 \(\times\)、\(-\) 全部弹出，否则会得到 8 3 2 * 6 3 / + - 一类的错式。

3.6　本章考点总结

考点常考题型热度核心方法
出栈序列合法性判断选择题★★★★★ 每年必考模拟法（逐个要元素、进到目标再看栈顶）；快速排除用「无 \(i\lt j\lt k\) 使 \(p_j\lt p_k\lt p_i\)」；计数用 Catalan \(\frac{1}{n+1}\binom{2n}{n}\)（n=4→14）
顺序栈 / 链栈 / 共享栈选择 / 判断★★★top 两种约定（指向栈顶元素 vs 下一空位）决定判空判满；链栈头插即栈顶；共享栈满：top1+1==top2
表达式转换与求值选择 / 解答★★★★★手算「完全加括号→移运算符」；机算运算符栈（同级先弹后压）；求值用操作数栈（先弹是右操作数）
循环队列判空判满与计数选择 / 填空★★★★★ 每年必考三方案：牺牲单元 (rear+1)%M==front / 设 size / 设 tag；个数 \((rear-front+M)\%M\)（front==rear 时注意公式失效）
链队与双端队列选择题★★★链队删最后一结点后 rear 重指头结点；输出受限（两端进一端出）与输入受限（一端进两端出）逐一模拟排除
数组地址计算选择 / 填空★★★★数「前面元素个数」×L：行优先 \(i\times n+j\)，列优先 \(j\times m+i\)；先统一下标起点
特殊矩阵压缩映射选择 / 填空★★★★对称阵下三角 \(k=\frac{i(i-1)}{2}+j-1\)（i≥j，借位 i<j）；三对角 \(k=2i+j-3\)、共 3n−2 个；稀疏阵三元组 / 十字链表概念
下一步本章过关标准：例题 9 道全部独立重做；自测 9 题至少 7 题正确；能 10 秒判出栈序列、5 秒算循环队列元素个数、30 秒算压缩地址；Catalan 数前 5 项（1、2、5、14、42）与三方案判满条件默写无误。然后进入 第 4 章 串（KMP 模式匹配）——线性结构的收官与 408 大题著名难点的正面交锋。