C语言稀疏矩阵倒置

稀疏矩阵是指矩阵中大部分元素都为0，只有少部分元素非零。稀疏矩阵倒置是指将矩阵按列优先的顺序存储方式转换为行优先的顺序存储方式。

以下是C语言实现稀疏矩阵倒置的代码：

#include <stdio.h>
#include <stdlib.h>

// 定义三元组结构体
typedef struct {
    int row; // 行号
    int col; // 列号
    int val; // 值
} Triple;

// 定义稀疏矩阵结构体
typedef struct {
    Triple *data; // 三元组数组
    int rows; // 矩阵行数
    int cols; // 矩阵列数
    int nums; // 非零元素个数
} SparseMatrix;

// 稀疏矩阵倒置函数
void transpose(SparseMatrix *m) {
    int *num = (int *)calloc(m->cols + 1, sizeof(int)); // 存储每一列非零元素个数
    int *cpot = (int *)calloc(m->cols + 1, sizeof(int)); // 存储每一列第一个非零元素的位置
    Triple *b = (Triple *)malloc(m->nums * sizeof(Triple)); // 存储转置后的三元组

    // 统计每一列非零元素个数
    for (int i = 0; i < m->nums; i++) {
        num[m->data[i].col]++;
    }

    // 计算每一列第一个非零元素的位置
    for (int i = 1; i <= m->cols; i++) {
        cpot[i] = cpot[i - 1] + num[i - 1];
    }

    // 转置
    for (int i = 0; i < m->nums; i++) {
        int col = m->data[i].col;
        int pos = cpot[col];
        b[pos].row = m->data[i].col;
        b[pos].col = m->data[i].row;
        b[pos].val = m->data[i].val;
        cpot[col]++;
    }

    // 更新稀疏矩阵
    free(m->data);
    m->data = b;
    int tmp = m->rows;
    m->rows = m->cols;
    m->cols = tmp;
}

int main() {
    SparseMatrix m = {
        .rows = 3,
        .cols = 4,
        .nums = 5,
        .data = (Triple[]){
            {0, 1, 1},
            {0, 3, 2},
            {1, 0, 3},
            {2, 1, 4},
            {2, 3, 5},
        }
    };

    // 打印原始矩阵
    printf("Original matrix:\n");
    for (int i = 0; i < m.rows; i++) {
        for (int j = 0; j < m.cols; j++) {
            int flag = 0;
            for (int k = 0; k < m.nums; k++) {
                if (m.data[k].row == i && m.data[k].col == j) {
                    printf("%-2d ", m.data[k].val);
                    flag = 1;
                    break;
                }
            }
            if (!flag) {
                printf("0  ");
            }
        }
        printf("\n");
    }

    // 矩阵倒置
    transpose(&m);

    // 打印转置后的矩阵
    printf("Transposed matrix:\n");
    for (int i = 0; i < m.rows; i++) {
        for (int j = 0; j < m.cols; j++) {
            int flag = 0;
            for (int k = 0; k < m.nums; k++) {
                if (m.data[k].row == i && m.data[k].col == j) {
                    printf("%-2d ", m.data[k].val);
                    flag = 1;
                    break;
                }
            }
            if (!flag) {
                printf("0  ");
            }
        }
        printf("\n");
    }

    return 0;
}

上面的代码中，我们用`Triple`结构体表示三元组，用`SparseMatrix`结构体表示稀疏矩阵。`transpose`函数实现矩阵倒置，具体实现过程如下：

1. 统计每一列非零元素个数，存储在`num`数组中。
2. 计算每一列第一个非零元素的位置，存储在`cpot`数组中。
3. 遍历稀疏矩阵，将每个元素转置后存储在`b`数组中。
4. 更新稀疏矩阵的行数、列数和三元组数组。

最后，我们可以用上面的代码测试稀疏矩阵倒置的功能。