<mark>行逻辑链接的矩阵乘法（稀疏矩阵）</mark>

针对稀疏矩阵的乘法，如果按照普通矩阵的乘法进行计算时，时间复杂度必定很大，于是为了尽量降低时间复杂度同时方便运算：

可以设定一个累加器：temp[]数组，用来存放当前行中Cij的值，当前行所以元素全部算出之后，再存放到C.data中

同时参考稀疏矩阵快速转置的思想：稀疏矩阵普通转置与快速转置的链接

设置两个数组num[]与rpot[]

快速矩阵转置利用两个数组：
copt[n+1]：表示每列的第一个非零元素在三元组表的位置
num[n+1]：表示每列的非零元素的个数

其中：
copt[1]=1;
copt[i]=copt[i-1]+num[i-1] (i>=2）

于是例题如下：

输入

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

输出

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

样例输入

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

样例输出

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

代码如下：

#include<cstdio> #include<cstdlib> #include<iostream> #include<cstring> #include<iostream> using namespace std; typedef struct { int x,y,v; } Node; typedef struct { int mu,nu,tu; //mu表示行,nu表示列 Node data[12505]; //其中data[]数组元素从1开始 } Matrix; Matrix A; Matrix B; Matrix C; int temp[250]; int num[250]; int rpot[250]; void MulMatrix(Matrix A,Matrix B) { C.mu=A.mu; C.nu=B.nu; if(A.tu*B.tu==0) { C.tu=0; } else { for(int i=1; i<=B.mu; i++) num[i]=0; for(int i=1; i<=B.tu; i++) { int k=B.data[i].x; num[k]++; } rpot[1]=1; for(int i=2; i<=B.mu; i++) rpot[i]=rpot[i-1]+num[i-1]; //for(int i=1;i<=B.mu;i++) // printf("rpot[%d]=%d\n",i,rpot[i]); int r=0; int p=1; for(int i=1; i<=A.mu; i++) { for(int j=1; j<=B.nu; j++) temp[j]=0; while(A.data[p].x==i) { int k=A.data[p].y; int t; if(k<B.mu) t=rpot[k+1]-1; else t=B.tu; for(int q=rpot[k]; q<=t; q++) { int j=B.data[q].y; temp[j]=temp[j]+A.data[p].v*B.data[q].v; } p++; } for(int j=1; j<=B.nu; j++) { if(temp[j]) { r++; C.data[r].x=i; C.data[r].y=j; C.data[r].v=temp[j]; } } } C.tu=r; //cout<<"C.tu="<<C.tu<<endl; } } int main() { int r1,c1,r2,c2; int num; scanf("%d%d",&r1,&c1); A.mu=r1; A.nu=c1; int t=1; for(int i=1; i<=r1; i++) { for(int j=1; j<=c1; j++) { scanf("%d",&num); if(num!=0) { A.data[t].x=i; A.data[t].y=j; A.data[t].v=num; t++; } } } A.tu=t-1; //for(int i=1;i<=A.tu;i++) // printf("x=%d,y=%d,v=%d\n",A.data[i].x,A.data[i].y,A.data[i].v); scanf("%d%d",&r2,&c2); B.mu=r2; B.nu=c2; t=1; for(int i=1; i<=r2; i++) { for(int j=1; j<=c2; j++) { scanf("%d",&num); if(num!=0) { B.data[t].x=i; B.data[t].y=j; B.data[t].v=num; t++; } } } B.tu=t-1; //for(int i=1;i<=B.tu;i++) // printf("x=%d,y=%d,v=%d\n",B.data[i].x,B.data[i].y,B.data[i].v); t=1; MulMatrix(A,B); //for(int i=1;i<=C.tu;i++) // printf("x=%d,y=%d,v=%d\n",C.data[i].x,C.data[i].y,C.data[i].v); //cout<<"r1="<<r1<<' '<<"c2="<<c2<<endl; for(int i=1; i<=r1; i++) { for(int j=1; j<=c2; j++) { if(C.data[t].x==i&&C.data[t].y==j) { if(j==1) printf("%d",C.data[t].v); else printf(" %d",C.data[t].v); t++; } else { if(j==1) printf("0"); else printf(" 0"); } } printf("\n"); } return 0; }