5.3矩阵的压缩存储 矩阵:二维数组 特殊矩阵:大量重复元素或大量0元素 稀疏矩阵:大量0元素 压缩存储:重复元素只分配一个存储空 间,0元素不分配存储空间
5.3 矩阵的压缩存储 矩阵: 二维数组 特殊矩阵: 大量重复元素或大量0元素 稀疏矩阵: 大量0元素 压缩存储: 重复元素只分配一个存储空 间,0元素不分配存储空间
5.3.1特殊矩阵 11 13 21 a 2 a 2a23 Anxn a31a32a33 an n1 n n 3 nn 对称矩阵:a1;=a1(1<=i,j-n) 下三角矩阵:当i<j时,aij=0,(1<=i,j=n 三对角矩阵:当|1-j>1时,a1;=0,(1<=i,j=n
5.3.1 特殊矩阵 对称矩阵: aij = aji (1<=i,j<=n) 下三角矩阵: 当i<j时, aij = 0, (1<=i,j<=n) 三对角矩阵: 当|i-j| > 1时, aij = 0, (1<=i,j<=n) a11 a12 a13 ... a1n a21 a22 a23 ... a2n a31 a32 a33 ... a3n ...... an1 an2 an3 ... ann Anxn =
对称矩阵:a;=an(1<=i,j=n 存储元素数:1+2+.+n=n(n+1)/2 维数组SA[1.n(n+1)/2]作为数组A下三角元素的 存储结构 SA[k]=[a1,a21,a22,a31, n(n-1)/2+1n(n+1)/2 SA[k]和A[i,j的一一对应关系: (i-1)/2+j当i>=j j(j-1)/2+i当i<j
对称矩阵 : aij = aji (1<=i,j<=n) 存储元素数: 1+2+...+n = n(n+1)/2 一维数组SA[1..n(n+1)/2]作为数组A下三角元素的 存储结构: SA[k] = [a11, a21, a22, a31, ... , an1, ... , ann] k = 1 2 3 4 n(n-1)/2+1 n(n+1)/2 SA[k]和A[i, j]的一一对应关系: i(i-1)/2 + j 当 i >= j k = { j(j-1)/2 + i 当 i < j
例5.3对称矩阵 4532 31327 25289 4532 13 6795 28 n=5,1+2+3+4+5=5*(5+1)/2=15 维数组SA[1..15]作为数组A的存储结构: SA=(452313252816795) 如:a[5,3]=a[3,5] k=5(5-1)/2+3=13 故:sa[13]=7
例5.3 对称矩阵 n = 5, 1+2+3+4+5 = 5*(5+1)/2 = 15 一维数组SA[1..15]作为数组A的存储结构: SA=(4 5 2 3 1 3 2 5 2 8 1 6 7 9 5) 如: a[5,3] = a[3,5] = 7 k = 5(5-1)/2 + 3 = 13 故:sa[13] = 7 4 5 3 2 1 5 2 1 5 6 3 1 3 2 7 2 5 2 8 9 1 6 7 9 5 A = 4 5 2 0 3 1 3 2 5 2 8 1 6 7 9 5 A =
下 角矩阵 当i<j时,a;=0,(1<=i,jn 同样用一维数组SA[1.n(n+1)/2]作为数组A非 零元素的存储结构: sa[k]和a[i,j的一一对应关系 sa[k],k=i(i-1)/2+j ali, jl=t (当i>=j 0 (当i<j
下三角矩阵 : 当i<j时, aij = 0, (1<=i, j<=n) 同样用一维数组SA[1..n(n+1)/2]作为数组A非 零元素的存储结构: sa[k]和a[i, j]的一一对应关系: sa[k], k = i(i-1)/2 + j a[i, j] = { (当 i >= j) 0 (当 i < j)