行逻辑链接的矩阵乘法（稀疏矩阵）

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

可以设定一个累加器：

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, r1

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

之后的一行有两个整数r2和c2（c1=r2<200, c2<200, r2

c2 <= 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;
}