实现稀疏矩阵相乘C/C++

1、问题描述：已知稀疏矩阵A(m1,n1)和B(m2,n2),求乘积C(m1,n2)。

A=|3 0 0 7| B=|4 1| C=|12 17|

|0 0 0 -1| |0 0| |0 -2|

|0 2 0 0| |1 -1| |0 0|

|0 2|

A、B、C的三元组表示法分别为：

A
	i	j	v
1	1	1	2
2	1	4	7
3	2	4	-1
4	3	2	2

B
	i	j	v
1	1	1	4
2	1	2	1
3	3	1	1
4	3	2	-1
5	4	2	2

C
	i	j	v
1	1	1	12
2	1	2	17
3	2	2	-2

2、解决思路：由矩阵乘法规则可知C(i,j) = A(i,1)*B(1,j)+A(i,2)*B(2,j)+….+A(i,n)*B(n,j)，即C(i,j)为A的第i行与B的第j列非零元素乘积之和。设置累加器temp[B的列值]保存C矩阵每行的值，结束后将temp中的值赋给C矩阵。

3、定义数据结构：

3.1、稀疏矩阵中节点的定义：

//定义三元组表的节点 typedef struct{ int i,j; int v; }SPNode;

i,j为行列值，v为此位置的数值。

3.2、稀疏矩阵的定义：

//定义三元组表 typedef struct{ int mu,nu,tu; SPNode data[SMAX]; }SPMatrix;

mu为矩阵行数，nu为矩阵列数，tu为矩阵中非零元素的个数。

4、具体实现：

为了便于B.data寻找第k行第一个非零元素，在此引入num和rpot两个内容。num[k]表示矩阵B中第k行非零元素的个数；rpot[k]表示第k行的第一个非零元素在B.data中的位置。

rpot[1] = 0;

rpot[k] = rpot[k-1]+num[k-1];

矩阵B中的num与rpot的值
col	1	2	3	4
num[col]	2	0	2	0
rpot[col]	0	2	2	4

4.1、初始化。清理一些单元，准备按行顺序存放乘积矩阵。

4.2、求B的num与rpot。

4.3、做矩阵的乘法。

5、代码的具体实现：

/* *进行两个稀疏矩阵之间的乘法 */ #include 
   
     #include 
    
      #define SMAX 1024 //定义三元组表的节点 typedef struct{ int i,j; int v; }SPNode; //定义三元组表 typedef struct{ int mu,nu,tu; SPNode data[SMAX]; }SPMatrix; //进行两个稀疏矩阵之间的乘法，返回值为乘积矩阵 SPMatrix * MulSMatrix(SPMatrix *A,SPMatrix *B){ SPMatrix *C; int p,j,q,i,r,k,t; //用于结果的暂存 int temp[B->nu+1]; int num[B->mu+1],rpot[B->mu+1]; C = (SPMatrix*)malloc(sizeof(SPMatrix)); if(C==NULL){ printf("申请内存空间失败！\n"); return NULL; } //A的列值与B的行值不相等时 if(A->nu!=B->mu) return NULL; C->mu = A->mu; C->nu = B->nu; //当A或B中的非零元素为0时 if(A->tu*B->tu==0){ C->tu = 0; return C; } //计算B矩阵中每行非0元素的个数 for(i = 1;i<=B->mu;i++) num[i] = 0; for(i = 0;i 
     
       tu;i++) num[B->data[i].i]++; rpot[1] = 0; //计算B矩阵中每行首位非0元素的位置 for(i = 2;i<=B->mu;i++) rpot[i] = rpot[i-1]+num[i-1]; r = 0;//记录当前C矩阵中非0元素的个数 p = 0;//指示当前A矩阵中非零元素的位置 //进行矩阵的乘积运算 for(i = 1;i<=A->mu;i++){ //将Cij的累加器初始化 for(j = 1;j<=B->nu;j++) temp[j] = 0; //求Cij第i行的元素集合 while(i==A->data[p].i){ k = A->data[p].j;//获取A矩阵中第p个非零元素的列值 //确定B中的k行的非零元素在B.data中的下限位置 if(k 
      
        mu) t = rpot[k+1]; else t = B->tu; //将B中第k行的每一列非零元素与A中非零元素记录到累加器中 for(q = rpot[k];q 
       
         data[q].j; temp[j] += A->data[p].v*B->data[q].v; } p++; } //将第i行的结果赋值给C矩阵 for(j = 1;j<=B->nu;j++){ if(temp[j]!=0){ C->data[r] = {i,j,temp[j]}; r++; } } } C->tu = r; return C; } int main(){ SPMatrix *A,*B,*C; int i; A = (SPMatrix*)malloc(sizeof(SPMatrix)); B = (SPMatrix*)malloc(sizeof(SPMatrix)); printf("请输入A矩阵的行列值与非零元素"); scanf("%d %d %d",&A->mu,&A->nu,&A->tu); printf("请输入A矩阵的非零元素值:\n"); for(i = 0;i 
        
          tu;i++) scanf("%d %d %d",&A->data[i].i,&A->data[i].j,&A->data[i].v); printf("请输入B矩阵的行列值与非零元素"); scanf("%d %d %d",&B->mu,&B->nu,&B->tu); printf("请输入B矩阵阵的非零元素值:\n"); for(i = 0;i 
         
           tu;i++) scanf("%d %d %d",&B->data[i].i,&B->data[i].j,&B->data[i].v); C = MulSMatrix(A,B); printf("C->nu:%d,C->mu:%d,C->tu:%d\n",C->mu,C->nu,C->tu); for(i = 0;i 
          
            tu;i++) printf("i:%d,j:%d,v:%d\n",C->data[i].i,C->data[i].j,C->data[i].v); delete A,B,C; return 0; }

5、算法的时间复杂度：

5.1、求num的时间复杂度为：O(2*B->nu)

5.2、求rpot的时间复杂度为：O(B->mu)

5.3、求temp的时间复杂度为：O(A->mu*B->nu)

5.4、求C中所有元素的时间复杂度为：O(A->tu*B->tu/B->mu)

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/212747.html原文链接：https://javaforall.net

实现稀疏矩阵相乘C/C++