#include<iostream.h>
#include<stdio.h>
#include<iomanip.h>
#define maxsize 12500;
#define TRUE   1
#define FALSE  0
#define OK     1
#define ERROR  0

/*建立三元組 RLSM*/
typedef struct
{int i,j;
int e;
}Tri;



typedef struct
{Tri data[12500];
int rops[1000];
int mu,nu,tu;
}RLSM; 



/*稀疏矩陣的M轉(zhuǎn)置N*/


void TSM(RLSM & M,RLSM & N)
{
     int q,col,p;
     N.mu=M.nu;
     N.nu=M.mu;
     N.tu=M.tu;
    if(N.tu)
{ 
      q=1;
     for(col=1;col<=M.nu;col++)
    for(p=0;p<=M.tu;p++)
    if(M.data[p].j==col)
{ 
    N.data[q].i=M.data[p].j;
    N.data[q].j=M.data[p].i;
    N.data[q].e=M.data[p].e;
    ++q;
}
}
}




/*稀疏矩陣的顯示*/

void show(RLSM M)
{
	int i,j,tu;
   for(i=1,tu=1;i<=M.mu;i++)
   {  
	for(j=1;j<=M.nu;j++)
           if(i==M.data[tu].i&&j==M.data[tu].j)
		   {
			   cout<<setw(4)<<M.data[tu].e;
               tu++;
		   }
          else cout<<setw(4)<<0;
            cout<<endl;
   }
       cout<<endl<<"三元組表示:"<<endl;
      for(i=1;i<=M.tu;i++)
        cout<<M.data[i].i<<"  "<<M.data[i].j<<"  "<<M.data[i].e<<endl;
       cout<<"mu="<<M.mu<<'\t'<<"nu="<<M.nu<<'\t'<<"tu="<<M.tu<<endl;
}

/*稀疏矩陣中元素的刪除*/


void deleteM(RLSM &M)
{
	int i,j,tu,a,b;
	cout<<"請輸入要?jiǎng)h除的元素的行和列："<<endl;
	cin>>a>>b;
	i=1;
	for(j=1;j<=M.tu;j++)
	if(a==M.data[j].i&&b==M.data[j].j)
	{
		M.data[j].e=0;
		i=0;
		for(tu=j;tu<M.tu;tu++)
		{
			M.data[tu].i=M.data[tu+1].i;
			M.data[tu].j=M.data[tu+1].j;
			M.data[tu].e=M.data[tu+1].e;
		}
		M.tu--;
		break;
	}
	if(i)
	{
		cout<<"輸入超出范圍！請重新輸入："<<endl;
		deleteM(M);
	}
}


/*稀疏矩陣中加入元素*/

void insertM(RLSM &M)
{int s,j,tu,a,b;
	cout<<"請輸入要插入元素的值："<<endl;
	cin>>s;
	cout<<"請輸入要插入的元素的行和列："<<endl;
cin>>a>>b;
for(j=1;j<=M.tu;j++)
if(a<=M.data[j].i&&b<=M.data[j].j) break;
for(tu=M.tu+1;tu>j;tu--)
{ 
	M.data[tu].i=M.data[tu-1].i;
	M.data[tu].j=M.data[tu-1].j;
	M.data[tu].e=M.data[tu-1].e;
}
M.data[j].i=a;
M.data[j].j=b;
M.data[j].e=s;
M.tu++;
}

/*求稀疏矩陣的和Q=M+N*/
int Add(RLSM M,RLSM N,RLSM &Q)    
{
int p=1,q=1,k=1;
if(M.tu==0||N.tu==0){cout<<"-----Cannot find matrix!!";return ERROR;}

if(M.mu!=N.mu||M.nu!=N.nu){cout<<"-----Cannot calculate!!"<<endl;return ERROR;}

while(p<=M.tu&&q<=N.tu)
     {if(M.data[p].i<N.data[q].i)
	{Q.data[k].i=M.data[p].i;
	 Q.data[k].j=M.data[p].j;
	 Q.data[k].e=M.data[p].e;
	 k++;p++;}
      else if(M.data[p].i>N.data[q].i)
	     {Q.data[k].i=N.data[q].i;
	      Q.data[k].j=N.data[q].j;
	      Q.data[k].e=N.data[q].e;
	      k++;q++;}
	    else if(M.data[p].j<N.data[q].j)
		    {Q.data[k].i=M.data[p].i;
		     Q.data[k].j=M.data[p].j;
		     Q.data[k].e=M.data[p].e;
		     k++;p++;}
		  else if(M.data[p].j>N.data[q].j)
			 {Q.data[k].i=N.data[q].i;
			  Q.data[k].j=N.data[q].j;
			  Q.data[k].e=N.data[q].e;
			  k++;q++;}
			else  {if(N.data[q].e+M.data[p].e==0){p++;q++;}
			       else {Q.data[k].i=N.data[q].i;
				     Q.data[k].j=N.data[q].j;
				     Q.data[k].e=N.data[q].e+M.data[p].e;
				     k++;p++;q++;}
			}
     }
while(p<=M.tu)
     {Q.data[k].i=M.data[p].i;
      Q.data[k].j=M.data[p].j;
      Q.data[k].e=M.data[p].e;
      k++;p++;}
while(q<=N.tu)
     {Q.data[k].i=N.data[q].i;
      Q.data[k].j=N.data[q].j;
      Q.data[k].e=N.data[q].e;
      k++;q++;}
Q.mu=M.mu;Q.nu=M.nu;Q.tu=k-1;
cout<<"-----Addition succeed!!"<<endl;
return OK;
}


			  



/*主函數(shù)*/


int main()
{RLSM M,N,T;
int K;
cout<<"請輸入矩陣M的mu,nu,tu："<<endl;
cin>>M.mu>>M.nu>>M.tu;
cout<<"請輸入矩陣中的元素："<<endl;
for(K=1;K<=M.tu;K++)
{
	cin>>M.data[K].i>>M.data[K].j>>M.data[K].e;
}                                              /*先建立稀疏矩陣M*/
cout<<"矩陣："<<endl;
show(M);
deleteM(M);
cout<<"刪除元素后的矩陣："<<endl;
show(M);
insertM(M);
cout<<"插入元素后的矩陣："<<endl;
show(M);
cout<<"M的轉(zhuǎn)置矩陣："<<endl;
TSM(M,N);
show(N);
cout<<"N和M的和矩陣："<<endl;
if(Add(M,N,T))
show(T);
else cout<<"error"<<endl;
return 0;
}