行逻辑链接的矩阵乘法

Description

对于一个稀疏矩阵，当需要频繁的随机存取任意一行的非零元时，则需要知道每一行的第一个非零元在三元组表中的位置。为此，可以将算法5.2中用来指示“行”信息的辅助数组cpot固定在稀疏矩阵的存储结构中。这种“带行链接信息”的三元组表即为行逻辑链接的顺序表。其类型描述如下：

针对存储于行逻辑链接顺序表的稀疏矩阵，其矩阵相乘的算法与经典算法有所不同。因此，对于两个稀疏矩阵相乘(Q=M×N)的过程可以大致描述如下：

请使用行逻辑链接的顺序表实现两个稀疏矩阵的乘法。

Input

输入的第一行是两个整数r1和c1（r1<200, c1<200, r1*c1 <= 12500），分别表示一个包含很多0的稀疏矩阵的行数和列数。接下来有r1行，每行有c1个整数，用空格隔开，表示第一个稀疏矩阵的各个元素。

之后的一行有两个整数r2和c2（c1=r2<200, c2<200, r2*c2 <= 12500），分别表示一个包含很多0的稀疏矩阵的行数和列数。接下来有r2行，每行有c2个整数，用空格隔开，表示第二个稀疏矩阵的各个元素。

Output

输出两个矩阵的乘积。输出共有r1行，每行有c2个整数，每个整数后输出一个空格。请注意行尾输出换行。

Sample Input

4 5
0 0 0 69 78
0 0 5 0 0
0 0 0 0 0
0 91 2 0 82
5 6
0 18 0 0 0 0
0 0 67 0 0 0
0 0 0 0 0 41
0 0 47 62 0 0
0 0 0 0 0 35

Sample Output

0 0 3243 4278 0 2730 
0 0 0 0 0 205 
0 0 0 0 0 0 
0 0 6097 0 0 2952

HINT

提示：

对于稀疏矩阵M和N，其相乘的基本操作是：对于M中每个元素M.data[p](p=1,2,...,M.tu)，找到N中所有满足条件M.data[p].j=N.data[q].i的元素N.data[q]，从而求得M.data[p]与M.data[q]的乘积。需要注意的是，这个乘积只是Q[i][j]中的一部分，需要将其累加从而得到最终的结果。

另外需要注意的是，两个稀疏矩阵相乘的乘积并不一定是稀疏矩阵。

总结：

采用行逻辑链接的顺序表通过使用非零元的行信息，使稀疏矩阵的存储和使用效能进一步提高。尤其是对于稀疏矩阵相乘, 这种算法省去了非常多无谓的计算。

  1 #include <stdio.h>  
  2 #include <string.h>  
  3 #include <iostream>  
  4 #include <string>  
  5 #include <math.h>  
  6 #include <algorithm>  
  7 #include <vector>  
  8 #include <stack>  
  9 #include <queue>  
 10 #include <set>  
 11 #include <map>
 12 const int INF=0x3f3f3f3f;  
 13 typedef long long LL;
 14 const int mod=1e9+7;
 15 const int maxn=1e4+2510;  
 16 using namespace std;  
 17   
 18 typedef struct  
 19 {  
 20     int row;//行
 21     int col;//列
 22     int val;//值
 23 }Triple;  
 24   
 25 typedef struct  
 26 {  
 27     Triple data[maxn];//三元组
 28     int rpos[maxn];//每一行的第一个非零元在三元组表中的位置
 29     int rows;//矩阵的总行数
 30     int cols;//矩阵的总列数
 31     int nums;//矩阵的非零元素个数
 32 }Matrix;
 33 
 34 void MulMatrix(Matrix A,Matrix B,Matrix *C)
 35 {
 36     if(A.cols!=B.rows)//如果矩阵A的列数与矩阵B的行数不等，则不能做矩阵乘运算
 37         return ;
 38     C->rows=A.rows;
 39     C->cols=B.cols;
 40     C->nums=0;
 41     if(A.nums*B.nums==0)//如果其中任意矩阵的元素个数为零，做乘法元素没有意义，全是0
 42         return ;
 43     int ccol;
 44     for(int arow=1;arow<=A.rows;arow++)
 45     {
 46         int temp[maxn]={0};//创建一个临时存储乘积结果的数组，且初始化为0，遍历每次都需要清空
 47         C->rpos[arow]=C->nums+1;
 48         int tp;
 49         if(arow<A.rows)
 50             tp=A.rpos[arow+1];//获取矩阵A的下一行第一个非零元素在data数组中位置
 51         else
 52             tp=A.nums+1;//若当前行是最后一行，则取最后一个元素+1
 53         //遍历当前行的所有的非0元素
 54         for(int p=A.rpos[arow];p<tp;p++)
 55         {
 56             int brow=A.data[p].col;//取该非0元素的列数，便于去B中找对应的做乘积的非0元素
 57             int t;
 58             // 判断如果对于A中非0元素，找到矩阵B中做乘法的那一行中的所有的非0元素
 59             if(brow<B.rows)
 60                 t=B.rpos[brow+1];
 61             else
 62                 t=B.nums+1;
 63             //遍历找到的对应的非0元素，开始做乘积运算
 64             for(int q=B.rpos[brow];q<t;q++)
 65             {
 66                 //得到的乘积结果，每次和temp数组中相应位置的数值做加和运算
 67                 ccol=B.data[q].col;
 68                 temp[ccol]+=A.data[p].val*B.data[q].val;
 69             }
 70         }
 71         //矩阵C的行数等于矩阵A的行数，列数等于矩阵B的列数，所以，得到的temp存储的结果，也会在C的列数的范围内
 72         for(ccol=1;ccol<=C->cols;ccol++)
 73         {
 74             //由于结果可以是0，而0不需要存储，所以在这里需要判断
 75             if(temp[ccol])
 76             {
 77                 C->nums++;
 78                 if(C->nums > maxn)
 79                     return;
 80                 C->data[C->nums].val=temp[ccol];
 81                 C->data[C->nums].row=arow;
 82                 C->data[C->nums].col=ccol;
 83             }
 84         }
 85     }
 86 }
 87 
 88 int main()  
 89 {
 90     Matrix A,B,C;
 91     scanf("%d %d",&A.rows,&A.cols);
 92     A.nums=0;
 93     for(int i=1;i<=A.rows;i++)
 94     {
 95         A.rpos[i]=A.nums+1;
 96         for(int j=1;j<=A.cols;j++)
 97         {
 98             int x;
 99             scanf("%d",&x);
100             if(x)
101             {
102                 A.nums++;  
103                 A.data[A.nums].row=i;
104                 A.data[A.nums].col=j;
105                 A.data[A.nums].val=x;
106             }
107         }
108     }
109     scanf("%d %d",&B.rows,&B.cols);  
110     B.nums=0;
111     for(int i=1;i<=B.rows;i++)  
112     { 
113         B.rpos[i]=B.nums+1;
114         for(int j=1;j<=B.cols;j++)  
115         {  
116             int x;  
117             scanf("%d",&x);  
118             if(x)  
119             {  
120                 B.nums++;  
121                 B.data[B.nums].row=i;  
122                 B.data[B.nums].col=j;  
123                 B.data[B.nums].val=x;  
124             }
125         }
126     }
127     MulMatrix(A,B,&C); 
128     int cnt=1; 
129     for(int i=1;i<=C.rows;i++)//输出转置后的矩阵   
130     {
131         for(int j=1;j<=C.cols;j++)
132         {
133             int a,b;
134             a=C.data[cnt].row;
135             b=C.data[cnt].col;
136             if(a==i&&b==j)
137             {
138                 printf("%d ",C.data[cnt].val);
139                 cnt++;
140             }
141             else
142                 printf("%d ",0);
143         }
144         printf("
");
145     }
146     return 0;
147 }