若i≤j,数组元素A[]在数组B中的存放位 置为 n+(m-1)+(n-2)+…+(n-i计1)+ji= =(2*n-i计1)*i/2+j-i= =(2*n-i-1)*i/2+i 若i>j,数组元素A川在矩阵的下三角部 分，在数组B中没有存放。因此，找它的 对称元素A[i]。A[i在数组B的第(2*n- 1)*j/2+i的位置中找到。 21
n 若 i j，数组元素A[i][j]在数组B中的存放位 置为 n + (n-1) + (n-2) + + (n-i+1) + j-i = = (2*n-i+1) * i / 2 + j-i = = (2*n-i-1) * i / 2 + j n 若i > j，数组元素A[i][j]在矩阵的下三角部 分，在数组 B 中没有存放。因此，找它的 对称元素A[j][i]。A[j][i]在数组 B 的第 (2*nj-1) * j / 2 + i 的位置中找到。 21
三对角矩阵的压缩存储 012345678 9 10 B 01a10a1a12421a2223a-ln-2 An-1n-1 22
B a00 a01 a10 a11 a12 a21 a22 a23 … an-1n-2 an-1n-1 0 1 2 3 4 5 6 7 8 9 10 22
·三对角矩阵中除主对角线及在主对角线上下 最临近的两条对角线上的元素外，所有其它 元素均为0。总共有3n-2个非零元素。 将三对角矩阵A中三条对角线上的元素按行存 放在一维数组B中，且M存放于B[0]。 在三条对角线上的元素a满足 0≤i≤n-1,i-1≤i≤it1 在一维数组B中A[1在第i行，它前面有 3*i-1个非零元素，在本行中第j列前面有j 什1个，所以元素A[川在B中位置为k= 2*i+j。 23
• 三对角矩阵中除主对角线及在主对角线上 下 最临近的两条对角线上的元素外，所有其它 元素均为0。总共有3n-2个非零元素。 • 将三对角矩阵A中三条对角线上的元素按行存 放在一维数组 B 中，且a00存放于B[0]。 • 在三条对角线上的元素aij满足 0 i n-1, i-1 j i+1 • 在一维数组 B 中 A[i][j] 在第 i 行，它前面有 3*i-1 个非零元素, 在本行中第 j 列前面有 ji+1 个，所以元素 A[i][j] 在 B 中位置为 k = 2*i + j。 23
·若已知三对角矩阵中某元素A川在数组 B]存放于第k个位置，则有 i=L(k+1)/3J j=k-2*i ·例如，当k=8时， i=L(8+1)/3J=3,j=8-2*3=2 当k=10时， i=L(10+1)/3=3,i=10-2*3=4 24
• 若已知三对角矩阵中某元素 A[i][j] 在数组 B[ ] 存放于第 k 个位置，则有 i = (k + 1) / 3 j = k - 2 * i • 例如，当 k = 8 时， i = (8+1) / 3 = 3, j = 8 - 2*3 = 2 当 k = 10 时， i = (10+1) / 3 = 3, j = 10 - 2*3 = 4 24
稀疏矩阵(Sparse Matrix) 0 000 91 0 002200 15 0) 0 11 0 00 0110 0 0 0 17 0 0 0 0 0 0 0 0 -6 0 0 0 8 0 0 22 0 0 0039 0 B16= 0 0 0 0 0 910 00 00 0 0 39 0028000 0 0 1 0 0 50 0 000 ■设矩阵A中有S个非零元素，若s远远小于 矩阵元素的总数（即s<<mXn),则称A 为稀疏矩阵。 25
A6 7 B7 6 0 0 0 22 0 0 15 0 11 0 0 0 17 0 0 0 0 6 0 0 0 0 0 0 0 0 39 0 91 0 0 0 0 0 0 0 0 28 0 0 0 0 0 0 0 0 91 0 0 11 0 0 0 0 0 0 0 0 0 28 22 0 6 0 0 0 0 0 0 0 0 0 0 17 0 39 0 0 15 0 0 0 0 0 稀疏矩阵 (Sparse Matrix) n 设矩阵 A 中有 s 个非零元素，若 s 远远小于 矩阵元素的总数（即s << m×n），则称 A 为稀疏矩阵。 25