#define MAX_ELEMENT_NYMBER 1000
template <class T>
struct MatrixNode
{
    int row;
    int col;
    int value;
};
template <class T>
struct SpareMatrix
{
    int m;
    int n;
    int t;
    MatrixNode<T> data[MAX_ELEMENT_NYMBER];
};

// O(nt)
template <class T>
void TransMat(SpareMatrix<T> *OrigMat, SpareMatrix<T> *TransMat)
{
    TransMat->m = OrigMat->n; // 设置转置矩阵的行数
    TransMat->n = OrigMat->m; // 设置转置矩阵的列数
    TransMat->t = 0;          // 初始时转置矩阵的非零元素个数为零

    for (int col = 0; col < OrigMat->n; col++)
        for (int j = 0; j < OrigMat->t; j++)
            if (OrigMat->data[j].col == col) // 找出列号为 col 的三元组
            {
                TransMat->data[TransMat->t].col = OrigMat->data[j].row;
                TransMat->data[TransMat->t].row = OrigMat->data[j].col;
                TransMat->data[TransMat->t].value = OrigMat->data[j].value;
                TransMat->t++; // 非零元素个数增加
            }
}
// 优化版O(n+t)

template <class T>
void QuickTransMat(SpareMatrix<T> *OrigMat, SpareMatrix<T> *TransMat)
{
    int i;
    TransMat->m = OrigMat->n;
    TransMat->n = OrigMat->m;
    TransMat->t = OrigMat->t;
    if (OrigMat->t)
    {
        int *number = new int[OrigMat->n];
        memset(number, 0, OrigMat->n * sizeof(int)); // 存储每一列的非零元素个数

        for (i = 0; i < OrigMat->t; i++)
            number[OrigMat->data[i].col]++;

        int *position = new int[OrigMat->n]; // 存储每一列第一个非零元素在转置矩阵中的位置
        position[0] = 0;
        for (i = 1; i < OrigMat->n; i++)
            position[i] = position[i - 1] + number[i - 1];

        for (i = 0; i < OrigMat->t; i++)
        {
            int pos = position[OrigMat->data[i].col]++;
            TransMat->data[pos].col = OrigMat->data[i].row;
            TransMat->data[pos].row = OrigMat->data[i].col;
            TransMat->data[pos].value = OrigMat->data[i].value;
        }
        delete[] number;
        delete[] position;
    }
}