数据结构8数组2.ppt

文档介绍：矩阵的压缩存储
矩阵: 二维数组
特殊矩阵: 大量重复元素或大量0元素
稀疏矩阵: 大量0元素
压缩存储: 重复元素只分配一个存储空间,0元素不分配存储空间
特殊矩阵
对称矩阵: 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 =
对称矩阵: 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
对称矩阵
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时, 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)
下三角矩阵
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时, 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,
a[i, j] = { 当|i - j|<=1
0 当|i - j|>1
三对角矩阵
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
稀疏矩阵 通常稀疏因子<.

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的转置