三元组.cpp

数据结构中稀疏矩阵的存储方式——三元组

/*写一个两个三元组相加（C=A+B）算法，其中C以二维数组表示*/
#include<iostream>
using namespace std;
#define MaxSize 255 /*用户自定义*/
typedef int DataType;  /*用户自定义*/
typedef struct
{
	int i,j;/*非零元素的行下标，列下标*/
	DataType d;  
 }Triple;/*定义三元组结构*/
typedef struct
{  
	Triple data[MaxSize];/*非零元三元组，data[0]未用*/
	int row_num,rank_num,not_zero;/*矩阵的行数，列数，非零元个数*/
}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的非零元个数开始为0个*/

	for(x=1;x<=A->row_num;x++)	 
	{	
		while(A->data[pa].i==x && B->data[pb].i==x) //行数相等时*
		{
			if(A->data[pa].j==B->data[pb].j) /*列数相等时*/
			{
				sum=A->data[pa].d+B->data[pb].d; /*矩阵相加*/
				if(sum) /*相加不为零时*/
				{
					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的列数大于B的列数时*/
				{
					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<<"两个三元组相加(C=A+B),C以二维数组表示"<<endl;
	cout<<endl;
	cout<<"输入三元组的行数:"<<endl;	/*输入三元组的行数*/
	cin>>A->row_num;
	cout<<"输入三元组的列数:"<<endl;
	cin>>A->rank_num; /*输入三元组的列数*/
	cout<<"输入A的非零元素个数:"<<endl;
	cin>>A->not_zero;/*输入A 的非零元*/
	cout<<"输入A:"<<endl;/*输入A的非零元三元组*/
	for(e=1;e<=A->not_zero;e++)/*循环输入A的三元组*/
		cin>>A->data[e].i>>A->data[e].j>>A->data[e].d;
	cout<<endl;
	cout<<"输入B的非零元素个数:"<<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<<"对应的三元组为："<<endl;	 
	for(b=1;b<=C->not_zero-1;b++)
	    cout<<C->data[b].i<<"  "<<C->data[b].j<<"  "<<C->data[b].d<<endl;
}