跳转至

408 高频考点精讲:特殊矩阵(Special and Sparse Matrices Compression Storage)

模块归属:数据结构 · 数组与特殊矩阵
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生


一、 考情档案

  • 近十年考查频次:5 次(2016~2025 年:2016#4、2017#3、2018#3、2020#1、2023#3)
  • 历年总考查频次:5 次
  • 出题形式:单项选择题(分值 2 分),常作为数据结构模块的前置基础题考查
  • 命题特点:
  • 考查重点聚焦于两大核心方向:特殊矩阵压缩存储的一维地址映射代数推导、稀疏矩阵存储结构原理及元数据维护。
  • 映射推导考查细节极多,涵盖行优先/列优先存储方向、上三角/下三角存储区域、矩阵二维下标起始基准(1-based 或 0-based)、一维数组下标起始基准(0-based 或 1-based)、对称转换映射(\(i\)$ \text{和} $\(j\) 互换)、带状矩阵反向坐标还原。
  • 稀疏矩阵考查侧重顺序存储(三元组顺序表)的元数据完备性,以及链式存储(十字链表)的结点指针结构特性。
近十年考查年份分布:
2016   2017   2018   2019   2020   2021   2022   2023   2024   2025
  √      √      √      -      √      -      -      √      -      -
 (#4)   (#3)   (#3)          (#1)                 (#3)

二、 具体考察内容

1. 数组及压缩存储理论基础

(1) 数组的顺序映射模型

多维数组在物理内存中本质上是线性连续存储的,多维逻辑结构映射到一维物理地址主要有两种标准遍历方式: * 行优先顺序(Row-Major Order):先行后列,逐行将元素存入物理空间。设二维数组 \(A[1..m, 1..n]\)$ \text{,每个元素占用} $\(L\)$ \text{个字节,基地址为} $\(\text{LOC}(A[1, 1])\)$ \text{,则元素} $\(A[i, j]\) 的地址为: $\(\text{LOC}(A[i, j]) = \text{LOC}(A[1, 1]) + [(i - 1) \times n + (j - 1)] \times L\)$ * 列优先顺序(Column-Major Order):先列后行,逐列将元素存入物理空间。元素 \(A[i, j]\) 的地址为: $\(\text{LOC}(A[i, j]) = \text{LOC}(A[1, 1]) + [(j - 1) \times m + (i - 1)] \times L\)$

(2) 特殊矩阵及稀疏矩阵压缩存储的界定

  • 特殊矩阵(Special Matrix):矩阵中存在大量值相同或分布具有规则几何形态的元素(如对称矩阵、三角矩阵、对角矩阵)。压缩存储原则是:相同的多个元素仅分配一个存储空间,零元素不分配空间,利用确定的数学映射公式直接由矩阵下标 \((i, j)\)$ \text{计算出一维物理存储下标} $\(k\)。
  • 稀疏矩阵(Sparse Matrix):矩阵中非零元素个数较少且零元素分布不规则。通常定义非零元素个数 \(t\)$ \text{及矩阵元素总数} $\(m \times n\)$ \text{的比值为稀疏因子} $\(\delta\): $\(\delta = \frac{t}{m \times n}\)$ 当 \(\delta \le 0.05\) 时,通常视为稀疏矩阵。由于零元素分布无规则,必须显式存储每个非零元素的行标、列表和数值。

2. 对称矩阵(Symmetric Matrix)的压缩存储

(1) 定义及代数性质

设方阵 \(A\)$ \text{为} $\(n\) 阶矩阵,若满足: $\(a_{i,j} = a_{j,i} \quad (1 \le i, j \le n)\)$ 则称 \(A\) 为对称矩阵。

(2) 存储空间开销

由于主对角线两侧元素关于主对角线对称相等,只需存储主对角线及上三角(或主对角线及下三角)元素,所需的总存储单元数为等差数列求和: $\(\sum_{r=1}^n r = 1 + 2 + \dots + n = \frac{n(n + 1)}{2}\)$ 将这 \(\frac{n(n+1)}{2}\)$ \text{个元素紧凑存入一维数组} $\(B\) 中。

(3) 四类地址映射推导(设矩阵下标 \(1 \le i, j \le n\)$ \text{,一维数组下标} $\(0 \le k < \frac{n(n+1)}{2}\))

对称矩阵 A (以 4x4 为例):
[ a11  a12  a13  a14 ]
[ a21  a22  a23  a24 ]
[ a31  a32  a33  a34 ]
[ a41  a42  a43  a44 ]
下三角区域: i >= j
上三角区域: i <= j
  • 模式一:存储下三角(含主对角线),按行优先存储
  • 当 \(i \ge j\) 时:
    • 第 1 行存 1 个,第 2 行存 2 个,...,第 \(i-1\)$ \text{行存} $\(i-1\) 个;
    • 前 \(i-1\)$ \text{行累计元素数:} $\(\sum_{t=1}^{i-1} t = \frac{i(i-1)}{2}\);
    • 第 \(i\)$ \text{行从} $\(a_{i,1}\)$ \text{存储到} $\(a_{i,j}\)$ \text{,本行排在} $\(a_{i,j}\)$ \text{前面的元素共有} $\(j - 1\) 个;
    • 一维数组下标(0-based)为: $\(k = \frac{i(i-1)}{2} + j - 1 \quad (i \ge j)\)$
  • 当 \(i < j\) 时:

    • 元素位于上三角,由对称性 \(a_{i,j} = a_{j,i}\),直接互换行标和列表,代入上述公式: $\(k = \frac{j(j-1)}{2} + i - 1 \quad (i < j)\)$
  • 模式二:存储下三角(含主对角线),按列优先存储

  • 当 \(i \ge j\) 时:
    • 第 1 列存 \(n\)$ \text{个,第 2 列存} $\(n-1\)$ \text{个,...,第} $\(j-1\)$ \text{列存} $\(n-(j-2)\) 个;
    • 前 \(j-1\)$ \text{列累计元素数:} $\(\frac{(j-1)[n + (n - j + 2)]}{2} = \frac{(j-1)(2n - j + 2)}{2}\);
    • 第 \(j\)$ \text{列中从} $\(a_{j,j}\)$ \text{到} $\(a_{i,j}\)$ \text{,本列排在} $\(a_{i,j}\)$ \text{前面的元素共有} $\(i - j\) 个;
    • 一维数组下标(0-based)为: $\(k = \frac{(j-1)(2n - j + 2)}{2} + i - j \quad (i \ge j)\)$
  • 当 \(i < j\) 时:互换下标代入: $\(k = \frac{(i-1)(2n - i + 2)}{2} + j - i \quad (i < j)\)$

  • 模式三:存储上三角(含主对角线),按行优先存储

  • 当 \(i \le j\) 时:
    • 第 1 行存 \(n\)$ \text{个,第 2 行存} $\(n-1\)$ \text{个,...,第} $\(i-1\)$ \text{行存} $\(n-(i-2)\) 个;
    • 前 \(i-1\)$ \text{行累计元素数:} $\(\frac{(i-1)(2n - i + 2)}{2}\);
    • 第 \(i\)$ \text{行中从} $\(a_{i,i}\)$ \text{到} $\(a_{i,j}\)$ \text{,本行排在} $\(a_{i,j}\)$ \text{前面的元素共有} $\(j - i\) 个;
    • 一维数组下标(0-based)为: $\(k = \frac{(i-1)(2n - i + 2)}{2} + j - i \quad (i \le j)\)$
  • 当 \(i > j\) 时:互换下标代入: $\(k = \frac{(j-1)(2n - j + 2)}{2} + i - j \quad (i > j)\)$

  • 模式四:存储上三角(含主对角线),按列优先存储

  • 当 \(i \le j\) 时:
    • 第 1 列存 1 个,第 2 列存 2 个,...,第 \(j-1\)$ \text{列存} $\(j-1\) 个;
    • 前 \(j-1\)$ \text{列累计元素数:} $\(\sum_{t=1}^{j-1} t = \frac{j(j-1)}{2}\);
    • 第 \(j\)$ \text{列中从} $\(a_{1,j}\)$ \text{到} $\(a_{i,j}\)$ \text{,本列排在} $\(a_{i,j}\)$ \text{前面的元素共有} $\(i - 1\) 个;
    • 一维数组下标(0-based)为: $\(k = \frac{j(j-1)}{2} + i - 1 \quad (i \le j)\)$
  • 当 \(i > j\) 时:互换下标代入: $\(k = \frac{i(i-1)}{2} + j - 1 \quad (i > j)\)$

3. 三角矩阵(Triangular Matrix)的压缩存储

(1) 下三角矩阵及上三角矩阵

  • 下三角矩阵(Lower Triangular Matrix):主对角线上方元素均为同一常数 \(C\)(常见为 0)。
  • 上三角矩阵(Upper Triangular Matrix):主对角线下方元素均为同一常数 \(C\)。

(2) 存储空间配置及访问映射

  • 一维数组容量配置为: $\(\text{Capacity} = \frac{n(n + 1)}{2} + 1\)$
  • 前 \(\frac{n(n+1)}{2}\) 个存储单元按对称矩阵规则连续存储三角区域的非零/非常数元素;
  • 最后一个存储单元(一维数组下标 \(k = \frac{n(n+1)}{2}\)$ \text{)专门用于存储常数} $\(C\)。
  • 访问映射:查询元素 \(a_{i,j}\) 时,若落在常数三角区,直接重定向至数组最后位置: $\(k = \frac{n(n + 1)}{2}\)$

4. 三对角带状矩阵(Tridiagonal Matrix)的压缩存储

(1) 带状特性及结构定义

三对角矩阵是非零元素集中在主对角线及其相邻上下两条对角线上的特殊带状矩阵。 对 \(n \times n\)$ \text{的方阵,元素} $\(a_{i,j}\) 满足: $\(|i - j| \le 1 \quad (1 \le i, j \le n)\)$ 其余位置元素均为 0。

三对角矩阵 A:
[ a11  a12    0   ...   0   ]
[ a21  a22  a23   ...   0   ]
[  0   a32  a33  a34    0   ]
[ ...  ...  ...  ...   ...  ]
[  0   ...   0   an,n-1  an,n ]

(2) 非零元素总数

  • 第 1 行:2 个元素(\(a_{1,1}, a_{1,2}\));
  • 第 \(2 \sim n-1\) 行:每行 3 个元素;
  • 第 \(n\)$ \text{行:2 个元素(} $\(a_{n,n-1}, a_{n,n}\));
  • 全部非零元素总数: $\(N = 2 + 3 \times (n - 2) + 2 = 3n - 2\)$

(3) 正向映射推导(已知矩阵下标 \(i, j\),求一维数组 0-based 下标 k)

  • 按行优先顺序存储:
  • 前 $i

  • 1$$ \text{行包含的非零元素总数:第 1 行存 2 个,中间} $$i

  • 2$$ \text{行每行存 3 个,前} $$i

  • 1$ 行总计元素数为: $\(S_{i-1} = 2 + 3 \times (i - 2) = 3i - 4\)$

  • 在第 \(i\)$ \text{行中,非零元素的起始列标为} $\(i - 1\)。
  • 当前元素 \(a_{i,j}\)$ \text{在第} $\(i\) 行内排在它前面的元素个数为: $$j

  • (i

  • 1) = j

  • i + 1$$

  • 因此,元素 \(a_{i,j}\) 是全部非零元素中的第几个(1-based 序号): $$\text{Rank} = S_{i-1} + (j

  • i + 1) + 1 = (3i

  • 4) + (j

  • i + 2) = 2i + j

  • 2$$

  • 对应一维数组从 0 开始的存储下标 \(k = \text{Rank} - 1\): $\(k = 2i + j - 3\)$

(4) 逆向坐标还原推导(已知一维数组下标 k,求矩阵下标 \(i, j\))

由于第 1 行只有 2 个元素,若虚拟假设第 1 行前面还有一个元素,则全部行均包含 3 个元素。 * 行号 \(i\) 计算公式: $\(i = \left\lfloor \frac{k + 1}{3} \right\rfloor + 1\)$ * 列号 \(j\) 计算公式: 代入正向公式 \(k = 2i + j - 3\),解得: $\(j = k - 2i + 3\)$


5. 稀疏矩阵(Sparse Matrix)的压缩存储

(1) 三元组顺序表(Triple Sequential Table)

  • 存储节点定义: 每个非零元素用一个三元组 (row, col, value)(或 (i, j, v))唯一确定。
  • 矩阵全局控制元数据: 三元组表不能只存储一维的三元组序列,必须同时保存三个矩阵全局参数:
  • 矩阵的总行数 rows(或 m);
  • 矩阵的总列数 cols(或 n);
  • 矩阵的非零元素总数 nums(或 terms)。
  • 理论核心辨析(考点本质):
  • 矩阵的总行数和总列数决定了矩阵在线性代数层面的向量空间维度,任何矩阵加法、转置、乘法算法均依赖维度兼容性检查;
  • 不需要额外保存“包含非零元素的行数”或“包含非零元素的列数”,因为全零行和全零列本身属于矩阵合法形态的一部分,且三元组表中未出现的行号即隐式表明该行为全零行,统计非零行数对矩阵空间形态的恢复无任何不可替代的决定性作用。
三元组顺序表存储结构示意:
Matrix M: 4 x 5, 3 个非零元: (1,2,12), (2,4,35), (4,1,-7)
全局元数据: {rows: 4, cols: 5, nums: 3}
三元组表:
  data[0]: {i: 1, j: 2, v: 12}
  data[1]: {i: 2, j: 4, v: 35}
  data[2]: {i: 4, j: 1, v: -7}

(2) 十字链表(Orthogonal Linked List)

  • 适用场景: 当稀疏矩阵需要频繁进行代数加、乘等运算时,非零元素的数量和位置处于动态变化之中。采用三元组顺序表会导致频繁的大量元素物理搬移;采用十字链表可将插入和删除的时间开销降至链表指针重定向级别。
  • 结点物理域结构: 每个非零元素分配一个 5 域结点: $\(\begin{array}{|c|c|c|c|c|} \hline \text{row} & \text{col} & \text{value} & \text{right} & \text{down} \\ \hline \end{array}\)$
  • row:非零元素的行下标;
  • col:非零元素的列下标;
  • value:非零元素数值;
  • right:行指针,指向同一行中下一个列标递增的非零元结点;
  • down:列指针,指向同一列中下一个行标递增的非零元结点。
  • 表头指针向量: 稀疏矩阵设置两个一维指针数组:
  • 行头指针数组 rhead[1..m]:每个指针指向对应行的非零元单链表头结点;
  • 列头指针数组 chead[1..n]:每个指针指向对应列的非零元单链表头结点。
十字链表正交网状结构示意:
chead[1]  chead[2]  chead[3]
   |         |         |
   v         v         v
+-------+ +-------+ +-------+
| Node  | | Node  | | Node  |
+-------+ +-------+ +-------+
   |         |         |
   v         v         v
rhead[1] -> [ (1,1,3) ] --------> [ (1,3,5) ]
                |                    |
                v                    v
rhead[2] -> [ (2,1,7) ] --------> [ (2,3,2) ]

三、 近十年真题精讲(2016~2025)


【真题 1】2023 年 408 第 3 题 · 稀疏矩阵三元组表元数据构成

题目
若采用三元组表存储结构存储稀疏矩阵 M。则除三元组外,下列数据中还需要保存的是( )。
I. M 的行数
II. M 中包含非零元素的行数
III. M 的列数
IV. M 中包含非零元素的列数
A. 仅 I 和 III          B. 仅 I 和 IV          C. 仅 II 和 IV          D. I, II, III, IV

【解析】

  1. 三元组表的数据结构定义:
    在稀疏矩阵的三元组顺序存储结构中,每个非零元素用三元组 (row, col, value) 记录其局部坐标及元素值。
  2. 全局元数据的必要性分析:
  3. 仅有三元组列表无法确定稀疏矩阵的整体几何形态。例如,一个包含 3 个非零元的三元组表,其矩阵形态可以是 \(3 \times 3\)、\(10 \times 10\)$ \text{乃至} $\(1000 \times 1000\)。为了完整还原矩阵形态、实现矩阵加法/转置/乘法时的维度兼容校验以及判定元素下标合法性,必须完整记录矩阵的总行数(I)和总列数(III),同时通常还会记录非零元素总数 nums。
  4. 对于 II(包含非零元素的行数)和 IV(包含非零元素的列数):稀疏矩阵中全零行和全零列属于合法定义,某一特定行或列是否含有非零元素可以通过遍历三元组表直接获知;稀疏矩阵的存储规格及算法逻辑均无需常驻维护非零行数和非零列数。
  5. 结论:必须保存的数据仅为 I 和 III。

正确答案:A


【真题 2】2020 年 408 第 1 题 · 对称矩阵按列优先压缩存储映射

题目
将一个 10×10 对称矩阵 M 的上三角部分的元素 \(m_{i,j} (1 \le i \le j \le 10)\)$ \text{,按列优先存入 C 语言的一维数组 N 中,元素} $\(m_{7,2}\) 在 N 中的下标是( )。
A. 15          B. 16          C. 22          D. 23

【解析】

  1. 对称性转化:
    题目明确指定压缩存储的是矩阵 M 的上三角部分(满足行标小于等于列表:\(i \le j\)$ \text{)。待查询元素为} $\(m_{7,2}\)$ \text{,此时行标} $\(7 >\)$ \text{列表} $\(2\)$ \text{,位于下三角区域。根据对称矩阵的定义} $\(m_{i,j} = m_{j,i}\),必须先将其映射为其上三角对称元素: $\(m_{7,2} = m_{2,7}\)$ 此时新的二维坐标为:行标 \(i = 2\)$ \text{,列表} $\(j = 7\)。
  2. 按列优先累加前置元素:
    按列优先存储上三角时,各列所存储的元素范围为 $$ \text{1 \le \text{行标} \le \text{列标}} $$:
  3. 第 1 列存储 1 个元素(\(m_{1,1}\));
  4. 第 2 列存储 2 个元素(\(m_{1,2}, m_{2,2}\));
  5. 第 3 列存储 3 个元素(\(m_{1,3}, m_{2,3}, m_{3,3}\));
  6. ...
  7. 第 6 列存储 6 个元素。 前 6 列(即第 1 列至第 \(j-1\) 列)累计存储的元素总数为等差数列求和: $\(S_6 = \sum_{c=1}^6 c = \frac{6 \times (1 + 6)}{2} = 21\)$
  8. 定位目标列内偏移量:
    在第 7 列(\(j = 7\))中,元素按行标升序排列:
  9. 第 1 个元素为 \(m_{1,7}\)$ \text{(全局第} $\(21 + 1 = 22\) 个元素);
  10. 第 2 个元素为 \(m_{2,7}\)$ \text{(全局第} $\(21 + 2 = 23\) 个元素)。
  11. 一维数组下标折算:
    题目指定存入 C 语言的一维数组 N 中,C 语言数组下标从 0 起始(0-based)。 第 23 个元素的物理下标为: $\(k = 23 - 1 = 22\)$

正确答案:C


【真题 3】2018 年 408 第 3 题 · 对称矩阵按行优先压缩存储映射

题目
设有一个 12×12 的对称矩阵 M,将其上三角部分的元素 \(m_{i,j} (1 \le i \le j \le 12)\)$ \text{按行优先存入 C 语言的一维数组 N 中,元素} $\(m_{6,6}\) 在 N 中的下标是( )。
A. 50          B. 51          C. 55          D. 66

【解析】

  1. 存储区域及矩阵维度:
    矩阵阶数 \(n = 12\)$ \text{。存储区域为上三角部分(} $\(1 \le i \le j \le 12\)$ \text{),存储顺序为按行优先。目标元素为} $\(m_{6,6}\)$ \text{,满足} $\(i = 6 \le j = 6\),直接位于上三角主对角线上,无需对称反转。
  2. 按行优先累加前置行元素数:
    矩阵上三角的各行元素个数自顶向下逐行递减:
  3. 第 1 行存 12 个元素(\(m_{1,1} \sim m_{1,12}\));
  4. 第 2 行存 11 个元素(\(m_{2,2} \sim m_{2,12}\));
  5. 第 3 行存 10 个元素(\(m_{3,3} \sim m_{3,12}\));
  6. 第 4 行存 9 个元素(\(m_{4,4} \sim m_{4,12}\));
  7. 第 5 行存 8 个元素(\(m_{5,5} \sim m_{5,12}\))。 前 5 行(即第 1 行至第 \(i-1\) 行)累计的元素总数为: $\(S_5 = 12 + 11 + 10 + 9 + 8 = \frac{5 \times (12 + 8)}{2} = 50\)$
  8. 定位目标行内偏移量:
    在第 6 行中,存储的第一个元素即为主对角线元素 \(m_{6,6}\)。 因此,\(m_{6,6}\)$ \text{是整个一维存储序列中的第} $\(50 + 1 = 51\) 个元素。
  9. C 语言下标换算:
    C 语言一维数组下标以 0 开始: $\(k = 51 - 1 = 50\)$

正确答案:A


【真题 4】2017 年 408 第 3 题 · 稀疏矩阵压缩存储结构适用性

题目
适用于压缩存储稀疏矩阵的两种存储结构是( )。
A. 三元组表和十字链表          B. 三元组表和邻接矩阵
C. 十字链表和二叉链表          D. 邻接矩阵和十字链表

【解析】

  1. 选项逐项解构:
  2. 三元组表(Triple Table):将非零元素的行标、列标及数值按顺序连续存储于线性表结构中,属于典型的稀疏矩阵顺序压缩存储结构。
  3. 十字链表(Orthogonal List):通过具有行指针 right 和列指针 down 的正交结点,将矩阵各行、各列非零元素分别链接为行单链表和列单链表,属于典型的稀疏矩阵链式压缩存储结构。
  4. 邻接矩阵(Adjacency Matrix):图的顺序存储结构,本质为标准的二维数组,未对矩阵中的零元素(或无穷大元素)进行存储空间压缩。
  5. 二叉链表(Binary Linked List):二叉树及树/森林的链式存储结构,每个结点包含 lchild 和 rchild 两个孩子指针,不用于矩阵压缩。
  6. 结论:同时适用于稀疏矩阵压缩存储的两种经典结构为三元组表和十字链表。

正确答案:A


【真题 5】2016 年 408 第 4 题 · 三对角矩阵按行优先压缩存储映射

题目
有一个 100 阶的三对角矩阵 M,其元素 \(m_{i,j} (1 \le i \le 100, 1 \le j \le 100)\)$ \text{按行优先依次压缩存入下标从 0 开始的一维数组 N 中。元素} $\(m_{30,30}\) 在数组 N 中的下标是( )。
A. 86          B. 87          C. 88          D. 89

【解析】

  1. 三对角矩阵的行结构分析:
    三对角矩阵满足非零元素限制条件 \(|i - j| \le 1\):
  2. 第 1 行仅包含 2 个非零元素:\(m_{1,1}, m_{1,2}\);
  3. 第 \(2 \sim 29\)$ \text{行,共计} $\(29 - 2 + 1 = 28\) 行,每行恰好包含 3 个非零元素;
  4. 因此,前 29 行(即第 1 行至第 \(i-1\) 行)存储的非零元素总数为: $\(S_{29} = 2 + 28 \times 3 = 2 + 84 = 86\)$
  5. 计算目标行内偏移:
    在第 30 行中,非零元素依序为:
  6. 第 1 个非零元:\(m_{30,29}\);
  7. 第 2 个非零元:\(m_{30,30}\);
  8. 第 3 个非零元:\(m_{30,31}\)。 因此,\(m_{30,30}\) 是第 30 行内的第 2 个非零元素。
  9. 计算一维数组下标:
  10. \(m_{30,30}\)$ \text{是全体非零元素中的第} $\(86 + 2 = 88\) 个元素。
  11. 数组 N 下标从 0 开始,故下标为: $\(k = 88 - 1 = 87\)$
  12. 通用公式法快速核算:
    三对角矩阵行优先压缩存储(1-based 二维下标映射到 0-based 一维下标)的通式为: $\(k = 2i + j - 3\)$ 代入 \(i = 30, j = 30\): $\(k = 2 \times 30 + 30 - 3 = 60 + 30 - 3 = 87\)$

正确答案:B


四、 核心解题套路及易错陷阱

1. 下标基准陷阱(1-based 与 0-based 对齐)

  • 常见陷阱: 试题中给定的矩阵行标、列表通常从 1 开始记数(如 \(1 \le i, j \le n\)),而数组下标在 C 语言语境下默认为从 0 开始记数(0-based)。
  • 规避策略: 解题时统一采用“两步定位法”:
  • 先求目标元素是全部序列中的第几个(设为序号 \(\text{Rank}\),从 1 开始);
  • 若一维数组下标从 0 开始,则物理下标 \(k = \text{Rank} - 1\)$ \text{;若一维数组下标从 1 开始,则} $\(k = \text{Rank}\)。

2. 存储优先次序及三角区域匹配陷阱

  • 辨析要点: 行优先累加的是“前 \(i-1\)$ \text{行包含的元素数”;列优先累加的是“前} $\(j-1\) 列包含的元素数”。
  • 对称矩阵的坐标折叠法则:
  • 若矩阵只压缩存储了上三角(\(i \le j\)$ \text{),而待求元素给定的坐标满足} $\(i > j\)$ \text{(如 2020 年真题} $\(m_{7,2}\)),必须立即执行对称变换: $\(m_{i,j} \implies m_{j,i}\)$
  • 同理,若矩阵存储的是下三角(\(i \ge j\)$ \text{),对待求元素} $\(m_{i,j}\)$ \text{当} $\(i < j\)$ \text{时,必须转换为} $\(m_{j,i}\) 再代入下三角公式。

3. 公式现推及极值验证法(防死记硬背)

考试中切忌机械套用公式,推荐通过以下“极值代入检验法”快速锁定通式中的常数项: * 验证三对角矩阵行优先通式: 设映射关系形式为 \(k = 2i + j + C\)。 代入第一个非零元素 \(m_{1,1}\)$ \text{(对应下标} $\(k = 0\)): $\(0 = 2(1) + 1 + C \implies C = -3\)$ 即可瞬间确认通式 \(k = 2i + j - 3\),无需耗费时间进行冗长推导。 * 验证对称矩阵下三角行优先通式: 代入第 1 行第 1 个元素 \(m_{1,1}\),下标应为 0: $\(\frac{1 \times 0}{2} + 1 - 1 = 0\)$ 代入第 2 行第 1 个元素 \(m_{2,1}\),下标应为 1: $\(\frac{2 \times 1}{2} + 1 - 1 = 1\)$ 公式 \(\frac{i(i-1)}{2} + j - 1\) 完全吻合。

4. 稀疏矩阵概念辨析陷阱

  • 邻接矩阵是图的顺序存储结构,虽然图的邻接矩阵在边稀疏时表现为稀疏矩阵,但它未对空间进行压缩,不属于稀疏矩阵的压缩存储结构。
  • 三元组顺序表属于顺序存储,十字链表属于链式存储。三元组表中必须记录总行数、总列数、非零元总数;十字链表结点的指针方向为:right 沿行向右链接列标递增结点,down 沿列向下链接行标递增结点。

五、 考点速记清单

  1. 对称矩阵存储单元数:\(n\)$ \text{阶对称矩阵压缩存储需} $\(\frac{n(n+1)}{2}\) 个存储单元。
  2. 对称矩阵下标映射口诀:
  3. 下三角行优先:\(k = \frac{i(i-1)}{2} + j - 1\)(\(i \ge j\));
  4. 上三角列优先:\(k = \frac{j(j-1)}{2} + i - 1\)(\(i \le j\));
  5. 上三角行优先:\(k = \frac{(i-1)(2n-i+2)}{2} + j - i\)(\(i \le j\));
  6. 若坐标越界,直接互换 \(i, j\)。
  7. 三对角矩阵核心公式:
  8. 非零元总数:\(3n - 2\);
  9. 正向行优先映射(0-based):\(k = 2i + j - 3\);
  10. 逆向行号还原:\(i = \lfloor \frac{k+1}{3} \rfloor + 1\)$ \text{,列号} $\(j = k - 2i + 3\)。
  11. 三角矩阵存储空间:非零三角区 \(\frac{n(n+1)}{2}\)$ \text{个单元,最后 1 个单元专门存储常数} $\(C\)。
  12. 稀疏矩阵三元组必备元数据:必须包含矩阵总行数 rows、总列数 cols 以及非零元总数 nums。
  13. 十字链表结点构成:5 域结点 (row, col, value, right, down),行指针向右,列指针向下。