1111.cpp

稀疏矩阵的运算

#include<iostream>
using namespace std;
template<class T>
struct term
{
	int row,col;
	T value;	
};
template<class T>
class seqtriple
{
	public:
		seqtriple(int msize=0);
	   ~seqtriple(){delete[]trip;}
	  int gett(){return t;}
	   void add(seqtriple<T> &b,seqtriple<T> &c);
       void sub(seqtriple<T> &b,seqtriple<T> &c);
	   void mul(seqtriple<T> &B,seqtriple<T> &C);
	  void transpose(seqtriple<T> &B);
	  void input(istream &in);
	  void output(ostream &out);
	   friend istream &operator >> (istream &in,seqtriple<T>&x);
	   friend ostream &operator << (istream &out, seqtriple<T>&x);
	   private:
		   int maxsize;    //最大元素个数
		   int m,n,t;        //稀疏矩阵的行数,列数和非元素个数
		   term<T>*trip; 
};
template<class T>
seqtriple<T>::seqtriple( int msize)//构造函数
{
	m=n=t=0;
	maxsize=msize;
	trip=new term<T>[maxsize];//动态分配顺序表的储存空间
}
template<class T>
void seqtriple<T>::input(istream &in)//输入
{
 cout<<"请按顺序输入稀疏矩阵各个非零元素，以列序为主"<<endl;

             
 int k;
 cout<<"输入稀疏矩阵非0元素的个数"<<endl;
			  
 in>>k;
     t=k;         
	cout<<"请输入行数"<<endl;
	in>>m;
  cout<<"请输入列数"<<endl;
  in>>n;
	for(int a=1;a<=t;a++)
	{  
		cout<<"请输该元素所在入列数,行数和该元素的数值"<<endl;
		
 
		in>>trip[a].row;
		if(trip[a].row>=m)
		{cout<<"输入不正确,请重新输入"<<endl;
		in>>trip[a].row;}

		in>>trip[a].col;
if(trip[a].row>=m)
		{cout<<"输入不正确,请重新输入"<<endl;
		in>>trip[a].col;}
			in>>trip[a].value;
	}
}
template<class T>
void seqtriple<T>::output(ostream &out) //输出
{  cout<<"======================"<<endl;
cout<<"请按顺序输出稀疏矩阵各个非零元素，以行序为主"<<endl;
 	 cout<<"   行数       列数      数值"<<endl;
	for(int a=1;a<=t;a++)
		{
		 out<<"(     "<<trip[a].row<<"         "<<trip[a].col<<"        "<<trip[a].value<<")"<<endl;    
	}
}
template<class T>
void seqtriple<T>::transpose(seqtriple<T> &B)//转置
/*//====================================================
{
	int *num=new int[n];int *k=new int[m];
	int i;
	n=B.m;m=B.n;t=B.t;
	num[20],k[20];
	if(t>0)                                //这个有点问题........
	{
  for(i=0;i<n;i++)num[i]=0;
  for(i=0;i<t;i++)num[trip[i].col]++;
  k[0]=0;
   for(i=1;i<n;i++)k[i]=k[i-1]+num[i-1];
    for(i=0;i<t;i++)
	{
		int j=k[trip[i].col]++;
		trip[i].col=B.trip[j].row;
		trip[i].row=B.trip[j].col;
		trip[i].value=B.trip[j].value;
	}
	}
	delete[]num;delete[]k;
}
*///==================================================
{
	int change;
	int x;
	x=B.m;B.m=B.n;B.n=x;B.t=t;
	for(int i=1;i<=B.t;i++)
	{
		change=B.trip[i].row;
		B.trip[i].row=B.trip[i].col;
		B.trip[i].col=change;
	}
}
template<class T>
void seqtriple<T>::add(seqtriple<T> &b,seqtriple<T> &c)
{
	int x,j;
	x=b.t;
	//b.t=b.t+c.t;
	if(b.m==c.m&&b.n==c.n)
	{
		for(int i=1;i<=x;i++)
		for( j=1;j<=c.t;j++)
		{
        if(b.trip[i].row ==c.trip[j].row)  //行数
			{if(b.trip[i].col==c.trip[j].col)//列数
			
			{
			b.trip[i].value=b.trip[i].value+c.trip[j].value;
		    if(b.trip[i].value==0)
				b.t=b.t-1;
			 if(b.t==1)
			 {cout<<"稀疏矩阵相加后为零矩阵"<<endl;}
			 else
			 for(int r=i;r<=b.t;r++){b.trip[r]=b.trip[r+1];}
		}
	    	else	
		    if(b.trip[i].col<c.trip[j].col)
			{ b.t=b.t+c.t;
				for(int r=b.t;i<r;r--){b.trip[r]=b.trip[r+1];}
                             
			 b.trip[i+1].value=c.trip[j].value;
			 b.trip[i+1].col=c.trip[j].col;
			 b.trip[i+1].row=c.trip[j].row;
			}
		    else
			{ b.t=b.t+c.t;
				for(int r=b.t;i<r;r--){b.trip[r]=b.trip[r+1];}
             b.trip[i+1].value=b.trip[i].value;
             b.trip[i+1].col=b.trip[i].col;
			 b.trip[i+1].row=b.trip[i].row;
			 b.trip[i].value=c.trip[j].value;
			 b.trip[i].col=c.trip[j].col;
			 b.trip[i].row=c.trip[j].row; 
			}
			}
	  if(b.trip[i].row>c.trip[j].row)
	  { b.t=b.t+c.t;
			 {  for(int r=b.t;i<r;r--){b.trip[r]=b.trip[r+1];}
             b.trip[i+1].value=b.trip[i].value;
             b.trip[i+1].col=b.trip[i].col;
			 b.trip[i+1].row=b.trip[i].row;
			 b.trip[i].value=c.trip[j].value;
			 b.trip[i].col=c.trip[j].col;
			 b.trip[i].row=c.trip[j].row; 
			}
	  }
	   if(b.trip[i].row<c.trip[j].row) //else  //=======================================有点问题
		 { b.t=b.t+c.t;
         // int p=0,n=0,m;
	  int m=0;
	      for(int k=0;i<x;k++)
	    /*  if(b.trip[k].row<c.trip[j].row)p++;
	       else
		    if(b.trip[k].row==c.trip[j].row)
		      if(b.trip[k].col<=c.trip[j].col)n++;
	  
       m=p+n;
       for(int r=b.t;m+1<r;r--){b.trip[r]=b.trip[r+1];}
	         b.trip[m+2].value=c.trip[j].value;
			 b.trip[m+2].col=c.trip[j].col;
			 b.trip[m+2].row=c.trip[j].row;*/
	   
		  {if(b.trip[k].row<c.trip[j].row)
			  {m=k;}
		 if(b.trip[k].row==c.trip[j].row)
				if(b.trip[k].col<c.trip[j].col){m=k;}
		 
		  }
		for(int r=x;m+1<r;r--){b.trip[r]=b.trip[r+1];}
	     b.trip[m+2].value=c.trip[j].value;
		 b.trip[m+2].col=c.trip[j].col;
		 b.trip[m+2].row=c.trip[j].row;
	  }
	  //=================================================
	}
	}
	else
	{ cout<<"不符合要求无法进行下面的操作"<<endl;}
		

}
template<class T>
void seqtriple<T>:: sub(seqtriple<T> &b,seqtriple<T> &c)
{
int x,j;
	x=b.t;

	if(b.m==c.m&&b.n==c.n)
	{
		for(int i=1;i<=x;i++)
		for( j=1;j<=c.t;j++)
		{
        if(b.trip[i].row ==c.trip[j].row)  //行数
			if(b.trip[i].col==c.trip[j].col)//列数
			{
				b.trip[i].value=b.trip[i].value-c.trip[j].value;
				if(b.trip[i].value==0)
				b.t=b.t-1;
			 if(b.t==1)
			 {cout<<"稀疏矩阵相加后为零矩阵"<<endl;}
			 else
			 for(int r=i;r<=b.t;r++){b.trip[r]=b.trip[r+1];}
			}
	    	else	
		    if(b.trip[i].col<c.trip[j].col)
			{ 	b.t=b.t+c.t;
				for(int r=b.t;i<r;r--){b.trip[r]=b.trip[r+1];}
                             
			 b.trip[i+1].value=-c.trip[j].value;
			 b.trip[i+1].col=c.trip[j].col;
			 b.trip[i+1].row=c.trip[j].row;
			}
		   else
			{ 	b.t=b.t+c.t;
			   for(int r=b.t;i<r;r--){b.trip[r]=b.trip[r+1];}
             b.trip[i+1].value=b.trip[i].value;
             b.trip[i+1].col=b.trip[i].col;
			 b.trip[i+1].row=b.trip[i].row;
			 b.trip[i].value=-c.trip[j].value;
			 b.trip[i].col=c.trip[j].col;
			 b.trip[i].row=c.trip[j].row; 
			} 
		   if(b.trip[i].row >c.trip[j].row)
	  { 	b.t=b.t+c.t;
			 {  for(int r=b.t;i<r;r--){b.trip[r]=b.trip[r+1];}
             b.trip[i+1].value=b.trip[i].value;
             b.trip[i+1].col=b.trip[i].col;
			 b.trip[i+1].row=b.trip[i].row;
			 b.trip[i].value=-c.trip[j].value;
			 b.trip[i].col=c.trip[j].col;
			 b.trip[i].row=c.trip[j].row; 
			}
	  }
	    if(b.trip[i].row<c.trip[j].row) //else  //=======================================有点问题
		 { b.t=b.t+c.t;
          int p=0,n=0,m;
	      for(int k=0;i<x;k++)
	      if(b.trip[k].row<c.trip[j].row)p++;
	       else
		    if(b.trip[k].row==c.trip[j].row)
		      if(b.trip[k].col<=c.trip[j].col)n++;
	  
       m=p+n;
       for(int r=b.t;m+1<r;r--){b.trip[r]=b.trip[r+1];}
	         b.trip[m+2].value=c.trip[j].value;
			 b.trip[m+2].col=c.trip[j].col;
			 b.trip[m+2].row=c.trip[j].row;
	  }
	  //=================================================
		}
	}
	else
		cout<<"不符合题目要求,无法进行下一步的操作"<<endl;

}
/*template<class T>
void seqtriple<T>:: mul(seqtriple<T> &b,seqtriple<T> &c)
{int y;
if(b.m==c.n)
{for(int i=1;i<=b.t;i++)
  for(int j=1;n<=c.t;j++)
  {if(b.trip[i].row=c.trip[j].col)
		 if(b.trip[i].col=c.trip[j].row)
	 {b.trip[i].value=c.trip[j].value*b.trip[i].value;
		 y++;
     b.trip[i].col=c.trip[j].col;
	 }
  }
 if(y)cout<<"相乘后的稀疏矩阵为0矩阵"<<endl;
 else
 {b.t=y;cout<<b;}
}
else
 cout<<"不符合题目要求,无法进行下一步的操作"<<endl;
} */
template<class T>
  void seqtriple<T>::mul(seqtriple<T>&B,seqtriple<T>&C)
{	
	  if(B.n!=C.m){cout<<"此两矩阵不符合相乘规则！"<<endl;}
	  else{;
	  T E[10][10];
	  T A[10][10];
	  T D[10][10];

	  for(int a=0;a<10;a++)
		  for(int b=0;b<10;b++)
		  { E[a][b]=0;A[a][b]=0;D[a][b]=0;}

	  for(int m=0;m<B.t;m++)
		  A[B.trip[m].row][B.trip[m].col]=B.trip[m].value;
	  for(int n=0;n<C.t;n++)
		  D[C.trip[n].row][C.trip[n].col]=C.trip[n].value;
	  
	  for(int i=0;i<10;i++)
		  for(int j=0;j<10;j++)
		  {
			  E[i][j]=0;
			  for(int k=0;k<10;k++)
				  E[i][j]+=A[i][k]*D[k][j];
		  }
    cout<<"稀疏矩阵相乘后结果为："<<endl;
	for(int p=0;p<=B.m;p++)
	{   
       for(int r=0;r<=C.n;r++)
	   {
		   cout<<"   "<<E[p][r];
	   }  
	   cout<<endl;
	   }
	  }
}
template<class T>
istream &operator >>(istream &in,seqtriple<T>&x)
{
  x.input(in);	return in;
}
template<class T>
ostream &operator << (ostream &out, seqtriple<T>&x)
{
	 x.output(out);	return out;
}
const int size=20;
void main()
{ seqtriple<int> EN(size),H(size),A(size),B(size);
int x,y=1; 
 to:
cout<<"======================================="<<endl;
cout<<"1.稀疏矩阵的输入"<<endl;
cout<<"2.稀疏矩阵的输出(三元组表示)"<<endl;
cout<<"3.稀疏矩阵的转置"<<endl;
cout<<"4.两个稀疏矩阵的相加A+B"<<endl;
cout<<"5.两个稀疏矩阵的相加A-B"<<endl;
cout<<"6.两个稀疏矩阵的相乘A*B"<<endl;
cout<<"0.退出"<<endl;
cout<<"========================================"<<endl;
	cin>>x;
	if(y){
	switch(x)
	{
	case 1:cin>>EN;y=1;goto to;
		   
	case 2: cout<<EN<<endl;y=1;goto to;
	case 3:	cout<<"转置前:"<<endl;cout<<EN;EN.transpose(EN);cout<<"转置后:"<<endl;cout<<EN;y=1;goto to;
	case 4:	cout<<"请输入稀疏矩阵A,B"<<endl;cin>>A;cin>>B;A.add(A,B);cout<<"相加结果为："<<endl;cout<<A<<endl;y=1;goto to;
	case 5: cout<<"请输入稀疏矩阵A,B"<<endl;cin>>A;cin>>B;A.sub(A,B);cout<<"相减结果为："<<endl;cout<<A<<endl;y=1;goto to;
	case 6:  cout<<"请输入稀疏矩阵A,B"<<endl;cin>>A;cin>>B;A.mul(A,B);cout<<"相乘结果为："<<endl;cout<<A<<endl;y=1;goto to;
	case 0: cout<<"欢迎使用,退出"<<endl;y=0;break;
	}
	}
}