稀疏矩阵转置

稀疏矩阵转置（Fast Transpose）

稀疏矩阵转置的快速算法使用两个辅助数组 num 和 cpot 来实现。

算法原理

1. num[col]：统计原矩阵第 col 列中非零元素的个数
2. cpot[col]：计算第 col 列第一个非零元素在新的三元组数组中的起始位置

cpot 的计算方式：

• cpot[1] = 1
• cpot[col] = cpot[col-1] + num[col-1]

算法步骤

1. 初始化目标矩阵的行、列数与非零元个数（交换原矩阵的 mu 和 nu）
2. 若无非零元则直接返回
3. 初始化 num 数组为 0
4. 遍历原三元组，统计每列非零元个数
5. 计算 cpot 数组，确定每列在新三元组中的起始位置
6. 再次遍历原三元组，对每个元素获取其列号 col，通过 cpot[col] 得到其在新三元组中的位置 q，放入后将该列的 cpot[col] 值加 1，以便下一个同列元素正确放置

代码实现

Status FastTransposeSMatrix(TSMatrix M, TSMatrix *T) {
    int num[M.nu + 1], cpot[M.nu + 1], col, p, q;
    T->mu = M.nu; T->nu = M.mu; T->tu = M.tu;  // 交换行列信息
    if (T->tu == 0) return OK;                  // 无零元则直接返回
    for (col = 1; col <= M.nu; ++col) num[col] = 0;  // 初始化 num 数组
    for (p = 1; p <= M.tu; ++p) ++num[M.data[p].j];  // 统计每列非零元个数
    cpot[1] = 1;  // 计算每列在新三元组中的起始位置
    for (col = 2; col <= M.nu; ++col)
        cpot[col] = cpot[col - 1] + num[col - 1];
    for (p = 1; p <= M.tu; ++p) {  // 将非零元放到正确位置
        col = M.data[p].j;
        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;
    }
    return OK;
}

复杂度分析

• 时间复杂度：O(col + tu)，其中 col 是原矩阵的列数，tu 是非零元素个数
• 相比普通转置算法（O(col x mu)）效率更高

链接到

• 上一个知识点：3.1 三元组稀疏矩阵
• 下一个知识点：无（本章最后一个知识点）