稀疏矩阵的基本运算.txt

稀疏矩阵的基本运算。

WELL...稀疏矩阵的基本运算
问题:以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两 个矩阵相加、相减、相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常 的阵列形式列出。
void TSMatrix_Add(TSMatrix A,TSMatrix B,TSMatrix &C)//三元组表示的稀疏矩阵加法
{
  C.mu=A.mu;C.nu=A.nu;C.tu=0;
  pa=1;pb=1;pc=1;
  for(x=1;x<=A.mu;x++) //对矩阵的每一行进行加法
  {
    while(A.data[pa].i<x) pa++;
    while(B.data[pb].i<x) pb++;
    while(A.data[pa].i==x&&B.data[pb].i==x)//行列值都相等的元素
    {
      if(A.data[pa].j==B.data[pb].j)
      {
        ce=A.data[pa].e+B.data[pb].e;
        if(ce) //和不为0
        {
          C.data[pc].i=x;
          C.data[pc].j=A.data[pa].j;
          C.data[pc].e=ce;
          pa++;pb++;pc++;
        }
      }//if
      else if(A.data[pa].j>B.data[pb].j) 
      {
        C.data[pc].i=x;
        C.data[pc].j=B.data[pb].j;
        C.data[pc].e=B.data[pb].e;
        pb++;pc++;
      }
      else
      {
        C.data[pc].i=x;
        C.data[pc].j=A.data[pa].j;
        C.data[pc].e=A.data[pa].e
        pa++;pc++;
      }
    }//while
    while(A.data[pa]==x) //插入A中剩余的元素(第x行)
    {
      C.data[pc].i=x;
      C.data[pc].j=A.data[pa].j;
      C.data[pc].e=A.data[pa].e
      pa++;pc++;
    }
    while(B.data[pb]==x) //插入B中剩余的元素(第x行)
    {
      C.data[pc].i=x;
      C.data[pc].j=B.data[pb].j;
      C.data[pc].e=B.data[pb].e;
      pb++;pc++;
    }
  }//for
  C.tu=pc;
}//TSMatrix_Add 

void TSMatrix_Minus(TSMatrix A,TSMatrix B,TSMatrix &C)//三元组表示的稀疏矩阵减法
{
  C.mu=A.mu;C.nu=A.nu;C.tu=0;
  pa=1;pb=1;pc=1;
  for(x=1;x<=A.mu;x++) //对矩阵的每一行进行减法
  {
    while(A.data[pa].i<x) pa++;
    while(B.data[pb].i<x) pb++;
    while(A.data[pa].i==x&&B.data[pb].i==x)//行列值都相等的元素
    {
      if(A.data[pa].j==B.data[pb].j)
      {
        ce=A.data[pa].e-B.data[pb].e;
        if(ce) //差不为0
        {
          C.data[pc].i=x;
          C.data[pc].j=A.data[pa].j;
          C.data[pc].e=ce;
          pa++;pb++;pc++;
        }
      }//if
      else if(A.data[pa].j>B.data[pb].j) 
      {
        C.data[pc].i=x;
        C.data[pc].j=B.data[pb].j;
        C.data[pc].e=-B.data[pb].e;
        pb++;pc++;
      }
      else
      {
        C.data[pc].i=x;
        C.data[pc].j=A.data[pa].j;
        C.data[pc].e=A.data[pa].e
        pa++;pc++;
      }
    }//while
    while(A.data[pa]==x) //插入A中剩余的元素(第x行)
    {
      C.data[pc].i=x;
      C.data[pc].j=A.data[pa].j;
      C.data[pc].e=A.data[pa].e
      pa++;pc++;
    }
    while(B.data[pb]==x) //插入B中剩余的元素(第x行)
    {
      C.data[pc].i=x;
      C.data[pc].j=B.data[pb].j;
      C.data[pc].e=-B.data[pb].e;
      pb++;pc++;
    }
  }//for
  C.tu=pc;
}//TSMatrix_Minus

typedef struct
{
	int i,j;
	int e;
}Triple;

typedef struct
{
	Triple data[401];
	int rpos[21];
	int mu,nu,tu;
}RLSMatrix;

void TSMatrix_Mults(RLSMatrix A,RLSMatrix B,RLSMatrix &C)//三元组表示的稀疏矩阵乘法
{
	int arow,brow,ccol,tp,p,q,t;
	int ctemp[401];
	if(A.nu!=B.mu){Error=true;return;}
	C.mu=A.mu;C.nu=B.nu;C.tu=0;
	if(A.tu*B.tu!=0)
	{
		for(arow=1;arow<=A.mu;arow++)
		{
			memset(ctemp,0,sizeof(ctemp));
			C.rpos[arow]=C.tu+1;
			if(arow<A.mu)tp=A.rpos[arow+1];
			else{tp=A.tu+1;}
			for(p=A.rpos[arow];p<tp;++p)
			{
				brow=A.data[p].j;
				if(brow<B.mu)t=A.rpos[brow+1];
				else {t=B.tu+1;}
				for(q=B.rpos[brow];q<t;++q)
				{
					ccol=B.data[q].j;
					ctemp[ccol] += A.data[p].e*B.data[q].e;
				}
			}
			for(ccol=1;ccol<B.nu;++ccol)
				if(ctemp[ccol])
				{
					if(++C.tu>400)return;
					C.data[C.tu].i=arow;
					C.data[C.tu].j=ccol;
					C.data[C.tu].e=ctemp[ccol];
				}
		}
	}

}