设计算法并编程实现用三元组顺序表解决稀疏矩阵的转置问题，用2种方法实现并分析比较2种算法的时间和空间复杂性。

算法1：直接遍历原矩阵，将每个非零元素插入到转置矩阵对应位置。
时间复杂度：O(nz)，其中 n 为矩阵行数，z 为矩阵中非零元素个数。
空间复杂度：O(nz)

#include <iostream>
using namespace std;

const int MAX_SIZE = 100;
const int MAX_Z = 100;

typedef struct {
    int row, col;
    int val;
} Triple;

typedef struct {
    Triple data[MAX_Z + 1];
    int rows, cols, nums;
} TSMatrix;

void transpose(TSMatrix A, TSMatrix &B) {
    B.rows = A.cols;
    B.cols = A.rows;
    B.nums = A.nums;
    if (B.nums == 0) return;
    int q = 1;
    for (int col = 1; col <= A.cols; col++) {
        for (int p = 1; p <= A.nums; p++) {
            if (A.data[p].col == col) {
                B.data[q].row = A.data[p].col;
                B.data[q].col = A.data[p].row;
                B.data[q].val = A.data[p].val;
                q++;
            }
        }
    }
}

int main() {
    TSMatrix A = {
        {
            {1, 2, 3},
            {1, 3, 5},
            {2, 1, 2},
            {2, 4, 6},
            {3, 2, 7}
        },
        3, 4, 5
    };
    TSMatrix B;
    transpose(A, B);
    for (int i = 1; i <= B.nums; i++) {
        cout << B.data[i].row << " " << B.data[i].col << " " << B.data[i].val << endl;
    }
    return 0;
}

算法2：按列优先顺序遍历原矩阵，将每一列非零元素插入到转置矩阵对应位置。
时间复杂度：O(nz)，其中 n 为矩阵行数，z 为矩阵中非零元素个数。
空间复杂度：O(nz)

#include <iostream>
using namespace std;

const int MAX_SIZE = 100;
const int MAX_Z = 100;

typedef struct {
    int row, col;
    int val;
} Triple;

typedef struct {
    Triple data[MAX_Z + 1];
    int rows, cols, nums;
} TSMatrix;

void fastTranspose(TSMatrix A, TSMatrix &B) {
    B.rows = A.cols;
    B.cols = A.rows;
    B.nums = A.nums;
    if (B.nums == 0) return;
    int num[MAX_SIZE + 1] = {0};
    for (int p = 1; p <= A.nums; p++) {
        num[A.data[p].col]++;
    }
    int cpot[MAX_SIZE + 1] = {0};
    cpot[1] = 1;
    for (int col = 2; col <= A.cols; col++) {
        cpot[col] = cpot[col-1] + num[col-1];
    }
    for (int p = 1; p <= A.nums; p++) {
        int col = A.data[p].col;
        int q = cpot[col];
        B.data[q].row = A.data[p].col;
        B.data[q].col = A.data[p].row;
        B.data[q].val = A.data[p].val;
        cpot[col]++;
    }
}

int main() {
    TSMatrix A = {
        {
            {1, 2, 3},
            {1, 3, 5},
            {2, 1, 2},
            {2, 4, 6},
            {3, 2, 7}
        },
        3, 4, 5
    };
    TSMatrix B;
    fastTranspose(A, B);
    for (int i = 1; i <= B.nums; i++) {
        cout << B.data[i].row << " " << B.data[i].col << " " << B.data[i].val << endl;
    }
    return 0;
}

两种算法的时间复杂度都为 O(nz)，其中 n 为矩阵行数，z 为矩阵中非零元素个数。但是算法2相对于算法1来说，空间复杂度更低，因为算法2只需要一个一维数组。因此，如果内存空间受限，则算法2更为适用。