定义#

$n \times n$ 矩阵 $M$ 满足 $m_{i,j} = m_{j,i}$（对所有 $1 \leq i,j \leq n$）。只存上三角或下三角，共 $\frac{n(n+1)}{2}$ 个元素。

上三角 · 行优先公式（1-based）#

第 $i$ 行：$m_{i,i}, m_{i,i+1}, \ldots, m_{i,n}$，共 $n-i+1$ 个。

上三角 · 列优先公式（1-based）#

第 $j$ 列：$m_{1,j}, m_{2,j}, \ldots, m_{j,j}$，共 $j$ 个。

下三角元素查询模板（⭐高频陷阱）#

当题目”只存上三角”且要查的元素在下三角时：

1. 用 $m_{i,j} = m_{j,i}$ 交换下标
2. 重新核对交换后是否进入上三角（$j \geq i$）
3. 代入公式

⚠️ 易错：漏掉第一步是 2020-01 选错最常见的原因。

真题精讲：2018-03（上三角行优先）#

$12 \times 12$ 对称矩阵 $M$，上三角按行优先存入一维数组 $N$（C 语言，0-based），求 $m_{6,6}$ 的下标。

$m_{6,6}$ 已在 $j \geq i$ 的上三角区域。代入 $n=12, i=6, j=6$：

$\text{idx} = \frac{5 \times (24 - 6 + 2)}{2} + (6-6) = \frac{5 \times 20}{2} + 0 = 50$

答案 50（手算验证：前 5 行共 $12+11+10+9+8=50$ 个元素，$m_{6,6}$ 是第 6 行第一个）。

真题精讲：2020-01（上三角列优先 + 对称性）#

$10 \times 10$ 对称矩阵 $M$，上三角按列优先存入 $N$，求 $m_{7,2}$ 的下标。

第一步：$m_{7,2}$ 在下三角，用对称性：$m_{7,2} = m_{2,7}$，查 $i=2, j=7$。

第二步：代入列优先公式： $\text{idx} = \frac{7 \times 6}{2} + (2-1) = 21 + 1 = 22$

答案 22。

行优先 vs 列优先公式对比#

定义#

• 上三角矩阵：$i > j$（下三角部分）的元素都等于同一常数 $c$
• 下三角矩阵：$i < j$（上三角部分）的元素都等于同一常数 $c$

压缩策略#

存非常数部分的 $\frac{n(n+1)}{2}$ 个元素 + 1 个常数 $c$，共 $\frac{n(n+1)}{2} + 1$ 个。

• 非常数部分的下标公式与对称矩阵的对应三角完全相同
• 常数 $c$ 单独存在末尾位置 $N[\frac{n(n+1)}{2}]$

三角矩阵 vs 对称矩阵（⭐辨析）#

定义#

只有 $|i-j| \leq 1$ 的元素非零（主对角线 + 上下副对角线）：

1
n=5 时的非零分布：
2
* *
3
* * *
4
  * * *
5
    * * *
6
      * *

每行非零元素数#

• 第 1 行：2 个 ⚠️
• 第 $2 \sim n-1$ 行：3 个
• 第 $n$ 行：2 个 ⚠️

总非零数：$2 + 3(n-2) + 2 = 3n - 2$

行优先下标公式（1-based）#

中间行（$2 \leq i \leq n-1$）：

手算验证：$m_{30,30}$ 之前有 $2 + 3 \times 28 = 86$ 个元素（$N[0]$ 到 $N[85]$）。第 30 行的 $m_{30,29}$、$m_{30,30}$、$m_{30,31}$ 依次占 $N[86]$、$N[87]$、$N[88]$。$m_{30,30}$ 在 $N[87]$ → 代入公式：$2 \times 30 + 30 - 3 = 87$ ✓

三个高频坑（⭐）#

1. 第 1 行只有 2 个元素——全部按 3 个算前缀和会错
2. $i=j$（主对角线）vs $i=j-1$（上副对角线）混淆——$m_{30,30}$ 在第 30 行的中间不是第一个
3. 公式 $2i+j-3$ 只对中间行成立——$i=1$ 或 $i=n$ 时单独处理

真题精讲：2016-04#

100 阶三对角矩阵 $M$，按行优先存入下标从 0 的一维数组 $N$。求 $m_{30,30}$ 的下标。

代入 $i=j=30$（属于 $2 \leq i \leq 99$ 的常规行）： $\text{idx} = 2 \times 30 + 30 - 3 = 87$

答案 87。

定义#

非零元素个数 $t$ 远小于矩阵总元素数 $m \times n$，且分布无规律。

三元组表#

对每个非零元素存一个三元组 $(i, j, value)$：

1
typedef struct {
2
    int rows;       // 原矩阵的行数
3
    int cols;       // 原矩阵的列数
4
    int nums;       // 非零元素个数
5
    Triple data[N]; // 三元组数组
6
} TSMatrix;

除三元组本身外，还需存储原矩阵的行数和列数（不是非零行列数）。仅存非零行列数会丢失零元素的行/列信息，无法还原矩阵形状。

真题精讲：2023-03#

采用三元组表存储稀疏矩阵 M，除三元组外还需保存的是？ I. M 的行数 II. M 中包含非零元素的行数 III. M 的列数 IV. M 中包含非零元素的列数

正确答案：I 和 III（原矩阵的行数和列数）。

反例：$5 \times 5$ 矩阵只有 $m_{1,1}=1$，三元组为 $\{(1,1,1)\}$。非零行数 II=1，非零列数 IV=1。如果只存 II+IV，重建出来是 $1 \times 1$ 矩阵，原矩阵的 4 行 4 列零元素信息全部丢失。

十字链表#

适合频繁修改的稀疏矩阵。每个非零元素是一个节点，同时挂在所在行链表和列链表上：

1
typedef struct OLNode {
2
    int row, col;
3
    ElemType value;
4
    struct OLNode *right;   // 同一行内下一个非零元素
5
    struct OLNode *down;    // 同一列内下一个非零元素
6
} OLNode;

优势：插入/删除 $O(\text{行长}+\text{列长})$，不需要移动其它元素。

三元组 vs 十字链表#

邻接矩阵不是稀疏矩阵的压缩结构（⭐辨析）#

邻接矩阵的”矩阵”二字容易误判为”与稀疏矩阵相关”。它就是一个普通的 $n \times n$ 二维数组，完全不压缩，0 元素照常占内存。稀疏图的邻接矩阵用三元组或十字链表压缩才高效。