JZTXT

稀疏矩阵快速转置

发布时间 2023-10-17 15:11:15作者: ww0809

如果需要将一个使用三元组形式存储的稀疏矩阵进行转置，当然可以直接交换每一个结点的行和列。但这样做的问题在于，原矩阵是按行数升序排列的，转置之后的矩阵就会变为无序的。
快速转置算法的目的就在于得到一个同样有序排列的转置后矩阵。

三元组和稀疏数组定义

#define MAXSIZE 12500

typedef int ElemType;
typedef struct {
    int i, j;
    ElemType e;
} Triple;
typedef struct {
    Triple data[MAXSIZE + 1];
    int mu, nu, tu; // 行数 列数 非零元个数
} TSMatrix;

如果我们能在进行转置之前就知道原矩阵的每一个非零元将位于新矩阵的哪个位置，就可以直接将其放在对应位置上，进而就可以得到有序的新矩阵。

需要借助两个额外的矩阵：

  1. num[]表示原矩阵每列中非零元的个数。
  2. cpot[]表示原矩阵中每一列的第一个非零元在新矩阵（也就是新矩阵每一行）中的位置。其中有如下两个公式：
    cpot[1] = 1；
    cpot[col] = cpot[col - 1] + num[col - 1]

快速转置函数代码

void FastTranspose(TSMatrix M, TSMatrix &T) {
    T.mu = M.nu, T.nu = M.mu, T.tu = M.tu;
    if(T.tu) {
        int col, num[105], cpot[105];
        memset(num, 0, sizeof(num));
        memset(cpot, 0, sizeof(cpot));
        for(int i = 1; i <= M.tu; i++) num[M.data[i].j]++; // 每列的非零元个数
        cpot[1] = 1; // 第一行第一列的元素
        for(col = 2; col <= M.nu; col++) cpot[col] = num[col - 1] + cpot[col - 1]; // 每个非零元在新数组中的位置
        for(int p = 1; p <= M.tu; p++) {
            col = M.data[p].j;
            int q = cpot[col];
            T.data[q].i = M.data[p].j;
            T.data[q].j = M.data[p].i;
            T.data[q].e = M.data[p].e;
            cpot[col]++; // 切换到原矩阵的下一个非零元
        }
    }
}

即可直接得到有序的转置后新矩阵。
*需要注意for循环中临时变量的范围，容易写错。