13.2.3 矩阵

矩阵本质上可以用二维数组存储，但特殊矩阵中有大量重复值或零值，直接存储会浪费空间。压缩存储就是只保存必要信息，再通过下标映射恢复元素位置。

特殊矩阵为什么能压缩

类型	规律	是否需要存全部元素
对称矩阵	$a_{ij}=a_{ji}$	不需要，只存一半加主对角线
上三角矩阵	主对角线以下元素为 0 或同一常数	只存上三角部分
下三角矩阵	主对角线以上元素为 0 或同一常数	只存下三角部分
稀疏矩阵	非零元素很少	只存非零元素及其位置

压缩存储的考试重点是：二维下标 $(i,j)$ 映射到一维数组下标 $k$。

下三角矩阵按行压缩

设 $n\times n$ 下三角矩阵按行优先存储，且下标从 1 开始，只存 $i\ge j$ 的元素。

第 i 行之前共有：

$$1+2+\cdots +(i-1)=\frac{i(i-1)}{2}$$

第 i 行中，A[i][j] 前面有 j-1 个元素。因此若一维数组下标从 0 开始：

$$k=\frac{i(i-1)}{2}+(j-1)$$

若一维数组下标从 1 开始：

$$k=\frac{i(i-1)}{2}+j$$

上三角矩阵按行压缩

上三角矩阵只存 $i\le j$ 的元素。第 i 行之前已存：

$$n+(n-1)+\cdots +(n-i+2)=\frac{(i-1)(2n-i+2)}{2}$$

第 i 行中，A[i][j] 是从 j=i 开始的第 j-i+1 个元素。若一维数组下标从 1 开始：

$$k=\frac{(i-1)(2n-i+2)}{2}+(j-i+1)$$

若题目用 0 起始下标，要整体再减 1。

对称矩阵

对称矩阵只需保存上三角或下三角。若保存下三角：

元素位置	处理
$i\ge j$	按下三角公式直接定位
$i<j$	利用对称性转为 $A[j][i]$

也就是说，访问 $A[i][j]$ 时先判断是否在已存区域，不在就交换行列。

稀疏矩阵：三元组存储

稀疏矩阵中大部分元素为 0。如果还用二维数组存储，空间浪费严重。常用三元组保存非零元素：

行号	列号	值
i	j	a[i][j]

三元组适合非零元素很少、矩阵规模很大的场景。代价是随机访问某个元素不如二维数组直接，需要查找对应三元组。

压缩存储的取舍

方式	优点	缺点
普通二维数组	访问直接，公式简单	对特殊矩阵浪费空间
三角/对称压缩	节省约一半空间	下标映射复杂，容易算错
稀疏三元组	非零元素少时极省空间	随机访问和矩阵运算实现更复杂

这种“技术迭代”的本质是用计算换空间：存储更省了，但访问时需要更多映射逻辑。

本节例题

单选

下标从 1 开始的下三角矩阵中，需要存储的元素满足：

Ai >= jBi < jCi + j = nDi = 0

自查清单

1. 能否推导下三角矩阵按行压缩的一维下标？
2. 能否说明对称矩阵访问上三角元素时为什么可以交换行列？
3. 能否判断稀疏矩阵三元组存储的优势和代价？