今天的数据结构课令人非常头大，本题算法其实十分容易理解，却WA了一个半小时的我始终找不出到底错在哪。最后发现似乎是Dev-C++十分“贴心”的功能特性造就的WA，这提醒我们，不要太过于信赖本地电脑的编译环境，在开发过程中，多换几个环境多换几个电脑试试，你可能就会发现你疏忽的地方。例如本题，我的疏忽在于

int count

int count 时，忘记对count 初始化，而本地环境，十分贴心地为你默认初始化为0，在本地，怎么寻找也没有找出问题，而提交oj自然就会出问题。（当然，也与学校电脑不具备调试环境有很大的关系）

忘记初始化，是一个非常常见的错误，没想到我摔过这么多次了，依旧还在出问题，务必要十分小心。

题目：

给定两个矩阵A和B，求其和矩阵C=A+B。

输入格式:

第一行包含两个数Row和Col，分别表示矩阵的行数和列数，A和B的维度是一致的。

第二行只有一个数N1，表示接下来要输入的A中的非零元素的个数。

接下来是N1行，每一行都是i j A[i,j]  这样的形式，表示的A中第i行第j列的元素A[i,j]，为了与大多数编程语言保持一致，它们都是从零开始的，也就是说下标的有效范围是[0,Row−1]×[0,Col−1]。

在N1行之后，是一个数N2，表示矩阵B中非零元素的数量，此后N2行描述B中的非零元素，它们与此前描述A中非零元素的形式一致。

矩阵元素的输入均遵循行主序。这里的所有的输入均可用int类型正确表示，可以假设输入均是合法的。

输出格式:

第一行输出和矩阵C=A+B中的绝对值大于0.1的元素个数N3，此后是N3行，按照行主序输出其中的非零元素，依次是行、列的下标和对应的元素。

输入样例：

2 2
1
1 1 1
1
0 0 1

输出样例：

2
0 0 1
1 1 1

我所用的算法思想

对于本题，我发现要按照一定的顺序进行输出，中间有些非0元素需要和0元素进行相加，涉及到插入，要便于插入，可以选用链表的数据结构。

整体上，这题和链表的归并排序算法十分相似，首先选出稍微靠前的元素为st，st的位置作为操作位置，在另外一个链表的首元素设为p2，在求和后，p2主动位移，在无求和操作时，p2的位移均通过与st不断地比较和交换完成，由于链表元素只用一次，我们将求和结果直接放在st节点中，将st结点排列为一个新的链表，得到的新链表就是加和结果。

上图为st的移动轨迹。

代码实现

#include <iostream>
#include <malloc.h>
#include <math.h>
using namespace std;
typedef struct Node{
    int i;
    int j;
    int data;
    Node* next;
}Node;
Node* GET_Info(int length)
{
    Node *p,*f,*head;
    p=(Node*)malloc(sizeof(Node));
    cin>>p->i>>p->j>>p->data;
    head=f=p;
    length--;
    while(length--)
    {
        p=(Node*)malloc(sizeof(Node));
        cin>>p->i>>p->j>>p->data;
        f->next=p;
        f=p;
    }
    p->next=NULL;
    return head;
}
Node* Sum(Node* n1,Node* n2)
{
    int count=0;//务必初始化
    Node *p3,*p2,*st,*head,*New,*New1;
    New=(Node*)malloc(sizeof(Node));
    New1=(Node*)malloc(sizeof(Node));
    head=New1;
    if(n1->i==n2->i)
    {
        if(n1->j<n2->j){st=n1;p2=n2;}
        else {st=n2;p2=n1;}
    }
    else{
        if(n1->i<n2->i){st=n1;p2=n2;}
        else {st=n2;p2=n1;}
    }//寻找开始位置
    while(st!=NULL)
    {
        if(p2!=NULL)
        if(st->i==p2->i&&st->j==p2->j)
        {st->data+=p2->data;p2=p2->next;}
        New->i=st->i;
        New->j=st->j;
        New->data=st->data;
        if(fabs(st->data)>0.1)count++;
        New1->next=New;
        New1=New;//new1为前置的指针，此处生成的list含有头结点
        New=(Node*)malloc(sizeof(Node));
        st=st->next;
        if(st==NULL&&p2!=NULL){p3=p2;p2=st;st=p3;}
        if(p2!=NULL)
        if(st->i>p2->i||((st->i==p2->i)&&(st->j>p2->j))){p3=p2;p2=st;st=p3;}//交换st和p2确保每一次操作都在st位置
    }
    head->data=count;//此处巧妙地用头结点保存了长度信息
    New1->next=NULL;
    return head;
}
void print(Node* head)
{
    Node *p=head;
    cout<<p->data<<endl;
    p=p->next;
    while(p!=NULL)
    {
     if(p->data==0){p=p->next;continue;}//细节：题目并未告知无1+ -1，0 should not print
        if(p->next==NULL)cout<<p->i<<' '<<p->j<<' '<<p->data;
        else cout<<p->i<<' '<<p->j<<' '<<p->data<<endl;
        p=p->next;
    }
    return;
}
int main()
{
    int col,row;
    cin>>row>>col;
    int Num1,Num2;
    cin>>Num1;
    Node *n1=GET_Info(Num1);
    cin>>Num2;
    Node *n2=GET_Info(Num2);//完成信息录入
    n1=Sum(n1,n2);//求和
    print(n1);//打印
    return 0;
}