特殊矩阵的压缩存储

特殊矩阵是指有大量相同元素或零元素的矩阵，可用一维数组压缩存储，节省空间。

对称矩阵

对称矩阵满足 $A[i][j] = A[j][i]$ ，只需存储下三角（含对角线）部分，共 $\frac{n(n+1)}{2}$ 个元素。

下三角元素 $A[i][j]$ （ $i \ge j$ ）在一维数组 $B[0..n(n+1)/2-1]$ 中的下标为：

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

推导：第 i 行之前共有 $0+1+2+\cdots+i = \frac{i(i+1)}{2}$ 个元素，第 i 行第 j 列之前还有 j 个元素。

下三角矩阵

与对称矩阵存储方式相同，但上三角部分统一存一个常数，共 $\frac{n(n+1)}{2} + 1$ 个存储单元。

三对角矩阵（带状矩阵）

三对角矩阵只有主对角线及其上下两条对角线共 $3n-2$ 个非零元素，按行优先存储时， $A[i][j]$ （ $|i-j| \le 1$ ）的下标为：

$k = 2i + j$

推导：第 i 行之前共有 $3(i) - 1$ 个元素（前 i 行每行 3 个，除第 0 行是 2 个），第 i 行第 j 列在本行内是第 $j-(i-1)$ 个。

习题

习题 1

设有一个 10×10 的对称矩阵 A，采用压缩存储方式，以下三角形式存储到一维数组 B 中，则 A[5][3]（下标从 0 开始）在 B 中的下标是（）

A. 13 B. 14 C. 15 D. 16

答案与解析

答案：C

解析：对称矩阵压缩存储，元素 $A[i][j]$ （ $i \ge j$ ）下标 $k = \frac{i(i+1)}{2} + j$ 。代入 i=5, j=3： $k = \frac{5\times6}{2} + 3 = 15 + 3 = 15$ 。

习题 2

简述对称矩阵压缩存储的推导思路。

答案与解析

对称矩阵 $A[i][j] = A[j][i]$ ，只存下三角（含对角线）即可。下三角共有 $1+2+\cdots+n = \frac{n(n+1)}{2}$ 个元素。元素 $A[i][j]$ （ $i \ge j$ ）的下标 $k = \frac{i(i+1)}{2} + j$ ：其中 $\frac{i(i+1)}{2}$ 是第 i 行之前所有行的元素总数，j 是第 i 行内第 j 列之前的元素数。

上一章节多维数组的存储一维、二维数组的存储结构，行优先与列优先的地址计算公式。

下一章节稀疏矩阵稀疏矩阵的三元组表示法与十字链表法。