稀疏矩阵的乘法（三元组）

先用的是数组形式

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int A[1000][1000],B[1000][1000],C[1000][1000];
int main()
{
memset(A,0,sizeof(A));
memset(B,0,sizeof(B));
memset(B,0,sizeof(B));
int i,j,k;
int t1,t2,p1,p2;
int a,b,temp;
scanf("%d%d",&t1,&t2);
while(!0)
{
scanf("%d%d%d",&a,&b,&temp);
if(a==0&&b==0&&temp==0)
break;
A[a][b]=temp;
}
scanf("%d%d",&p1,&p2);
while(!0)
{
scanf("%d%d%d",&a,&b,&temp);
if(a==0&&b==0&&temp==0)
break;
B[a][b]=temp;
}
for (i=1;i<=t1;i++)
for (j=1;j<=p2;j++)
{

for(k=1;k<=p1;k++)
C[i][j]+=A[i][k]*B[k][j];
}
for(i=1;i<=t1;i++)
for(j=1;j<=p2;j++)
{
if(C[i][j]!=0)
printf("%d %d %d\n",i,j,C[i][j]);
}
return 0;

}

三元组储存形式

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 200
typedef struct
{
int i,j;
int elem;
}triple;
typedef struct
{
triple data[MAXN];
int rpos[MAXN];
int m,n,len;
}triplematrix;
void intimatrix(triplematrix *M) //取地址才能赋值啊
{
int num[MAXN];
scanf("%d%d",&(M->m),&(M->n));
int x1,x2,x3;
int ii,jj;
M->len=0;
while(!0)
{
scanf("%d%d%d",&x1,&x2,&x3);
if(x1==0&&x2==0&&x3==0)
break;
M->data[M->len].i=x1;
M->data[M->len].j=x2;
M->data[M->len].elem=x3;
M->len++;
}
if(M->len)
{ //num[i]也不是下标类，num才是0 0 1进入的原因。
for(ii=0;ii<=M->m;ii++) // 因为我没有限制超过矩阵的大小会产生错误，所以我没次多建了一行一列的矩阵
num[ii]=0;
for(jj=0;jj<M->len;jj++) //data是从0开始记的
{
num[M->data[jj].i]++; //与转置不同，这里找的是每行有几个数。
} //这步处理了三元组存矩阵，下标可能为0的情况
M->rpos[0]=0; //rpos就是统计以1或2等行数开头的相对位置的
//
for(ii=1;ii<=M->m;ii++)//ii<=M->len
{
M->rpos[ii]=M->rpos[ii-1]+num[ii-1];
}
M->rpos[ii]=M->len;//因为下面要考虑边界，使ii=A->rpos[arow]最后一个<成立,但仅仅一次成立,M->rpos[3]要保留，M->rpos[4]不保留,极其重要
}
return;
}
void multimatrix(triplematrix *A,triplematrix *B,triplematrix *C)
{
int arow,brow,ccol;
int ii,jj;
int ctemp[MAXN];
for(arow=0;arow<=A->m;arow++)
{
C->rpos[arow]=C->len; // 这步可以省略 ->column ->B->row ->B->column
for(ii=A->rpos[arow];ii<A->rpos[arow+1];ii++) //列举A中所有同行。关系图A->row->column ->B->row ->B->column ->C[row,column]
{
memset(ctemp,0,sizeof(ctemp)); // ->column ->B->row ->B->column
brow=A->data[ii].j; //A的列对应B的行。
for(jj=B->rpos[brow];jj<B->rpos[brow+1];jj++) //列举B的所有同行
{
ccol=B->data[jj].j; //rpos记录能获取相应位置的data ,data<n,arow,column<=n;
ctemp[ccol]+=A->data[ii].elem*B->data[jj].elem;
}
for(ccol=0;ccol<=C->n;ccol++)
{
if (ctemp[ccol]!=0) //
{
C->data[C->len].i=arow;
C->data[C->len].j=ccol;
C->data[C->len].elem=ctemp[ccol];
C->len++;
}
}
}
}
return;
}
void print(triplematrix *C)
{
int ii;
for(ii=0;ii<C->len;ii++)
printf("%d %d %d\n",C->data[ii].i,C->data[ii].j,C->data[ii].elem);
return;
}
int main()
{
triplematrix A,B,C;
intimatrix(&A); //按我的惯用手法
intimatrix(&B); //矩阵的data下标都是从0开始
C.m=A.m; //
C.n=B.n;
C.len=0;
if (A.m==B.n)
multimatrix(&A,&B,&C);
print(&C);
return 0;

}

外加一步排序，不用sort，我都不知怎么排

稀疏矩阵的乘法（三元组）

相关推荐