用三元组表示稀疏矩阵的乘法

《用三元组表示稀疏矩阵的乘法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、用三元组表实现稀疏矩阵的乘法运算两个矩阵相乘也是矩阵的一种常用的运算。设矩阵M是m1×n1矩阵，N是m2×n2矩阵；若可以相乘，则必须满足矩阵M的列数n1与矩阵N的行数m2相等，才能得到结果矩阵Q=M×N（一个m1×n2的矩阵）。数学中矩阵Q中的元素的计算方法如下：其中：1≤i≤m1,1≤j≤n2。根据数学上矩阵相乘的原理，我们可以得到矩阵相乘的经典算法：for(i=1;i<=m1;i++)for(j=1;j<=n2;j++){Q［i］［j］=0;for(k=1;k<=n1;k++)Q［i］［j］=Q［i］［j］+M［i］［k］*N［k］[j］;}图5.

2、17Q=M×N图5.17给出了一个矩阵相乘的例子。当矩阵M、N是稀疏矩阵时，我们可以采用三元组表的表示形式来实现矩阵的相乘。图5.18矩阵M、N、Q的三元组表经典算法中，不论M［i］［k］、N［k］［j］是否为零，都要进行一次乘法运算，而实际上，这是没有必要的。采用三元组表的方法来实现时，因为三元组只对矩阵的非零元素做存储所以可以采用固定三元组表a中的元素（i，k，Mik）（1≤i≤m1，1≤k≤n1），在三元组表b中找所有行号为k的的对应元素（k，j，Nkj）（1≤k≤m2，1≤j≤n2）进行相乘、累加，从而得到Q［i］［j］，即以三元组表a中的元素为基准，依次求

3、出其与三元组表b的有效乘积。算法中附设两个向量num［］、first［］，其中num［row］表示三元组表b中第row行非零元素个数（1≤row≤m2），first［row］表示三元组表b中第row行第一个非零元素所在的位置。显然，first［row+1］-1指向三元组表b中第row行最后一个非零元素的位置。first［1］=1；first［row］=first［row-1］+num［row-1］，2≤row≤m2+1。这里，first［m2+1］-1表示最后一行最后一个非零元素的存储位置。当三元组表a中第i行非零元素的列号等于三元组表b中非零元素的行号时，则元

4、素相乘并将结果累加。图5.19Q=M×N图5.20图5.19中矩阵N对应的向量num［row］,first［row］Row1234(5)Num[row]2111First[row]13456＃defineMAXSIZE1000/*非零元素的个数最多为1000*/＃defineMAXROW1000/*矩阵最大行数为1000*/typedefstruct{introw,col;/*该非零元素的行下标和列下标*/ElementTypee；/*该非零元素的值*/}Triple;typedefstruct{Tripledata［MAXSIZE+1］;/*非零

5、元素的三元组表，data［0］未用*/intfirst［MAXROW+1］;/*三元组表中各行第一个非零元素所在的位置*/intm,n,len;/*矩阵的行数、列数和非零元素的个数*/}TriSparMatrix；具体算法如下：该算法的时间主要耗费在乘法运算及累加上，其时间复杂度为O（A.len×B.n）。当A.len接近于A.m×A.n时，该算法时间复杂度接近于经典算法的时间复杂度O（A.m×A.n×B.n）。稀疏矩阵的链式存储结构:十字链表与用二维数组存储稀疏矩阵比较，用三元组表表示的稀疏矩阵不仅节约了空间，而且使得矩阵某些运算的运算时间比经典算法还少。

6、但是在进行矩阵加法、减法和乘法等运算时，有时矩阵中的非零元素的位置和个数会发生很大的变化。如A=A+B，将矩阵B加到矩阵A上，此时若还用三元组表表示法，势必会为了保持三元组表“以行序为主序”而大量移动元素。在十字链表中，矩阵的每一个非零元素用一个结点表示，该结点除了（row，col，value）以外，还要有以下两个链域：right：用于链接同一行中的下一个非零元素；down：用于链接同一列中的下一个非零元素。rowcolValueDownright图5.23十字链表的结构十字链表的结构类型说明如下：typedefstructOLNode{introw,col;

7、/*非零元素的行和列下标*/ElementTypevalue;structOLNode*right,*down;/*非零元素所在行表、列表的后继链域*/}OLNode;*OLink;typedefstruct{OLink*row_head,*col_head;/*行、列链表的头指针向量*/intm,n,len;/*稀疏矩阵的行数、列数、非零元素的个数*/}CrossList;CreateCrossList(CrossList*M){/*采用十字链表存储结构，创建稀疏矩阵M*/scanf(&m,&n,&t);/*输入M的行数,列数和非零元素的个