稀疏矩阵的乘法

#include<iostream>
using namespace std;
struct triple{
	int r;//hang
	int c;//lie
	int data;
};
struct matrix{
	triple ko[300];
	int rpos[15];//各行第一个非0原在ko中的位置
	int num[15];//各行非0元的个数
	int mu;//矩阵的行数
	int nu;//矩阵的列数
	int tu;//矩阵的非零元数
};
void mul(matrix x,matrix y,matrix &z)
{
	z.mu=x.mu;
	z.nu=y.nu;
	z.tu=0;
	int i,j,ca,p,q;
	for(i=1;i<=x.mu;i++)
	{
		int ctemp[20];
		for(j=1;j<=y.nu;j++)
			ctemp[j]=0;
		int xn;
		if(i==x.mu)
			xn=x.tu+1;
		else xn=x.rpos[i+1];
		for(j=x.rpos[i];j<xn;j++)
		{
			ca=x.ko[j].c;
			int yn;
			if(ca==y.mu)
				yn=y.tu+1;
			else yn=y.rpos[ca+1];
			for(p=ca;p<yn;p++)
				ctemp[y.ko[p].c]+=(x.ko[j].data*y.ko[p].data);
		}
		for(q=1;q<=y.nu;q++)
		{
			if(ctemp[q]!=0)
			{
				z.tu=z.tu+1;
				z.ko[z.tu].r=i;
				z.ko[z.tu].c=q;
				z.ko[z.tu].data=ctemp[q];
			}
		}
	}
}
int main()
{
	while(1)
	{
		matrix A,B,C;
		int i,j,r;
		cout<<"输入矩阵A的信息"<<endl;
		cin>>A.mu>>A.nu>>A.tu;
		for(i=0;i<=A.mu;i++)
		{
			A.num[i]=0;
			A.rpos[i]=0;
		}
		for(i=1;i<=A.tu;i++)
		{
			cin>>A.ko[i].r>>A.ko[i].c>>A.ko[i].data;
		    A.num[A.ko[i].r]+=1;
		}
		A.rpos[1]=1;
		for(i=2;i<=A.mu;i++)
			A.rpos[i]=A.rpos[i-1]+A.num[i-1];
		cout<<"输入矩阵B的信息"<<endl;
		cin>>B.mu>>B.nu>>B.tu;
		for(i=0;i<=B.mu;i++)
		{
			B.num[i]=0;
			B.rpos[i]=0;
		}
		for(i=1;i<=B.tu;i++)
		{
			cin>>B.ko[i].r>>B.ko[i].c>>B.ko[i].data;
		    B.num[B.ko[i].r]+=1;
		}
		B.rpos[1]=1;
		for(i=2;i<=B.mu;i++)
			B.rpos[i]=B.rpos[i-1]+B.num[i-1];
		mul(A,B,C);
		cout<<"输出C的所有元素"<<endl;
		for(i=1;i<=C.tu;i++)
			cout<<C.ko[i].r<<" "<<C.ko[i].c<<" "<<C.ko[i].data<<endl;
		cout<<endl;
	}
	return 0;
}

稀疏矩阵的乘法

原文：http://blog.csdn.net/killer_in_silence/article/details/19088719