7-2 三元组顺序表表示的稀疏矩阵加法 (10 分)

题目：7-2 三元组顺序表表示的稀疏矩阵加法（10 分）

解析：

题目给定两个三元组顺序表表示的稀疏矩阵A和B，要求计算A+B的结果，并将结果存储在新的三元组顺序表中。

三元组顺序表是将每个非零元素用一个元组表示，元组的三个分量分别表示该非零元素在矩阵中的行下标、列下标和元素值。因此，稀疏矩阵可以用三元组顺序表的形式进行存储。

对于矩阵加法，需要同时遍历A和B的三元组顺序表，按照行列下标逐个比较，将相同位置的元素相加存入新的三元组表中。如果仅在A或B中出现的元素，则直接将其插入新的三元组表中。

具体实现时，可以按照行下标升序、列下标升序的顺序遍历两个三元组顺序表，依次比较每个元素的行下标和列下标大小关系，实现如下：

typedef struct {
    int row, col;
    ElemType value;
} Triple;

typedef struct {
    Triple data[MAXSIZE];
    int mu, nu, tu; // 稀疏矩阵的行数、列数和非零元素个数
} TSMatrix;

void AddMatrix(TSMatrix A, TSMatrix B, TSMatrix &C) {
    int pa = 0, pb = 0, pc = 0; // pa、pb、pc分别为A、B、C当前扫描到的三元组的下标

    // 矩阵行数、列数、非零元素个数与A相等
    C.mu = A.mu;
    C.nu = A.nu;
    C.tu = 0;

    // 按行优先顺序遍历A、B
    while (pa < A.tu || pb < B.tu) {
        if (A.data[pa].row < B.data[pb].row ||
            (A.data[pa].row == B.data[pb].row && A.data[pa].col < B.data[pb].col)) {
            // 将A当前元素插入C中
            C.data[pc].row = A.data[pa].row;
            C.data[pc].col = A.data[pa].col;
            C.data[pc].value = A.data[pa].value;
            pa++;
        } else if (A.data[pa].row > B.data[pb].row ||
                   (A.data[pa].row == B.data[pb].row && A.data[pa].col > B.data[pb].col)) {
            // 将B当前元素插入C中
            C.data[pc].row = B.data[pb].row;
            C.data[pc].col = B.data[pb].col;
            C.data[pc].value = B.data[pb].value;
            pb++;
        } else {
            // 两元素行列下标相同，则将它们的值相加后插入C中
            C.data[pc].row = A.data[pa].row;
            C.data[pc].col = A.data[pa].col;
            C.data[pc].value = A.data[pa].value + B.data[pb].value;
            pa++;
            pb++;
        }

        // 确定新插入元素在C中的下标
        if (C.data[pc].value != 0) {
            // 如果插入元素的值为0，则不在C中插入该元素
            pc++;
            C.tu++;
        }
    }
}

时间复杂度分析：该算法需要同时遍历A、B三元组表，时间复杂度为O(t1+t2)，其中t1、t2为A、B的非零元素个数。在最坏的情况下，A、B可以同时包含所有非零元素，此时时间复杂度为O(mn)，其中m、n为矩阵的行数和列数。