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

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中的元素满足： 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= 金山中学计算机竞赛班教程数据结构5.1.2 带状矩阵54在nn的矩阵中，若所有非零元素均集中在以对角线为中的带状区中，该带状区包括主对角线上面和下面各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个元素来存储，此时存储的元素个数为 (2k+1)n个。【参考答案】： i(i-1) / 2 + j (n+(n-i+1)(i-1) + (j-i+1) j - i k nn (n-k)(nk1)5.2 稀疏矩阵 大多数元素的值为零的矩阵称为稀疏矩阵，为了节省存储空间，可以采取三元组或十字链表等方法来存储。 5.2.1 三元组表示法三元组表示法是用三元组（i , j , v）表示矩阵的每个非零元素。第一行的i , j , v分别表示矩阵a的行数、列数、非零元素个数，第二行开始的 i , j , v分别表示矩阵a中每个非零元素的行下标、列下标、元素的值。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三元组矩阵转置对矩阵的运算有许多，如两个矩阵相加、相乘、转置等。转置是一种简单的矩阵运算，对于一个mn的矩阵m，它的转置矩阵n是一个nm的矩阵，且m（i , j）n（j , i）。n1 42 53 6【例5.2_2】1 2 34 5 6这里只讨论三元组的转置算法。三元组的转置只需做到：（1）将三元组中的行列值相互交换；（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)为ms的矩阵，b=(bij)是sn的矩阵，则矩阵a与矩阵b相乘将得到一个mn的矩阵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行： i2