问题描述：

解析：

创建一个结构体，里边包含row，col和value三个变量，表示value处在row行col列中。输入得到两个稀疏矩阵A和B。同时遍历A和B，首先比较行号，行号靠前的先加入C；其次（即行号相同时）比较列号，列号靠前的先加入C。行号列号相同，就把对应元素相加，加入C。

这样解决了：

（1）按顺序进入C表并顺序输出的过程；

（2）保证时间复杂度仅为max(m, n)，而不必两层循环；

重点：

关键在于要同时遍历A和B，保证最小的时间复杂度。

遍历思想与单链表的归并一样，都是同时遍历。

单链表的归并：(62条消息) 【数据结构】NOJ004—单链表的归并_杨的博客-CSDN博客

代码：

#include <iostream>
#include<malloc.h>
using namespace std;

typedef struct triple{
    int i,j;
    int val;
}*Triple;

typedef struct matrix{
    triple *data;
    int mu,nu,tu;
}*Matrix;

Matrix Create_Triple(int n)
{
    Matrix M;
    M=(Matrix)malloc(sizeof(matrix));
    M->data=(Triple)malloc(sizeof(triple)*n);
    M->tu=n;
    for(int i=0;i<n;i++)
        cin>>M->data[i].i>>M->data[i].j>>M->data[i].val;
    return M;
}

Matrix Add_Triple(Matrix A,Matrix B)
{
    Matrix C;
    C=(Matrix)malloc(sizeof(matrix));
    C->data=(Triple)malloc(sizeof(triple)*(A->tu+B->tu));
    int i=0,j=0;
    int k=0;
    while(i<A->tu&&j<B->tu)
    {
        if(A->data[i].i<B->data[j].i)
        {
            C->data[k].i=A->data[i].i;
            C->data[k].j=A->data[i].j;
            C->data[k].val=A->data[i].val;
            k++;
            i++;
        }
        else if(A->data[i].i>B->data[j].i)
        {
            C->data[k].i=B->data[j].i;
            C->data[k].j=B->data[j].j;
            C->data[k].val=B->data[j].val;
            k++;
            j++;
        }
        else//行号相等
        {
            if(A->data[i].j<B->data[j].j)
            {
                C->data[k].i=A->data[i].i;
                C->data[k].j=A->data[i].j;
                C->data[k].val=A->data[i].val;
                k++;
                i++;
            }
            else if(A->data[i].j>B->data[j].j)
            {
                C->data[k].i=B->data[j].i;
                C->data[k].j=B->data[j].j;
                C->data[k].val=B->data[j].val;
                k++;
                j++;
            }
            else
            {
                C->data[k].i=A->data[i].i;
                C->data[k].j=A->data[i].j;
                C->data[k].val=A->data[i].val+B->data[j].val;
                k++;
                i++;
                j++;
            }
        }
    }
    C->tu=k;
    return C;
}
int main()
{
    int t1,t2;
    cin>>t1>>t2;
    Matrix A,B,C;
    A=Create_Triple(t1);
    B=Create_Triple(t2);

    //实现加法
    C=Add_Triple(A,B);
    for(int i=0;i<C->tu;i++)
        cout<<C->data[i].i<<" "<<C->data[i].j<<" "<<C->data[i].val<<endl;
    free(A);
    free(B);
    free(C);
    return 0;
}

总结：

（1）对应于题目，要选择同时遍历两个表；

（2）掌握创建表和结构体，以及Create_Triple的方法，有返回值和无返回值，以及有无指针时的情况；