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

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);													// 输出和矩阵
}