特殊矩阵的压缩存储

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

对称矩阵

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

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

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

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

下三角矩阵

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

三对角矩阵(带状矩阵)

三对角矩阵只有主对角线及其上下两条对角线共 3n−23n-2 个非零元素,按行优先存储时,A[i][j]A[i][j](∣i−j∣≤1|i-j| \le 1)的下标为:

k=2i+jk = 2i + j

推导:第 i 行之前共有 3(i)−13(i) - 1 个元素(前 i 行每行 3 个,除第 0 行是 2 个),第 i 行第 j 列在本行内是第 j−(i−1)j-(i-1) 个。

习题

习题 1

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

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

对称矩阵压缩存储下三角存储下标计算

解题思路:

本题考查对称矩阵按下三角压缩存储时元素下标的计算。先确认所求元素落在下三角区域,再套用下三角压缩存储的下标公式,最后代入 ii、jj 求出它在一维数组 B 中的位置。

详细步骤:

  1. 对称矩阵满足 A[i][j]=A[j][i]A[i][j] = A[j][i],压缩存储时只保留下三角(含对角线)部分,因此 A[5][3]A[5][3] 可以直接在下三角中定位。
  2. 下三角中元素 A[i][j]A[i][j](i≥ji \ge j)的下标为 k=i(i+1)2+jk = \frac{i(i+1)}{2} + j,其中 i(i+1)2\frac{i(i+1)}{2} 是第 ii 行之前所有行的元素总数,jj 是第 ii 行内第 jj 列之前的元素个数。
  3. 代入 i=5i = 5、j=3j = 3:k=5×62+3=15+3=15k = \frac{5\times6}{2} + 3 = 15 + 3 = 15,对照选项可知应选 C。

最终答案:

C(15)。

习题 2

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

对称矩阵压缩存储下三角存储下标计算

解题思路:

本题考查对称矩阵压缩存储公式的推导思路。答题时先由对称性说明只需存下三角,再计算下三角的元素总数,最后把下标拆成“之前各行的元素总数”与“本行内的偏移”两部分来推导公式。

详细步骤:

  1. 由对称性 A[i][j]=A[j][i]A[i][j] = A[j][i] 可知,只需存下三角(含对角线)即可,下三角共有 1+2+⋯+n=n(n+1)21+2+\cdots+n = \frac{n(n+1)}{2} 个元素。
  2. 把下标拆成两部分:第 ii 行之前所有行的元素总数为 i(i+1)2\frac{i(i+1)}{2},第 ii 行内第 jj 列之前的元素数为 jj。
  3. 两部分相加即得下标公式 k=i(i+1)2+jk = \frac{i(i+1)}{2} + j(适用于 i≥ji \ge j)。

最终答案:

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

发现内容有问题?

告诉我们哪里需要改进。