广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程..pdf

《广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程..pdf》由会员分享，可在线阅读，更多相关《广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程..pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、5 5矩阵的压缩存储矩阵的压缩存储5.15.1特殊矩阵特殊矩阵5.1.15.1.1 三角矩阵与对称矩阵三角矩阵与对称矩阵设有矩阵 A:array 1.n,1.n of Atype；三角矩阵：三角矩阵：若 A 的对角线以上（或以下）的元素均为零。对称矩阵：对称矩阵：若 A 中的元素满足：aij=aji（1i，jn），则称为 n 阶对称矩阵。为了节省存储空间，三角矩阵和对称矩阵都不需存储对角线以上（或以下）的元素，一般采用一维数组的结构。V：12345678910a11a21a22a31a32a33a41a42a43a44a110000a21 a22000a31 a32 a3300a41 a42

2、a43 a440a51 a52 a53 a54 a55上三角矩阵a11a12 a13 a14 a15a21 a22 a23 a24 a25a31 a32 a33 a34 a35a41 a42 a43 a44 a45a51 a52 a53 a54 a55对称矩阵此时需要个元素的存储空间。若将上三角矩阵中的元素按行顺序存储到V 中，则 Vk与 Ai,j的对应关系是：k=若将下三角矩阵中的元素按行顺序存储到V 中，则 Vk与 Ai,j的对应关系是：k=5.1.25.1.2 带状矩阵带状矩阵a11 a12 a13 a14 a150a22 a23 a24 a2500a33 a34 a35000a44 a

3、450000a55下三角矩阵在 nn 的矩阵中，若所有非零元素均集中在以对角线为中的带状区中，该带状区包括主对角线上面和下面各 k 条对角线以及主对角线上的元素，这种矩阵称带状矩阵。k 条对角线11 230004210 1300k 条对角线5127680020 17 9 11 150061 14 210002183k=2 的带状矩阵主对角线金山中学计算机竞赛班教程数据结构在带状矩阵 A 中，i j k 或 时，A i,j =0。对于带状区以外的 0 元素可不必存储，而只存储带状区中的元素。带状区中有 个元素，但为了方便起见，每行当作 2k+1 个元素来存储，此时存储的元素个数为(2k+1)n

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

5、28000T=6681115142216-15221123334-6519163285.2.25.2.2 三元组矩阵转置三元组矩阵转置对矩阵的运算有许多，如两个矩阵相加、相乘、转置等。转置是一种简单的矩阵运算，对于一个 mn 的矩阵 M，它的转置矩阵 N 是一个 nm 的矩阵，且 M（i,j）N（j,i）。【例 5.2_2】14123N2545636这里只讨论三元组的转置算法。三元组的转置只需做到：（1）将三元组中的行列值相互交换；（2）将 i、j 相互调换；（3）重排三元组中的次序52金山中学计算机竞赛班教程数据结构就可实现三元组的矩阵转置。这里关键是如何重排三元组里的次序。66811151

6、42216-15221123334-6519163286681115412261-15221132343-6159136286681115159122113233628412243-661-15T=B=5.2.25.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 d

7、o 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 j2 v2 (B的行数、列数、非零元素个数)第 v1+3 至 v1+v2+2 行：bi bj bv输出格式：（输出文件 syz.out）第 1 行：i3 j3 v3 (C的行数、列数、非零元素个数)53金山中学计算机竞赛班教程数据结构第 2 至 v3+1 行：ci cj cv54