41.cpp

稀疏矩阵的运算

#include<iostream>
#include <vector> 
#include <iomanip>
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=0;a<t;a++)
	{  
		cout<<"请输该元素所在入列数,行数和该元素的数值"<<endl;
		in>>trip[a].row;
		while(trip[a].row>=m)
		{cout<<"输入行有误,请检查后重新输入"<<endl;
		in>>trip[a].row;}
		in>>trip[a].col;
while(trip[a].col>=n)
		{cout<<"输入列有误,请检查后重新输入"<<endl;
		in>>trip[a].col;}
in>>trip[a].value;
while(trip[a].value==0)
		{cout<<"输入值有误,请检查后重新输入"<<endl;
		in>>trip[a].value;}		
	}
}
template<class T>
void seqtriple<T>::output(ostream &out) //输出
{  cout<<"======================"<<endl;
cout<<"请按顺序输出稀疏矩阵各个非零元素，以行序为主"<<endl;
 	 cout<<"   行数       列数      数值"<<endl;
	for(int a=0;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 g;
	int x;
	x=B.m;B.m=B.n;B.n=x;B.t=t;
	for(int i=0;i<B.t;i++)
	{
		g=B.trip[i].row;
		B.trip[i].row=B.trip[i].col;
		B.trip[i].col=g;
	}
	vector<vector<int> > A(B.m, vector<int>(B.n));
    for(int l=0;l<B.m;l++)
		  for(int s=0;s<B.n;s++)
		  { A[l][s]=0;}
for(int u=0;u<B.t;u++)
		  A[B.trip[u].row][B.trip[u].col]=B.trip[u].value;
for(int h=0;h<B.t;)                  
		for(int z=0;z<B.m;z++)            
		  for(int v=0;v<B.n;v++)		   		  
	{                                   
		if(A[z][v]!=0)
		{
		  B.trip[h].row=z;
		  B.trip[h].col=v;
		  B.trip[h].value=A[z][v];
		  h++;
		}
	}
}
template<class T>
void seqtriple<T>::add(seqtriple<T> &b,seqtriple<T> &c)//相加
{
//注意下面这一行：vector<int后两个">"之间要有空格！否则会被认为是重载">>"。 
   vector<vector<int> > A(b.m, vector<int>(b.n));
   vector<vector<int> > C(c.m, vector<int>(c.n));
   if(b.m!=c.m&&b.n!=c.n){cout<<"此两个矩阵不符合相减规则！"<<endl;}
   else 
   {int p=0,y=0;
	  for(int l=0;l<b.m;l++)
		  for(int s=0;s<b.n;s++)
		  { C[l][s]=0;A[l][s]=0;}

	  for(int u=0;u<b.t;u++)
		  A[b.trip[u].row][b.trip[u].col]=b.trip[u].value;
	  for(int g=0;g<c.t;g++)
		  C[c.trip[g].row][c.trip[g].col]=c.trip[g].value;

	  for(int i=0;i<b.m;i++)
		  for(int j=0;j<b.n;j++)
		  {A[i][j]=A[i][j]+C[i][j];
		  if(A[i][j]!=0)p++;
		  }
if(p==0)cout<<"     稀疏矩阵为0矩阵"<<endl;
else
{
	      b.t=p;
//=========================================		
	   for(int h=0;h<p;)                  
		for(int z=0;z<b.m;z++)            
		  for(int v=0;v<b.n;v++)		   		  
	{                                   
		if(A[z][v]!=0)
		{
		  b.trip[h].row=z;
		  b.trip[h].col=v;
		  b.trip[h].value=A[z][v];
		  h++;
		}
	}
   cout<<b;     	
   }
}
//==========================================
}
template<class T>
void seqtriple<T>::sub(seqtriple<T> &b,seqtriple<T> &c)//相减
{	
	//注意下面这一行：vector<int后两个">"之间要有空格！否则会被认为是重载">>"。 
   vector<vector<int> > A(b.m, vector<int>(b.n));
   vector<vector<int> > C(c.m, vector<int>(c.n));
   if(b.m!=c.m&&b.n!=c.n){cout<<"此两个矩阵不符合相减规则！"<<endl;}
   else 
   {int p=0,y=0;
	  for(int l=0;l<b.m;l++)
		  for(int s=0;s<b.n;s++)
		  { C[l][s]=0;A[l][s]=0;}

	  for(int u=0;u<b.t;u++)
		  A[b.trip[u].row][b.trip[u].col]=b.trip[u].value;
	  for(int g=0;g<c.t;g++)
		  C[c.trip[g].row][c.trip[g].col]=c.trip[g].value;

	  for(int i=0;i<b.m;i++)
		  for(int j=0;j<b.n;j++)
		  {A[i][j]=A[i][j]-C[i][j];
		  if(A[i][j]!=0)p++;
		  }
if(p==0)cout<<"     稀疏矩阵为0矩阵"<<endl;
else
{
	      b.t=p;
		  
	   for(int h=0;h<p;)
		for(int z=0;z<b.m;z++)
		  for(int v=0;v<b.n;v++)
			  		  
	{  
		if(A[z][v]!=0)
		{
		  b.trip[h].row=z;
		  b.trip[h].col=v;
		  b.trip[h].value=A[z][v];
		  h++;
		}
	}
   cout<<b;     
   }
}  
}
template<class T>
void seqtriple<T>::mul(seqtriple<T> &B,seqtriple<T> &C)//相乘
{
  	
if(B.n!=C.m){cout<<"此两矩阵不符合相乘规则！"<<endl;}
else
{
  vector<vector<int> > A(B.m, vector<int>(B.n));
  vector<vector<int> > D(C.m, vector<int>(C.n));
  vector<vector<int> > E(B.m, vector<int>(C.n));
  int p=0;
for(int a=0;a<B.m;a++)
    for(int b=0;b<B.n;b++)
     {A[a][b]=0;} 
for(int d=0;d<C.m;d++)
   for(int e=0;e<C.n;e++)
    {D[d][e]=0;}
for(int f=0;f<B.m;f++)
   for(int g=0;g<C.m;g++)
    {E[f][g]=0;}
for(int x=0;x<B.t;x++)
   A[B.trip[x].row][B.trip[x].col]=B.trip[x].value;
for(int l=0;l<C.t;l++)
    D[C.trip[l].row][C.trip[l].col]=C.trip[l].value; 
for(int i=0;i<B.m;i++)
 for(int j=0;j<C.n;j++)
	{
	 E[i][j]=0;
	 for(int k=0;k<B.n;k++)
	 {
		 E[i][j]=E[i][j]+A[i][k]*D[k][j];
		 
	 }if(E[i][j]!=0)p++;
	}
if(p==0)cout<<"     稀疏矩阵为0矩阵"<<endl;
else	  
{B.t=p;
   for(int h=0;h<p;)
	for(int z=0;z<B.m;z++)
	  for(int v=0;v<C.n;v++)		  		  
	{  
		if(E[z][v]!=0)
		{
		  B.trip[h].row=z;
		  B.trip[h].col=v;
		  B.trip[h].value=E[z][v];
		  h++;
		}
	}
   cout<<B; 
	  } 
} 
}
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; 
 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;
	switch(x)
	{
	case 1:cout<<"请输入稀疏矩阵A,B"<<endl;cin>>A;cin>>B;goto to;	   
	case 2: cout<<"请输出稀疏矩阵A,B"<<endl;cout<<A<<endl;cout<<B<<endl;goto to;
	case 3:	cout<<"转置前A:"<<endl;cout<<A;A.transpose(A);cout<<"转置后A:"<<endl;cout<<A;goto to;
	case 4:	cout<<"稀疏矩阵A,B"<<endl;cout<<A<<endl;cout<<B<<endl;cout<<"相加结果为："<<endl;A.add(A,B);goto to;
	case 5: cout<<"稀疏矩阵A,B"<<endl;cout<<A<<endl;cout<<B<<endl;cout<<"相减结果为："<<endl;A.sub(A,B);goto to;
	case 6:  cout<<"稀疏矩阵A,B"<<endl;cout<<A<<endl;cout<<B<<endl;cout<<"相乘结果为："<<endl;A.mul(A,B);goto to;
	case 0: cout<<"欢迎使用,退出"<<endl;break;
	}	
}