特殊矩阵的压缩存储
特殊矩阵是指有大量相同元素或零元素的矩阵,可用一维数组压缩存储,节省空间。
对称矩阵
对称矩阵满足 A[i][j]=A[j][i],只需存储下三角(含对角线)部分,共 2n(n+1) 个元素。
下三角元素 A[i][j](i≥j)在一维数组 B[0..n(n+1)/2−1] 中的下标为:
k=2i(i+1)+j
推导:第 i 行之前共有 0+1+2+⋯+i=2i(i+1) 个元素,第 i 行第 j 列之前还有 j 个元素。
下三角矩阵
与对称矩阵存储方式相同,但上三角部分统一存一个常数,共 2n(n+1)+1 个存储单元。
三对角矩阵(带状矩阵)
三对角矩阵只有主对角线及其上下两条对角线共 3n−2 个非零元素,按行优先存储时,A[i][j](∣i−j∣≤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
对称矩阵压缩存储下三角存储下标计算
解题思路:
本题考查对称矩阵按下三角压缩存储时元素下标的计算。先确认所求元素落在下三角区域,再套用下三角压缩存储的下标公式,最后代入 i、j 求出它在一维数组 B 中的位置。
详细步骤:
- 对称矩阵满足 A[i][j]=A[j][i],压缩存储时只保留下三角(含对角线)部分,因此 A[5][3] 可以直接在下三角中定位。
- 下三角中元素 A[i][j](i≥j)的下标为 k=2i(i+1)+j,其中 2i(i+1) 是第 i 行之前所有行的元素总数,j 是第 i 行内第 j 列之前的元素个数。
- 代入 i=5、j=3:k=25×6+3=15+3=15,对照选项可知应选 C。
最终答案:
C(15)。
习题 2
简述对称矩阵压缩存储的推导思路。
对称矩阵压缩存储下三角存储下标计算
解题思路:
本题考查对称矩阵压缩存储公式的推导思路。答题时先由对称性说明只需存下三角,再计算下三角的元素总数,最后把下标拆成“之前各行的元素总数”与“本行内的偏移”两部分来推导公式。
详细步骤:
- 由对称性 A[i][j]=A[j][i] 可知,只需存下三角(含对角线)即可,下三角共有 1+2+⋯+n=2n(n+1) 个元素。
- 把下标拆成两部分:第 i 行之前所有行的元素总数为 2i(i+1),第 i 行内第 j 列之前的元素数为 j。
- 两部分相加即得下标公式 k=2i(i+1)+j(适用于 i≥j)。
最终答案:
对称矩阵 A[i][j]=A[j][i],只存下三角(含对角线)即可。下三角共有 1+2+⋯+n=2n(n+1) 个元素。元素 A[i][j](i≥j)的下标 k=2i(i+1)+j:其中 2i(i+1) 是第 i 行之前所有行的元素总数,j 是第 i 行内第 j 列之前的元素数。