稀疏矩阵求转置快速方法c

稀疏矩阵的转置可以通过压缩稀疏列（CSC）或稀疏行（CSR）格式来进行。以下是基于CSC格式的转置方法：

假设有一个稀疏矩阵A，它的CSC格式表示为：

struct SparseMatrix {
    int* val;         // 非零元素数组
    int* row_idx;     // 行号数组
    int* col_ptr;     // 列指针数组
    int num_cols;     // 矩阵列数
    int num_nonzeros; // 非零元素个数
};

其中：

- `val` 数组存储所有非零元素的值；
- `row_idx` 数组存储所有非零元素所在的行号；
- `col_ptr` 数组存储每一列中第一个非零元素在 `val` 和 `row_idx` 中的下标；
- `num_cols` 存储矩阵的列数；
- `num_nonzeros` 存储非零元素的个数。

要求矩阵的转置，可以先创建一个新的稀疏矩阵B，它的CSC格式表示为：

struct SparseMatrix {
    int* val;         // 非零元素数组
    int* row_idx;     // 行号数组
    int* col_ptr;     // 列指针数组
    int num_cols;     // 矩阵列数
    int num_nonzeros; // 非零元素个数
};

其中：

- `val` 和 `row_idx` 数组的含义与原矩阵相同，存储所有非零元素的值和行号；
- `col_ptr` 数组存储每一行中第一个非零元素在 `val` 和 `row_idx` 中的下标；
- `num_cols` 存储矩阵的列数；
- `num_nonzeros` 存储非零元素的个数。

接下来，可以遍历原矩阵A的每一列，将它们转置到新矩阵B中。具体来说，可以按照以下步骤进行：

1. 初始化一个数组 `count`，用于记录每一行已经插入了多少个元素；
2. 遍历每一列 `j`，找到它在 `col_ptr` 中的位置 `start` 和 `end`；
3. 遍历该列中的所有非零元素，将它们插入到新矩阵的对应行中：
1. 获取元素的值 `v` 和行号 `i`；
2. 将元素插入到新矩阵的第 `i` 行，并且将 `count[i]` 加 1；
4. 更新新矩阵的 `col_ptr` 数组，以便下一列的元素插入。

下面是基于CSC格式的稀疏矩阵转置的代码实现：

void transpose_csc(const SparseMatrix* A, SparseMatrix* B) {
    // 初始化B的属性
    B->num_cols = A->num_cols;
    B->num_nonzeros = A->num_nonzeros;
    B->val = (int*) malloc(B->num_nonzeros * sizeof(int));
    B->row_idx = (int*) malloc(B->num_nonzeros * sizeof(int));
    B->col_ptr = (int*) malloc((B->num_cols + 1) * sizeof(int));
    int* count = (int*) calloc(B->num_cols, sizeof(int));

    // 遍历每一列
    for (int j = 0; j < A->num_cols; j++) {
        int start = A->col_ptr[j];
        int end = A->col_ptr[j+1];

        // 遍历该列中的所有非零元素
        for (int k = start; k < end; k++) {
            int v = A->val[k];
            int i = A->row_idx[k];

            // 将元素插入到新矩阵的第i行
            B->val[count[i]] = v;
            B->row_idx[count[i]] = j;
            count[i]++;
        }

        // 更新B的col_ptr数组
        B->col_ptr[j+1] = end - start + B->col_ptr[j];
    }

    free(count);
}

需要注意的是，稀疏矩阵的转置操作可能会改变原矩阵的稀疏格式。因此，在实际应用中，需要根据具体情况选择合适的格式来存储矩阵。