/*寫一個(gè)兩個(gè)三元組相加（C=A+B）算法，其中C以二維數(shù)組表示*/
#include<iostream>
using namespace std;
#define MaxSize 255 /*用戶自定義*/
typedef int DataType;  /*用戶自定義*/
typedef struct
{
	int i,j;/*非零元素的行下標(biāo)，列下標(biāo)*/
	DataType d;  
 }Triple;/*定義三元組結(jié)構(gòu)*/
typedef struct
{  
	Triple data[MaxSize];/*非零元三元組，data[0]未用*/
	int row_num,rank_num,not_zero;/*矩陣的行數(shù)，列數(shù)，非零元個(gè)數(shù)*/
}TSMatrix;
TSMatrix *addition(TSMatrix *A,TSMatrix *B,TSMatrix *C) /*三元組相加算法*/
{
	int x,sum,pa,pb,pc;
	pa=1;
	pb=1;
	pc=1;
	C->row_num=A->row_num;
	C->rank_num=A->rank_num;
	C->not_zero=0; /*定義矩陣C的非零元個(gè)數(shù)開始為0個(gè)*/

	for(x=1;x<=A->row_num;x++)	 
	{	
		while(A->data[pa].i==x && B->data[pb].i==x) //行數(shù)相等時(shí)*
		{
			if(A->data[pa].j==B->data[pb].j) /*列數(shù)相等時(shí)*/
			{
				sum=A->data[pa].d+B->data[pb].d; /*矩陣相加*/
				if(sum) /*相加不為零時(shí)*/
				{
					C->data[pc].i=x;
					C->data[pc].j=A->data[pa].j;
					C->data[pc].d=sum;
					pa++;
					pb++;
					pc++;
				}
			}
			else
				if(A->data[pa].j>B->data[pb].j) /*A的列數(shù)大于B的列數(shù)時(shí)*/
				{
					C->data[pc].i=x;
					C->data[pc].j=B->data[pb].j;
					C->data[pc].d=B->data[pb].d;
					pb++;
					pc++;
				}
				else
					if(A->data[pa].j<B->data[pb].j) 
				{
					C->data[pc].i=x;
					C->data[pc].j=A->data[pa].j;
					C->data[pc].d=A->data[pa].d;
					pa++;
					pc++;
				}	 
		}
		while(A->data[pa].i==x) /*插入A剩余的元素*/
		{
			C->data[pc].i=x;
			C->data[pc].j=A->data[pa].j;
			C->data[pc].d=A->data[pa].d;
			pa++;
			pc++;
		}
		while(B->data[pb].i==x) /*插入B的元素*/
		{
			C->data[pc].i=x;
			C->data[pc].j=B->data[pb].j;
			C->data[pc].d=B->data[pb].d;
			pb++;
			pc++;
		}	 
	} 
	C->not_zero=pc;		
	return C;
}
void shuchu(TSMatrix *A)
{
	int Array[100][100]={0};
	int x,y,k=1; 
	for(x=1;x<=A->row_num;x++)
	{ 
		for(y=1;y<=A->rank_num;y++)
		{
			for(k=1;k<=A->not_zero;k++)
			{
		if(x==A->data[k].i && y==A->data[k].j)
		{			
			Array[x][y]=A->data[k].d;			 		 
		}	 
			}
		}	 
	}   
	for(x=1;x<=A->row_num;x++)
	{ 
		for(y=1;y<=A->rank_num;y++)
		{
			cout<<Array[x][y]<<"  ";
		}
		cout<<endl;
	}
}
void main()
{ 
	TSMatrix *A , *B, *C; 
	int b,e,k;
	A=new TSMatrix;
    B=new TSMatrix;
	C=new TSMatrix;
	cout<<"兩個(gè)三元組相加(C=A+B),C以二維數(shù)組表示"<<endl;
	cout<<endl;
	cout<<"輸入三元組的行數(shù):"<<endl;	/*輸入三元組的行數(shù)*/
	cin>>A->row_num;
	cout<<"輸入三元組的列數(shù):"<<endl;
	cin>>A->rank_num; /*輸入三元組的列數(shù)*/
	cout<<"輸入A的非零元素個(gè)數(shù):"<<endl;
	cin>>A->not_zero;/*輸入A 的非零元*/
	cout<<"輸入A:"<<endl;/*輸入A的非零元三元組*/
	for(e=1;e<=A->not_zero;e++)/*循環(huán)輸入A的三元組*/
		cin>>A->data[e].i>>A->data[e].j>>A->data[e].d;
	cout<<endl;
	cout<<"輸入B的非零元素個(gè)數(shù):"<<endl;/*輸入B的非零元三元組*/
	cin>>B->not_zero;
	cout<<"輸入B:"<<endl;
	for(k=1;k<=B->not_zero;k++)
		cin>>B->data[k].i>>B->data[k].j>>B->data[k].d;
	cout<<endl;
	C=addition(A,B,C); /*引用相加算法*/
	cout<<"輸出C:"<<endl;/*輸出C的三元組*/ 
	shuchu(C);
    cout<<"對(duì)應(yīng)的三元組為："<<endl;	 
	for(b=1;b<=C->not_zero-1;b++)
	    cout<<C->data[b].i<<"  "<<C->data[b].j<<"  "<<C->data[b].d<<endl;
}