Description

以十字链表为存储结构，编写程序，将稀疏矩阵B加到稀疏矩阵A上。

Input

第一行输入四个正整数，分别为稀疏矩阵A和稀疏矩阵B的行数m、列数n、稀疏矩阵A的非零元素个数t1和稀疏矩阵B的非零元素个数t2。接下来的t1+t2行三元组表示，其中第一个元素表示非零元素所在的行值，第二个元素表示非零元素所在的列值，第三个元素表示非零元素的值。

Output

输出相加后的矩阵三元组。

• Sample Input 

  3 4 3 2
  1 1 1
  1 3 1
  2 2 2
  1 2 1
  2 2 3

• Sample Output

  1 1 1
  1 2 1
  1 3 1
  2 2 5

#include<stdio.h>
#include<stdlib.h>

typedef struct list
{
	int row, col, num;
	struct list *down, *next;
}list;

typedef struct crosslist
{
	int mu, nu, tu;//记录行列数以及元素个数
	list *headr[100],*headc[100];//行列的头指针用两个指针数组来表示
}cs;

void init(cs* a)
{
	int m, n,t1;//输入行列数，以及每个矩阵的非零元素数
	scanf("%d%d%d",&m,&n,&t1);
	a->mu = m;
	a->nu = n;
	a->tu  = t1;
	for(int i = 1;i <= m;i++)
	{
		a->headr[i] = NULL;
	}
	for(int i = 1;i <= n;i++)
	{
		a->headc[i] = NULL;
	}
}

void creat(cs *a)
{
	int i, m, n, k, t2;
	scanf("%d",&t2);
	list* q;
	for(i = 1;i <= a->tu;i++)
	{
		list* p = (list* )malloc(sizeof(list));
		scanf("%d%d%d",&m,&n,&k);
		p->row = m;
		p->col =n;
		p->num = k;
		if(a->headr[m] == NULL||a->headr[m]->col > n)//插入到头节点之后
		{
			p->next = a->headr[m];
			a->headr[m] = p;
		}
		else
		{
			for(q = a->headr[m];(q->next)&&q->next->col < n;q = q->next);//很神奇
			p->next = q->next;
			q->next = p;
		}//完成行插入
		if(a->headc[n] == NULL || a->headc[n]->row > m)
		{
			p->down = a->headc[n];
			a->headc[n] = p;
		}
		else
		{
			for(q = a->headc[n];(q->down)&&q->down->col < n;q = q->down);
			p->down = q->down;
			q->down = p;
		}
	}
	int flag = 0;
	for(i = 0;i < t2;i++)
	{
		scanf("%d%d%d",&m,&n,&k);
		for(q = a->headr[m];q;q = q->next)
		{
			if(q->col == n)
			{
				q->num = k + q->num;
				flag = 1;
				break;
			}
		}
		if(flag == 0)
		{
			list *p = (list* )malloc(sizeof(list));
			p->row = m;p->col = n;p->num = k;
			if(a->headr[m] == NULL||a->headr[m]->col > n)//插入到头节点之后
			{
				p->next = a->headr[m];
				a->headr[m] = p;
			}
			else
			{
				for(q = a->headr[m];(q->next)&&q->next->col < n;q = q->next);
				p->next = q->next;
				q->next = p;
			}
		}
		flag = 0;
	}
}

void getout(cs* a)
{
	list* p;
	int i;
	for(i = 1;i <= a->mu;i++)
	{
		if(a->headr[i] == NULL)
		{
			continue;
		}
		else
		{
			p = a->headr[i];
			while(p)
			{
				if(p->num == 0)
				{
					p = p->next//注意会陷入死循环;
					continue;
				}
				printf("%d %d %d\n",p->row,p->col,p->num);
				p = p->next;
			}
		}
	}
}

int main()
{
	cs *a;
	a = (cs* )malloc(sizeof(cs));
	init(a);
	creat(a);
	getout(a);
	return 0;
}