高中信息技术 竞赛班数据结构专项培训教程 05矩阵的压缩存储教案-人教版高中全册信息技术教案VIP免费

§5矩阵的压缩存储§5.1特殊矩阵§5.1.1三角矩阵与对称矩阵设有矩阵A:array[1..n,1..n]ofAtype；三角矩阵：若A的对角线以上（或以下）的元素均为零。对称矩阵：若A中的元素满足：aij=aji（1≤i，j≤n），则称为n阶对称矩阵。为了节省存储空间，三角矩阵和对称矩阵都不需存储对角线以上（或以下）的元素，一般采用一维数组的结构。12345678910……a11a21a22a31a32a33a41a42a43a44……此时需要个元素的存储空间。若将上三角矩阵中的元素按行顺序存储到V中，则V[k]与A[i,j]的对应关系是：k=①若将下三角矩阵中的元素按行顺序存储到V中，则V[k]与A[i,j]的对应关系是：k=②§5.1.2带状矩阵在n×n的矩阵中，若所有非零元素均集中在以对角线为中的带状区中，该带状区包括主对角线上面和下面各k条对角线以及主对角线上的元素，这种矩阵称带状矩阵。a110000a21a22000a31a32a3300a41a42a43a440a51a52a53a54a55上三角矩阵a11a12a13a14a15a21a22a23a24a25a31a32a33a34a35a41a42a43a44a45a51a52a53a54a55对称矩阵V：a11a12a13a14a150a22a23a24a2500a33a34a35000a44a450000a55下三角矩阵11230004210130051276800201791115006114210002183k=2的带状矩阵主对角线k条对角线k条对角线在带状矩阵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】§5.2.2三元组矩阵转置对矩阵的运算有许多，如两个矩阵相加、相乘、转置……等。转置是一种简单的矩阵运算，对于一个m×n的矩阵M，它的转置矩阵N是一个n×m的矩阵，且M（i,j）＝N（j,i）。1500220－150113000000－60000000091000000028000A=6681115142216-15221123334-651916328T=这里只讨论三元组的转置算法。三元组的转置只需做到：（1）将三元组中的行列值相互交换；（2）将i、j相互调换；（3）重排三元组中的次序就可实现三元组的矩阵转置。这里关键是如何重排三元组里的次序。§5.2.2矩阵相乘两个矩阵相乘是另一种常用的矩阵运算。设：C＝A×BA=(aij)为m×s的矩阵，B=(bij)是s×n的矩阵，则矩阵A与矩阵B相乘将得到一个m×n的矩阵C=(cij)，其中cij＝ai1b1j+ai2b2j+……+aisbsj（i=1,2,…,mj=1,2,…,n）对于非压缩矩阵，算法如下：fori:=1tomdoforj:=1tondobeginC[i,j]:=0；fork:=1tosdoC[i,j]:=C[i,j]+A[i,k]*B[k,j]；end；123456Ｍ＝N＝142536【例5.2_2】6681115142216-15221123334-651916328T=6681115412261-15221132343-615913628=>6681115159122113233628412243-661-15B=当A和B是稀疏矩阵，并分别用三元组M、N存储时，应如何处理？注意1：两个稀疏矩阵相乘的积不一定是稀疏矩阵；2：即使cij＝ai1b1j+ai2b2j+……+aisbsj中的每个分项aikbkj均不为零，其累加值Cij也有可能为零。【练习】输入M、N两个三元组，分别表示A、B两个稀疏矩阵，请计算A、B的乘积C，输出C的（压缩存储）三元组Y。输入格式：（输入文件syz.in）第1行：i1j1v1(分别表示A的行数、列数、非零元素个数)第2至v1+1行：aiajav(行下标、列下标、元素的值)第v1+2行：i2j2v2(B的行数、列数、非零元素个数)第v1+3至v1+v2+2行：bibjbv输出格式：（输出文件syz.out）第1行：i3j3v3(C的行数、列数、非零元素个数)第2至v3+1行：cicjcv