实现稀疏矩阵的快速转置算法5.3

稀疏矩阵的快速转置算法主要分为两种：行逐行转置和列逐列转置。其中，行逐行转置的算法复杂度较低，但是对于稀疏矩阵来说，由于矩阵中非零元素的分布不均匀，会导致算法的效率较低。因此，我们这里介绍列逐列转置的算法。

算法5.3的基本思想是，先扫描一遍原矩阵，确定每一列非零元素的个数，在转置后的矩阵中确定每一行的起始位置。然后再扫描一遍原矩阵，将每一个非零元素转置到转置后的矩阵中对应的位置。

具体实现过程如下：

1. 定义结构体Node，表示稀疏矩阵的非零元素：

typedef struct {
    int row; // 非零元素所在的行
    int col; // 非零元素所在的列
    int val; // 非零元素的值
} Node;

2. 定义转置函数transpose：

void transpose(Node *a, Node *b, int m, int n)
{
    int *num = (int*)malloc((n+1)*sizeof(int)); // num数组用于记录每一列的非零元素个数
    memset(num, 0, (n+1)*sizeof(int));
    
    for (int i = 0; i < m; i++) {
        num[a[i].col]++; // 统计每一列的非零元素个数
    }
    
    int *cpot = (int*)malloc((n+1)*sizeof(int)); // cpot数组用于记录每一行的起始位置
    cpot[0] = 0;
    for (int i = 1; i <= n; i++) {
        cpot[i] = cpot[i-1] + num[i-1];
    }
    
    for (int i = 0; i < m; i++) {
        int j = cpot[a[i].col]++;
        b[j].row = a[i].col;
        b[j].col = a[i].row;
        b[j].val = a[i].val;
    }
}

3. 在主函数中调用transpose函数：

int main()
{
    int m = 5, n = 4; // 原矩阵的大小
    Node a[6] = {{0, 0, 1}, {0, 3, 2}, {1, 1, 3}, {3, 0, 4}, {3, 2, 5}, {4, 3, 6}}; // 原矩阵的非零元素
    Node b[6]; // 转置后的矩阵
    
    transpose(a, b, 6, n);
    
    printf("转置前的矩阵：\n");
    for (int i = 0; i < 6; i++) {
        printf("(%d,%d,%d)\n", a[i].row, a[i].col, a[i].val);
    }
    
    printf("转置后的矩阵：\n");
    for (int i = 0; i < 6; i++) {
        printf("(%d,%d,%d)\n", b[i].row, b[i].col, b[i].val);
    }
    
    return 0;
}

上述代码中，我们假设原矩阵有5行4列，非零元素分别为(0,0,1)、(0,3,2)、(1,1,3)、(3,0,4)、(3,2,5)、(4,3,6)，然后调用transpose函数进行转置，最后输出转置前后的矩阵。