#include<iostream.h>//cout,cin
#include"process.h"//exit()
#include"stdio.h"//EOF,NULL

struct MTNode												// 三元组
{ 
	int i,j;												// 行号，列号
	int e;													// 非零元
	MTNode *next;											// 指向同行下一个结点
};

typedef struct
{
	int mu,nu,tu;											// 行数、列数、非零元个数
	MTNode **rops;											// 存放各行链表的头指针
}LMatrix;

int cmp(int a,int b)										// 列号比较
{						
	if(a<b) return -1;
	else if(a=b) return 0;
	else return 1;
}

void NodeCopy(MTNode * &s,MTNode * x)						// 结点拷贝
{									
	s->e=x->e;s->i=x->i;s->j=x->j;
}

void AddNode(MTNode * &lp,MTNode * &lq,MTNode *s)			// 表尾添加结点
{
	MTNode *p;
	p=new MTNode;
	NodeCopy(p,s);
	p->next=NULL;
	if(lp==NULL)											// 首元结点
	{
		lp=p;
		lq=p;
	}
	else													// 非首元结点
	{
		 lq->next =p;
		 lq=p;
	 }
}//

 
 LMatrix MatrixAdd(LMatrix ma,LMatrix mb)					// 求矩阵和
{
	LMatrix mc;
	MTNode *pa,*pb,*pc;										// 分别指向被加数、加数、和矩阵行向量首元结点
	MTNode *s;//
	int i,sum;
	int m,n;												// 行数，列数
	int flag=1;
	m=ma.mu ;
	n=ma.nu ;
	mc.mu=m;mc.nu=n;mc.tu=0;mc.rops=NULL;
	if(mc.rops) delete [] mc.rops;
	mc.rops=new MTNode* [m];
	for(i=0;i<m;i++)
		mc.rops[i]=NULL;									// C行指针向量初始化
	for(i=0;i<m;i++)
	{
		pa=ma.rops[i];
	    pb=mb.rops[i];
		pc=mc.rops[i];
		while(pa && pb)										// 被加矩阵、加矩阵行链不空
		{
			flag=1;
			if(pa->j<pb->j)
			{
				s=new MTNode;//
				NodeCopy(s,pa);
				s->next=NULL;
				pa=pa->next;
			}
			else if(pa->j==pb->j)
			{
				sum=pa->e+pb->e;
				if(sum==0)  flag=0;
				else
				{
					s=new MTNode;
					NodeCopy(s,pa);
					s->e=sum;
					s->next=NULL;
				}
				pa=pa->next;pb=pb->next;//pa,pb后移
		    }
		    else
			{
				 s=new MTNode;
                 NodeCopy(s,pb);							// 复制pb所指结点
				 pb=pb->next;								// pb后移
				 s->next=NULL;
			 }
			if(flag)										// 有新结点生成
			{
				mc.tu++;
				AddNode(mc.rops[i],pc,s);
			}
		}//while
		if(pa)												// pa不空，复制pa剩余链到和矩阵中
		{
			while(pa)
			{
				s=new MTNode;
				NodeCopy(s,pa);pa=pa->next;
				AddNode(mc.rops [i],pc,s);
			}//while
		}//if(pa)
		if(pb)												// pb不空，复制pb剩余链到和矩阵中
		{
			while(pb)
			{
				s=new MTNode;
				NodeCopy(s,pb);pb=pb->next ;
				AddNode(mc.rops [i],pc,s);
			}//while
		}//if(pb)
	}//for
	return mc;
}//MAdd

void MDisp(LMatrix a)
{
	MTNode *p;
	int i,j,c=0;
	for(i=0;i<a.mu;i++)
	{
		p=a.rops[i];
		for(j=0;j<a.nu;j++)
		{
			if(p==NULL)
				cout<<'\t'<<c;
			else if (j<p->j)
				cout<<'\t'<<c;
			else
			{
				cout<<'\t'<<p->e;
				p=p->next;
			}
		}//for
		cout<<endl;
	}//for
}//MatrixDisp

LMatrix MCreate(int d[][3],int m,int n,int k)
{															// 由三元组的二维数组生成行向量稀疏存储矩阵
	LMatrix M={m,n,k,NULL};
	int i,r1,r2;
	MTNode *s,*p;											// 工作指针
	if(M.rops) delete [] M.rops;
	M.rops=new MTNode* [m];
	for(i=0;i<m;i++)
		M.rops[i]=NULL;
	r1=m;
	p=M.rops[r1];//
	for(i=0;i<k;i++)										// 扫描非零元数组
	{
		s=new MTNode;
		s->i=d[i][0];
		s->j=d[i][1];
		s->e=d[i][2];
		r2=s->i;											// 非零元所在行
		if(r2!=r1)											// 创建链表第1个结点
		{
			M.rops[r2]=s;
			s->next=NULL;
			p=s;
			r1=r2;
		}
		else												// 创建链表非首元结点
		{
			s->next=p->next;
			p->next =s;
			p=s;
		}
	}//for
	return M;
}//MCreate
		

void main()
{
	//MTNode *p;
	LMatrix ma,mb,mc;
	int m=4,n=6;												// 行数，列数
	int da[5][3]={{0,1,3},{1,1,2},{1,3,5},{3,0,9},{3,5,1}};
	int db[4][3]={{0,2,7},{1,1,6},{1,3,-5},{2,1,4}};
	ma=MCreate(da,4,6,5);										// 构造ma矩阵
	cout<<"ma="<<endl;
	MDisp(ma);													// 显示ma矩阵
	mb=MCreate(db,4,6,4);										// 构造mb矩阵
	cout<<"mb="<<endl;
	MDisp(mb);													// 显示mb矩阵
	mc=MatrixAdd(ma,mb);												// 求mc=ma+mb
	cout<<"mc=ma+mb="<<endl;
	MDisp(mc);													// 输出和矩阵
}