高中信息技术竞赛班数据结构专项培训教程05矩阵的压缩存储教案.doc

§5 矩阵的压缩存储
a11 0 0 0 0
a21 a22 0 0 0
a31 a32 a33 0 0
a41 a42 a43 a44 0
a51 a52 a53 a54 a55
上三角矩阵
§5.1 特殊矩阵
§5.1.1 三角矩阵与对称矩阵
设有矩阵A : array [1..n , 1..n] of Atype；
三角矩阵：
若A的对角线以上（或以下）的元素均为零。
对称矩阵：
a11 a12 a13 a14 a15
a21 a22 a23 a24 a25
a31 a32 a33 a34 a35
a41 a42 a43 a44 a45
a51 a52 a53 a54 a55
对称矩阵
若A中的元素满足： aij = aji （1≤i，j≤n），
则称为n阶对称矩阵。

为了节省存储空间，三角矩阵和对称矩阵都不需存储对角线以上（或以下）的元素，一般采用一维数组的结构。
V：
1
2
3
4
5
6
7
8
9
10
……
a11
a21
a22
a31
a32
a33
a41
a42
a43
a44
……
此时需要 个元素的存储空间。
若将上三角矩阵中的元素按行顺序存储到V中，则V[k]与A[i, j]的对应关系是：
k = ①
a11 a12 a13 a14 a15
0 a22 a23 a24 a25
0 0 a33 a34 a35
0 0 0 a44 a45
0 0 0 0 a55
下三角矩阵
若将下三角矩阵中的元素按行顺序存储到V中，则V[k]与A[i, j]的对应关系是：
k= ②

§5.1.2 带状矩阵

在n×n的矩阵中，若所有非零元素均集中在以对角线为中的带状区中，该带状区包括主对角线上面和下面各k条对角线以及主对角线上的元素，这种矩阵称带状矩阵。
主对角线
k条对角线
k条对角线

11 2 3 0 0 0
4 2 10 13 0 0
5 12 7 6 8 0
0 20 17 9 11 15
0 0 6 1 14 21
0 0 0 2 18 3
k=2的带状矩阵

在带状矩阵A中，i – j > k或 ③ 时，A[ i , j ] = 0 。
对于带状区以外的0元素可不必存储，而只存储带状区中的元素。带状区中有
④ 个元素，但为了方便起见，每行当作2k+1个元素来存
储，此时存储的元素个数为 (2k+1)×n个。
【参考答案】：
① i×(i-1) / 2 + j
② (n+(n-i+1))×(i-1) + (j-i+1)
③ j - i > k
④ n×n – (n-k)×(n–k–1)

§5.2 稀疏矩阵
大多数元素的值为零的矩阵称为稀疏矩阵，为了节省存储空间，可以采取三元组或十字链表等方法来存储。
§5.2.1 三元组表示法
三元组表示法是用三元组（i , j , v）表示矩阵的每个非零元素。
第一行的i , j , v分别表示矩阵A的行数、列数、非零元素个数，第二行开始的 i , j , v分别表示矩阵A中每个非零元素的行下标、列下标、元素的值。
15
0
0
22
0
－15
0
11
3
0
0
0
0
0
0
－6
0
0
0
0
0
0
0
0
91
0
0
0
0
0
0
0
28
0
0
0
6 6 8
1 1 15
1 4 22
1 6 -15
2 2 11
2 3 3
3 4 -6
5 1 91
6 3 28
T =
A =
【例5.2_1】

§5.2.2三元组矩阵转置
对矩阵的运算有许多，如两个矩阵相加、相乘、转置……等。转置是一种简单的矩阵运算，对于一个m×n的矩阵M，它的转置矩阵N是一个n×m的矩阵，且M（i , j）＝N（j , i）。
N＝
1 4
2 5
3 6
【例5.2_2】

1 2 3
4 5 6
Ｍ＝

这里只讨论三元组的转置算法。
三元组的转置只需做到：
（1）将三元组中的行列值相互交换；
（2）将i、j相互调换；
（3）重排三元组中的次序
就可实现三元组的矩阵转置。
这里关键是如何重排三元组里的次序。
6 6 8
1 1 15
1 4 22
1 6 -15
2 2 11
2 3 3
3 4 -6
5 1 91
6 3 28
T =
6 6 8
1 1 15
4 1 22
6 1 -15
2 2 11
3 2 3
4 3 -6
1 5 91
3 6 28
=>
6 6 8
1 1 15
1 5 91
2 2 11
3 2 3
3 6 28
4 1 22
4 3 -6
6 1 -15
B =

§5.2.2 矩阵相乘
两个矩阵相乘是另一种常用的矩阵运算。
设： C ＝ A × B
A=(aij)为m×s的矩阵，B=(bij)是s×n的矩阵，则矩阵A与矩阵B相乘将得到一个m×n的矩阵C=(cij)，其中
cij＝ai1b1j + ai2b2j + …… + aisbsj （i = 1 , 2 ,…, m j = 1 , 2 ,…, n）
对于非压缩矩阵，算法如下：
for i := 1 to m do
for j := 1 to n do begin
C[ i , j ] := 0；
for k := 1 to s do
C[ i , j ] := C[ i , j ] + A[ i , k ] * B[ k , j ]；
end；
当A和B是稀疏矩阵，并分别用三元组M、N存储时，应如何处理？
注意 1：两个稀疏矩阵相乘的积不一定是稀疏矩阵；
2：即使cij＝ai1b1j + ai2b2j + …… + aisbsj中的每个分项aikbkj均不为零，其累加值Cij也有可能为零。

【练习】输入M、N两个三元组，分别表示A、B两个稀疏矩阵，请计算A、B的乘积C，输出C的（压缩存储）三元组Y。
输入格式： （输入文件 syz.in）
第1行： i1 j1 v1 (分别表示A的行数、列数、非零元素个数)
第2至v1+1行： ai aj av (行下标、列下标、元素的值)
第v1+2行： i2 j2 v2 (B的行数、列数、非零元素个数)
第v1+3至v1+v2+2行：bi bj bv
输出格式： （输出文件 syz.out）
第1行： i3 j3 v3 (C的行数、列数、非零元素个数)
第2至v3+1行： ci cj cv