C语言实现三元组稀疏矩阵的转置的两种方法

方法一：快速转置

快速转置的思路是，不用创建一个新的数组存储转置后的矩阵，而是直接在原矩阵上进行操作，将每个非零元素的行列坐标互换即可。

具体实现步骤如下：

1. 定义一个临时变量 temp 用于交换两个元素的行列坐标。

2. 遍历原矩阵的所有非零元素，将它的行列坐标互换。

3. 由于原矩阵已经被修改，所以再次遍历原矩阵时，需要按列优先的方式遍历，即先遍历第一列的所有元素，然后是第二列的所有元素，以此类推。

4. 将转置后的矩阵输出。

代码实现如下：

#include <stdio.h>
#define MaxSize 100

typedef struct {
    int i, j, e;
} Triple;

typedef struct {
    Triple data[MaxSize + 1];
    int m, n, len;
} TSMatrix;

void TransposeTSMatrix(TSMatrix M, TSMatrix *T) {
    int col, t, p;
    T->m = M.n;
    T->n = M.m;
    T->len = M.len;
    if (T->len > 0) {
        p = 1;
        for (col = 1; col <= M.n; col++) {
            for (t = 1; t <= M.len; t++) {
                if (M.data[t].j == col) {
                    T->data[p].i = M.data[t].j;
                    T->data[p].j = M.data[t].i;
                    T->data[p].e = M.data[t].e;
                    p++;
                }
            }
        }
    }
}

int main() {
    int m, n, k, i, j, e;
    TSMatrix M, T;
    printf("请输入矩阵的行数、列数和非零元素个数：\n");
    scanf("%d%d%d", &m, &n, &k);
    M.m = m;
    M.n = n;
    M.len = k;
    printf("请输入矩阵的三元组表示：\n");
    for (i = 1; i <= k; i++) {
        scanf("%d%d%d", &M.data[i].i, &M.data[i].j, &M.data[i].e);
    }
    TransposeTSMatrix(M, &T);
    printf("转置后的矩阵的三元组表示为：\n");
    for (i = 1; i <= T.len; i++) {
        printf("%d %d %d\n", T.data[i].i, T.data[i].j, T.data[i].e);
    }
    return 0;
}

方法二：行逻辑链接转置法

行逻辑链接转置法是指，首先创建一个新的数组存储转置后的矩阵，然后通过行逻辑链接的方式将原矩阵中每一列的非零元素存储到新矩阵的相应行上。

具体实现步骤如下：

1. 定义一个新的数组 B 来存储转置后的矩阵。

2. 遍历原矩阵的每一列，将每一列的非零元素存储到新矩阵的相应行上。

3. 计算每一行的非零元素个数。

4. 计算每一行的第一个非零元素在 B 数组中的位置。

5. 将转置后的矩阵输出。

代码实现如下：

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100

typedef struct {
    int i, j, e;
} Triple;

typedef struct {
    Triple data[MaxSize + 1];
    int rpos[MaxSize + 1];
    int m, n, len;
} RLSMatrix;

void TransposeRLSMatrix(RLSMatrix M, RLSMatrix *T) {
    int i, j, k, p;
    T->m = M.n;
    T->n = M.m;
    T->len = M.len;
    if (T->len > 0) {
        p = 1;
        for (i = 1; i <= M.n; i++) {
            T->rpos[i] = p;
        }
        for (i = 1; i <= M.m; i++) {
            for (k = M.rpos[i]; k < M.rpos[i + 1]; k++) {
                j = M.data[k].j;
                T->data[p].i = j;
                T->data[p].j = i;
                T->data[p].e = M.data[k].e;
                p++;
            }
        }
    }
}

int main() {
    int m, n, k, i, j, e;
    RLSMatrix M, T;
    printf("请输入矩阵的行数、列数和非零元素个数：\n");
    scanf("%d%d%d", &m, &n, &k);
    M.m = m;
    M.n = n;
    M.len = k;
    printf("请输入矩阵的三元组表示：\n");
    for (i = 1; i <= k; i++) {
        scanf("%d%d%d", &M.data[i].i, &M.data[i].j, &M.data[i].e);
    }
    M.rpos[m + 1] = k + 1;
    for (i = m; i >= 1; i--) {
        M.rpos[i] = M.rpos[i + 1];
        while (M.data[M.rpos[i] - 1].i == i) {
            M.rpos[i]--;
        }
    }
    TransposeRLSMatrix(M, &T);
    printf("转置后的矩阵的三元组表示为：\n");
    for (i = 1; i <= T.len; i++) {
        printf("%d %d %d\n", T.data[i].i, T.data[i].j, T.data[i].e);
    }
    return 0;
}