矩阵.cpp

数据结构课程设计

#include<iostream.h>
#define MAXSIZE 200
#define ERROR 0
#define OK 1
typedef struct 
{
	int i,j;
	int e;
}Triple;
typedef struct
{
	Triple data[MAXSIZE+1];//非零元三元组表
	int mu,nu,tu;//矩阵的行数，列数和非零元个数
	int rpos[MAXSIZE+1];//各行第一个非零元的位置表
}TSMatrix;
/*************创建稀疏矩阵***************/
void CreateSMatrix(TSMatrix &M,int flag)
{ 
	int k;
    cout<<"请输入第";cout<<flag;cout<<"个矩阵行数m，列数n，非零元个数t"<<endl;
	cin>>M.mu>>M.nu>>M.tu;
	for(k=1;k<=M.tu;k++)
	{
	  cout<<"请输入第k个非零元所在的行mu，列nu，值e"<<endl;
	  cin>>M.data[k].i>>M.data[k].j>>M.data[k].e;
	}

}
void PrintSMatrix(TSMatrix M)
{
	int k;
	for (k=1;k<=M.tu;k++)
		cout<<" "<<M.data[k].i<<" "<<M.data[k].j<<" "<<M.data[k].e<<endl;
}
/***************矩阵相减加函数**************/						
void TSMatrix_Add(TSMatrix A,TSMatrix B,TSMatrix &C,char flag)//三元组表示的稀疏矩阵加法及减法
{ int x,ce,pa,pb,pc;
  C.mu=A.mu;C.nu=A.nu;C.tu=0;
  pa=1;pb=1;pc=1;
  if(A.mu!=B.mu||A.nu!=B.nu)
  {
	  cout<<"出错两矩阵的行或列不相同"<<endl;
	  return ;
  }
  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)
      { if(flag=='+')
        ce=A.data[pa].e+B.data[pb].e;
	    else 
        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++;
        }
		else{pa++;pb++;}
      }//if
      else if(A.data[pa].j>B.data[pb].j) 
      {
        C.data[pc].i=x;
        C.data[pc].j=B.data[pb].j;
        if(flag=='+')
        C.data[pc].e=B.data[pb].e;
        else if(flag=='-')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].i==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].i==x) //插入B中剩余的元素(第x行)
    {
      C.data[pc].i=x;
      C.data[pc].j=B.data[pb].j;
      if(flag=='+')
      C.data[pc].e=B.data[pb].e;
      else  C.data[pc].e=-B.data[pb].e;
      pb++;pc++;
    }
  }//for
  C.tu=pc-1;
}//TSMatrix_Add
/******Firstaddress（）函数实现查找每一行第一个非零元的位置表******/
void Firstaddress(TSMatrix &M)

{ 
	int num[20],col,t;
	if(M.tu)
	{
	  for(col=1;col<=M.mu;++col)num[col]=0;
	  for(t=1;t<=M.tu;t++) ++num[M.data[t].i];
      M.rpos[1]=1;
	  for(col=2;col<=M.mu;++col)M.rpos[col]=M.rpos[col-1]+num[col-1];
	}
}
/**************MultSMatrix（）函数实现矩阵相乘***********************/
int MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)
{   int arow,ctemp[20],i,tp,p,brow,t,q,ccol;
	if(M.nu!=N.mu)return ERROR;
	Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;
	if(M.tu*N.tu!=0){
		for(arow=1;arow<=M.mu;++arow)
		{   for(i=0;i<=10;i++)
			ctemp[i]=0;
			Q.rpos[arow]=Q.tu+1;
			if(arow<M.mu)tp=M.rpos[arow+1];
			else{tp=M.tu+1;}
			for(p=M.rpos[arow];p<tp;++p){
				brow=M.data[p].j;
				if(brow<N.mu)t=N.rpos[brow+1];
				else {t=N.tu+1;}
				for(q=N.rpos[brow];q<t;++q){
					ccol=N.data[q].j;
					ctemp[ccol]+=M.data[p].e*N.data[q].e;
				}
			}
			for(ccol=1;ccol<=Q.nu;++ccol)
				if(ctemp[ccol]){
					if(++Q.tu>MAXSIZE)return ERROR;
					Q.data[Q.tu].i=arow;
					Q.data[Q.tu].j=ccol;
					Q.data[Q.tu].e=ctemp[ccol];
				}
		}
	}return OK;
}
/***********主函数***************/
void main()
{  
	TSMatrix A,B,C;
	char flag=1,math;
    CreateSMatrix(A,1);
	CreateSMatrix(B,2);
	cout<<"两矩阵相加:+,相减:-,相乘:*"<<endl;
	for(;flag;)
	{
	   cin>>math;
	   if(math!='+'&&math!='-'&&math!='*')
	   { cout<<"输入错误,请重新输入"<<endl;
	     cout<<"两矩阵相加:+,相减:-,相乘:*"<<endl;
         flag=1;
	   }
	   else flag=0;
	}
	switch(math)
	{

     	case '+':
			{
              TSMatrix_Add( A, B,C,math);
              PrintSMatrix(C);
		      break;
			}
		case '-':
			{
              TSMatrix_Add( A, B,C,math);
              PrintSMatrix(C);
		      break;
			}
	case '*':
			{ 
			  Firstaddress(A);
              Firstaddress(B); 
              MultSMatrix(A, B,C);
              PrintSMatrix(C);
		      break;
			}
	default:
		break;
	}
}