精品文档
§5 矩阵的压缩存储
§5.1 特殊矩阵
§5.1.1 三角矩阵与对称矩阵
设有矩阵A : array [1..n , 1..n] of Atype； 三角矩阵：
若A的对角线以上（或以下）的元素均为零。
对称矩阵：
若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 …… 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 上三角矩阵 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 对称矩阵
此时需要 个元素的存储空间。
若将上三角矩阵中的元素按行顺序存储到V中，则V[k]与A[i, j]的对应关系是： k = ①
若将下三角矩阵中的元素按行顺序存储到V中，则V[k]与A[i, j]的对应关系是： k= ②
§5.1.2 带状矩阵
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
下三角矩阵
在n×n的矩阵中，若所有非零元素均集中在以对角线为中的带状
区中，该带状区包括主对角线上面和下面各k条对角线以及主对角线上的元素，这种矩阵称带状矩阵。
k条对角线 11 2 3 0 0 0
4 2 10 13 0 0
k条对角线
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的带状矩阵 主对角线
。 1欢迎下载
精品文档
在带状矩阵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中每个非零元素的行下标、列下标、元素的值。 【例5.2_1】
15 0 0 22 0
A =
－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
T =
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
§5.2.2三元组矩阵转置
对矩阵的运算有许多，如两个矩阵相加、相乘、转置……等。转置是一种简单的矩阵运算，对于一个m×n的矩阵M，它的转置矩阵N是一个n×m的矩阵，且M（i , j）＝N（j , i）。
【例5.2_2】
1 4
1 2 3
Ｍ＝ N＝ 2 5
4 5 6 3 6
这里只讨论三元组的转置算法。 三元组的转置只需做到：
（1）将三元组中的行列值相互交换； （2）将i、j相互调换； （3）重排三元组中的次序
。 2欢迎下载
精品文档
就可实现三元组的矩阵转置。 这里关键是如何重排三元组里的次序。
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
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
T = => 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的行数、列数、非零元素个数)
。 3欢迎下载
精品文档
第2至v3+1行： ci cj cv
。 4欢迎下载
高中信息技术-竞赛班数据结构专项培训教程-05矩阵的压缩存储教案
