浙江大学：《数据结构与算法》第五章（5-3） 矩阵的压缩存储

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(11时,a1;=0,(1<=i,j=n

5.3.1 特殊矩阵 对称矩阵: aij = aji (1 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=j j(j-1)/2+i当i<j

对称矩阵 : aij = aji (1= 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 0 (当i<j

下三角矩阵 : 当i= j) 0 (当 i < j)

例5.4下三角矩阵 40000 31300 80 6795 如:a[5,3]=7 k=5(5-1)/2+3=13 故:sa[13]=7但a[3,5]=0

例5.4 下三角矩阵 4 0 0 0 0 5 2 0 0 0 A = 3 1 3 0 0 2 5 2 8 0 1 6 7 9 5 如: a[5,3] = 7 k = 5(5-1)/2 + 3 = 13 故:sa[13] = 7 但 a[3,5] = 0

对角矩阵 当i-j>1时,a;=0,(1<=i,jn) a11a12 21a22a23 0 0 Anxn 0 a32a33a34 0 0 00 nn-1 a 维数组SA[1..3米n-2]作为数组A下三角元素的 存储结构 SA[k]=[a1,a1,a1,a22,a2,a32,a33,a34,,anm-1,an k=12345678 3n-33n2

三对角矩阵 : 当|i-j| > 1时, aij = 0, (1<=i,j<=n) a11 a12 0 0 ... 0 a21 a22 a23 0 ... 0 Anxn = 0 a32 a33 a34 ... 0 ...... 0 0 0 ... ann-1 ann 一维数组SA[1..3*n-2]作为数组A下三角元素的 存储结构: SA[k]=[a11,a12,a21,a22,a23,a32,a33,a34,...,ann-1,ann] k = 1 2 3 4 5 6 7 8 3n-3 3n-2

sa[k]和a[i,,j的一一对应关系 sa[k],k=3*(i-1)+j-i+1, j<=1

sa[k]和a[i,,j]的一一对应关系: sa[k], k = 3*(i-1) + j-i+1, a[i, j] = { 当 |i - j|1

例5.5三对角矩阵 43000 52200 A 01040 00287 00095 维数组SA[1..3*5-2]作为数组A的存储结构: SA=(4352210428795) 如:a[5,4]=9 k=3*(5-1)+4-5+1=12 故:sa[12]=9

例5.5 三对角矩阵 4 3 0 0 0 5 2 2 0 0 A = 0 1 0 4 0 0 0 2 8 7 0 0 0 9 5 一维数组SA[1..3*5-2]作为数组A的存储结构: SA=(4 3 5 2 2 1 0 4 2 8 7 9 5) 如: a[5,4] = 9 k = 3*(5-1) + 4-5+1 = 12 故:sa[12] = 9

5.3.2 稀疏矩阵 通常稀疏因子<0.05时称为稀疏矩阵. 例5.6 01290000 00-30015 0000000 12000180 M=|-30000140 9002400 00240000 T=00000-7 01800000 000000 1500-7000 0014000 000000 M: mu x nu(6x7 T: nu x mu(7x6 M是T的转置

5.3.2 稀 疏 矩 阵 通常稀疏因子<0.05时称为稀疏矩阵. 例5.6 0 12 9 0 0 0 0 0 0 -3 0 0 15 0 0 0 0 0 0 0 12 0 0 0 18 0 M= -3 0 0 0 0 14 0 9 0 0 24 0 0 0 0 24 0 0 0 0 T= 0 0 0 0 0 -7 0 18 0 0 0 0 0 0 0 0 0 0 0 15 0 0 -7 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 M: mu x nu (6x7) T: nu x mu (7x6) M是T的转置