C语言数据结构稀疏矩阵的压缩存储及其(1) 稀疏矩阵的压缩存储:采用三元组表示,压缩存储稀疏矩阵 (2) 求两个具有相同行列数的稀疏矩阵A和B的相加矩阵C,并输出C。 (3) 求出A的转置矩阵D,输出D。 (4) 求两

个具有相同行列数的稀疏矩阵A和B的相乘矩阵C,并输出C。

对于问题1，稀疏矩阵的压缩存储采用三元组表示，即对于一个 m 行 n 列的稀疏矩阵，只需要记录下其中非零元素的行、列、值即可。这里我们可以定义一个结构体来表示三元组：

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

对于一个稀疏矩阵，我们可以用一个 Triple 类型的数组来存储其中的所有非零元素。同时，我们还需要记录下稀疏矩阵的行数、列数和非零元素的个数，可以定义一个 SparseMatrix 类型来表示：

typedef struct {
    Triple data[MAXSIZE];   // 三元组数组
    int rows, cols, nums;   // 行数、列数、非零元素个数
} SparseMatrix;

对于问题2，我们需要先判断两个稀疏矩阵的行列数是否相同，若不同则无法相加。然后可以定义一个函数来实现稀疏矩阵的相加，具体实现可参考下面的代码：

void addSparseMatrix(SparseMatrix A, SparseMatrix B, SparseMatrix *C) {
    if (A.rows != B.rows || A.cols != B.cols) {
        printf("Error: rows and cols of A and B do not match!\n");
        return;
    }
    int i = 0, j = 0, k = 0;
    while (i < A.nums && j < B.nums) {
        if (A.data[i].row < B.data[j].row || (A.data[i].row == B.data[j].row && A.data[i].col < B.data[j].col)) {
            C->data[k++] = A.data[i++];
        } else if (A.data[i].row > B.data[j].row || (A.data[i].row == B.data[j].row && A.data[i].col > B.data[j].col)) {
            C->data[k++] = B.data[j++];
        } else {    // A.data[i].row == B.data[j].row && A.data[i].col == B.data[j].col
            int sum = A.data[i].val + B.data[j].val;
            if (sum != 0) {
                C->data[k].row = A.data[i].row;
                C->data[k].col = A.data[i].col;
                C->data[k].val = sum;
                k++;
            }
            i++;
            j++;
        }
    }
    while (i < A.nums) C->data[k++] = A.data[i++];
    while (j < B.nums) C->data[k++] = B.data[j++];
    C->rows = A.rows;
    C->cols = A.cols;
    C->nums = k;
}

对于问题3，稀疏矩阵的转置可以简单地理解为将原矩阵中的行列互换。因此，我们只需要将原矩阵中每个非零元素的行列交换即可。具体实现可参考下面的代码：

void transposeSparseMatrix(SparseMatrix A, SparseMatrix *D) {
    D->rows = A.cols;
    D->cols = A.rows;
    D->nums = A.nums;
    if (D->nums == 0) return;
    int k = 0;
    for (int col = 1; col <= A.cols; col++) {
        for (int i = 0; i < A.nums; i++) {
            if (A.data[i].col == col) {
                D->data[k].row = A.data[i].col;
                D->data[k].col = A.data[i].row;
                D->data[k].val = A.data[i].val;
                k++;
            }
        }
    }
}

对于问题4，稀疏矩阵的相乘可以参考矩阵乘法的思路，具体实现可参考下面的代码：

void multiplySparseMatrix(SparseMatrix A, SparseMatrix B, SparseMatrix *C) {
    if (A.cols != B.rows) {
        printf("Error: cols of A and rows of B do not match!\n");
        return;
    }
    SparseMatrix BT;
    transposeSparseMatrix(B, &BT);  // 先将 B 转置，方便后面的计算
    int *sums = (int*) calloc(BT.rows + 1, sizeof(int));   // 记录每行非零元素的个数
    for (int i = 0; i < BT.nums; i++) {
        sums[BT.data[i].row]++;
    }
    int *start = (int*) calloc(BT.rows + 1, sizeof(int));  // 记录每行第一个非零元素的位置
    for (int i = 1; i <= BT.rows; i++) {
        start[i] = start[i - 1] + sums[i - 1];
    }
    for (int i = 0; i < A.nums; i++) {
        int row = A.data[i].row;
        for (int j = start[row - 1]; j < start[row]; j++) {
            if (A.data[i].col == BT.data[j].row) {
                int sum = A.data[i].val * BT.data[j].val;
                int col = BT.data[j].col;
                C->data[C->nums].row = row;
                C->data[C->nums].col = col;
                C->data[C->nums].val += sum;
                C->nums++;
            }
        }
    }
    C->rows = A.rows;
    C->cols = B.cols;
    free(sums);
    free(start);
}

以上就是关于 C 语言数据结构稀疏矩阵的压缩存储及其相关操作的实现。