00 21 n-10 (a)一个下三角矩阵 01234 67 n(n+1) n(n+1) 2 n(n+1) 2 aooJa10 a11 a22 a3d a31 an-In-3 an-1n-2 an-ln-1 (b)下三角矩阵的压缩存储形式 图5-4对称矩阵及用下三角压缩存储
1 0 1 1 1 2 1 1 2 0 2 1 2 2 1 0 1 1 0 0 ... ... ... ... ... ... an− an− an− an− n− a a a a a a (a) 一个下三角矩阵 a00 a10 a11 a20 a21 a22 a30 a31 …… an-1n-3 an-1n-2 an-1n-1 0 1 2 3 4 5 6 7 …… 2 n(n+1) -3 2 n(n+1) -2 2 n(n+1) -1 (b) 下三角矩阵的压缩存储形式 图 5-4 对称矩阵及用下三角压缩存储
?(2)只存放上三角部分 对于对称阵,除了用下三角形式存放外,还可以用上 三角形式存放,这时aO[0]存入s[0],a[o]入s[1, a[OI[2]存入S2],…,具体参见图5-5。这时k]与a[j[j 的对应关系可以按下面方法推出: 当时,a;在上三角部分中,前面共有i行,共有n+n 1++n(i1)n-“2个元素,而是本行第个元素, 入故k=正“2+,当时,交换i与即可。故队]与a 的对应关系为 i(-1) 2+ k- j(-1) n - 当ii
(2) 只存放上三角部分 对于对称阵，除了用下三角形式存放外，还可以用上 三角形式存放，这时a[0][0]存入 s[0],a[0][1]存入s[1]， a[0][2]存入 s[2]，…，具体参见图5-5。这时s[k]与a[i][j] 的对应关系可以按下面方法推出： 当i≤j时，aij在上三角部分中，前面共有i行，共有n+n- 1+…+n-(i-1)=i*n- 个元素，而aij是本行第j-i个元素， 故k=i*n- +j-i，当i>j时，交换i与j即可。故s[k]与a[i][j] 的对应关系为： 2 i(i−1) 2 i(i−1) i*n- +j-i 当i≤j k= j*n- +i-j 当i>j 2 i(i−1) 2 j( j−1)
aoo aoi a02 12 a (a)一个上三角矩阵 01234 m(n+1)-3m+1)-2m+ aoojao1 a02 a05 aod ao7 an-2n-2 an-2n-I an-In-1 b)上三角矩阵的压缩存储形式 图5-5对称矩阵及用上三角压缩存储
1 1 22 2 1 11 12 1 1 00 01 02 0 1 ... ... ... ... ... ... ... ... − − − − − n n n n n a a a a a a a a a a (a) 一个上三角矩阵 a00 a01 a02 a03 a04 a05 a06 a07 …… an-2n-2 an-2n-1 an-1n-1 0 1 2 3 4 5 6 7 …… 2 n(n+1) -3 2 n(n+1) -2 2 n(n+1) -1 (b) 上三角矩阵的压缩存储形式 图 5-5 对称矩阵及用上三角压缩存储