广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 05矩阵的压缩存储教案

1、§5 矩阵的压缩存储a11 0 0 0 0a21 a22 0 0 0a31 a32 a33 0 0a41 a42 a43 a44 0a51 a52 a53 a54 a55上三角矩阵§5.1 特殊矩阵§5.1.1 三角矩阵与对称矩阵设有矩阵A : array 1.n , 1.n of Atype；三角矩阵：若A的对角线以上（或以下）的元素均为零。 对称矩阵：a11 a12 a13 a14 a15a21 a22 a23 a24 a25a31 a32 a33 a34 a35a41 a42 a43 a44 a45a51 a52 a53 a54 a55对称矩阵若A中的元素满

2、足： aij = aji （1i，jn），则称为n阶对称矩阵。为了节省存储空间，三角矩阵和对称矩阵都不需存储对角线以上（或以下）的元素，一般采用一维数组的结构。V：12345678910a11a21a22a31a32a33a41a42a43a44此时需要 个元素的存储空间。若将上三角矩阵中的元素按行顺序存储到V中，则Vk与Ai, j的对应关系是： k = a11 a12 a13 a14 a150 a22 a23 a24 a250 0 a33 a34 a350 0 0 a44 a450 0 0 0 a55下三角矩阵若将下三角矩阵中的元素按行顺序存储到V中，则Vk与Ai, j的对应关系是： k=

3、§5.1.2 带状矩阵在n×n的矩阵中，若所有非零元素均集中在以对角线为中的带状区中，该带状区包括主对角线上面和下面各k条对角线以及主对角线上的元素，这种矩阵称带状矩阵。主对角线k条对角线k条对角线11 2 3 0 0 04 2 10 13 0 05 12 7 6 8 00 20 17 9 11 150 0 6 1 14 210 0 0 2 18 3k=2的带状矩阵在带状矩阵A中，i j > k或 时，A i , j = 0 。对于带状区以外的0元素可不必存储，而只存储带状区中的元素。带状区中有 个元素，但为了方便起见，每行当作2k+1个元素来存储，此时存储的元素个数

4、为 (2k+1)×n个。【参考答案】： i×(i-1) / 2 + j (n+(n-i+1)×(i-1) + (j-i+1) j - i > k n×n (n-k)×(nk1)§5.2 稀疏矩阵 大多数元素的值为零的矩阵称为稀疏矩阵，为了节省存储空间，可以采取三元组或十字链表等方法来存储。 §5.2.1 三元组表示法三元组表示法是用三元组（i , j , v）表示矩阵的每个非零元素。第一行的i , j , v分别表示矩阵A的行数、列数、非零元素个数，第二行开始的 i , j , v分别表示矩阵A中每个非零元素的行下标、

5、列下标、元素的值。1500220150113000000600000000910000000280006 6 81 1 151 4 221 6 -152 2 112 3 33 4 -65 1 916 3 28T =A = 【例5.2_1】 §5.2.2三元组矩阵转置对矩阵的运算有许多，如两个矩阵相加、相乘、转置等。转置是一种简单的矩阵运算，对于一个m×n的矩阵M，它的转置矩阵N是一个n×m的矩阵，且M（i , j）N（j , i）。N1 42 53 6【例5.2_2】1 2 34 5 6这里只讨论三元组的转置算法。三元组的转置只需做到：（1）将三元组中的行列值相互

6、交换；（2）将i、j相互调换；（3）重排三元组中的次序就可实现三元组的矩阵转置。 这里关键是如何重排三元组里的次序。6 6 81 1 151 4 221 6 -152 2 112 3 33 4 -65 1 916 3 28T =6 6 81 1 154 1 226 1 -152 2 113 2 34 3 -61 5 913 6 28=>6 6 81 1 151 5 912 2 113 2 33 6 284 1 224 3 -66 1 -15B = §5.2.2 矩阵相乘两个矩阵相乘是另一种常用的矩阵运算。设： C A × BA=(aij)为m×s的矩阵，B=

7、(bij)是s×n的矩阵，则矩阵A与矩阵B相乘将得到一个m×n的矩阵C=(cij)，其中 cijai1b1j + ai2b2j + + aisbsj （i = 1 , 2 , m j = 1 , 2 , n） 对于非压缩矩阵，算法如下： for i := 1 to m do for j := 1 to n do beginC 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：即使cijai1b1j + 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行