三元组稀疏矩阵的相加和转置

三元组稀疏矩阵是指矩阵中大部分元素为0，只有少部分元素非0。为了节约内存空间和降低计算成本，通常只将非零元素存储在矩阵中，采用三元组的方式。

三元组采用三个一维数组来表示，分别存储非零元素的行、列、和值，具体定义如下：

struct Triple {
    int row, col; // 行和列
    ElemType value; // 元素值
};

矩阵的相加可以按照以下方法：

STATUS MatrixAdd(TSMatrix M, TSMatrix N, TSMatrix &Q) {
    // 判断两个矩阵是否可以相加
    if (M.rows != N.rows || M.cols != N.cols)
        return ERROR;

    int m = 1, n = 1, k = 0; // 分别指向M、N、Q的当前元素
    Q.rows = M.rows;
    Q.cols = M.cols;
    Q.nums = 0; // Q中实际存储的非零元素个数

    while (m <= M.nums && n <= N.nums) {
        // 当前元素在M和N中的行和列不同时，按序号小的为当前元素
        if (M.data[m].row < N.data[n].row || 
            (M.data[m].row == N.data[n].row && M.data[m].col < N.data[n].col)) {
            Q.data[++k] = M.data[m];
            m++;
        } else if (M.data[m].row > N.data[n].row || 
                   (M.data[m].row == N.data[n].row && M.data[m].col > N.data[n].col)) {
            Q.data[++k] = N.data[n];
            n++;
        } else { // 当前元素在M和N中的行和列相同
            Q.data[++k] = M.data[m];
            Q.data[k].value += N.data[n].value; // 直接相加
            m++;
            n++;
        }
    }

    // 将M或N中剩余的元素插入Q中
    while (m <= M.nums)
        Q.data[++k] = M.data[m++];
    while (n <= N.nums)
        Q.data[++k] = N.data[n++];

    Q.nums = k; // 设置Q中实际存储的非零元素个数

    return OK;
}

矩阵的转置可以按照以下方法：

STATUS MatrixTranspose(TSMatrix M, TSMatrix &T) {
    T.rows = M.cols;
    T.cols = M.rows;
    T.nums = M.nums;

    if (T.nums == 0) // M中没有非零元素
        return OK;

    int num[M.cols + 1] = {0}; // 存储每一列的非零元素个数
    for (int k = 1; k <= M.nums; k++)
        num[M.data[k].col]++;

    int cpot[M.cols + 1] = {0}; // 存储每一列在T中的起始位置
    for (int i = 2; i <= M.cols; i++)
        cpot[i] = cpot[i - 1] + num[i - 1];

    for (int k = 1; k <= M.nums; k++) {
        int j = M.data[k].col; // 获取M中的列
        int q = cpot[j]; // 获取T中的位置
        T.data[q].row = M.data[k].col;
        T.data[q].col = M.data[k].row;
        T.data[q].value = M.data[k].value;
        cpot[j]++; // 将T中当前列的位置向后移动一位
    }

    return OK;
}