两稀疏矩阵相加，减，乘，及任一矩阵的转置，C语言

以下是两个稀疏矩阵相加、减、乘、以及任意矩阵的转置的 C 语言实现：

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

// 稀疏矩阵节点结构体
typedef struct {
    int row;    // 行号
    int col;    // 列号
    int val;    // 值
} SparseNode;

// 稀疏矩阵结构体
typedef struct {
    int rows;   // 行数
    int cols;   // 列数
    int count;  // 非零节点个数
    SparseNode *data;   // 非零节点数组
} SparseMatrix;

// 稠密矩阵结构体
typedef struct {
    int rows;   // 行数
    int cols;   // 列数
    int **data; // 二维数组
} DenseMatrix;

// 稀疏矩阵加法
SparseMatrix addSparseMatrix(SparseMatrix A, SparseMatrix B) {
    SparseMatrix C;
    C.rows = A.rows;
    C.cols = A.cols;
    C.count = 0;
    C.data = (SparseNode *) malloc(sizeof(SparseNode) * (A.count + B.count));

    int i = 0, j = 0, k = 0;
    while (i < A.count && j < B.count) {
        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 {
            int val = A.data[i].val + B.data[j].val;
            if (val != 0) {
                SparseNode node = {A.data[i].row, A.data[i].col, val};
                C.data[k++] = node;
            }
            i++;
            j++;
        }
    }
    while (i < A.count) {
        C.data[k++] = A.data[i++];
    }
    while (j < B.count) {
        C.data[k++] = B.data[j++];
    }

    C.count = k;
    C.data = (SparseNode *) realloc(C.data, sizeof(SparseNode) * k);
    return C;
}

// 稀疏矩阵减法
SparseMatrix subSparseMatrix(SparseMatrix A, SparseMatrix B) {
    SparseMatrix C;
    C.rows = A.rows;
    C.cols = A.cols;
    C.count = 0;
    C.data = (SparseNode *) malloc(sizeof(SparseNode) * (A.count + B.count));

    int i = 0, j = 0, k = 0;
    while (i < A.count && j < B.count) {
        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)) {
            SparseNode node = {B.data[j].row, B.data[j].col, -B.data[j].val};
            C.data[k++] = node;
            j++;
        } else {
            int val = A.data[i].val - B.data[j].val;
            if (val != 0) {
                SparseNode node = {A.data[i].row, A.data[i].col, val};
                C.data[k++] = node;
            }
            i++;
            j++;
        }
    }
    while (i < A.count) {
        C.data[k++] = A.data[i++];
    }
    while (j < B.count) {
        SparseNode node = {B.data[j].row, B.data[j].col, -B.data[j].val};
        C.data[k++] = node;
        j++;
    }

    C.count = k;
    C.data = (SparseNode *) realloc(C.data, sizeof(SparseNode) * k);
    return C;
}

// 稀疏矩阵乘法
SparseMatrix mulSparseMatrix(SparseMatrix A, SparseMatrix B) {
    SparseMatrix C;
    C.rows = A.rows;
    C.cols = B.cols;
    C.count = 0;
    C.data = (SparseNode *) malloc(sizeof(SparseNode) * (A.rows * B.cols));

    int *rowBegin = (int *) malloc(sizeof(int) * A.rows);
    for (int i = 0; i < A.rows; i++) {
        rowBegin[i] = -1;
    }
    for (int i = 0; i < A.count; i++) {
        int row = A.data[i].row;
        int col = A.data[i].col;
        int val = A.data[i].val;
        for (int j = rowBegin[row]; j != -1; j = C.data[j].col) {
            if (C.data[j].col == col) {
                C.data[j].val += val;
                break;
            }
        }
        SparseNode node = {row, col, val};
        node.col = rowBegin[row];
        rowBegin[row] = C.count;
        C.data[C.count++] = node;
    }
    for (int i = 0; i < C.count; i++) {
        int row = C.data[i].row;
        int col = C.data[i].col;
        int val = C.data[i].val;
        for (int j = B.data[col].row; j < B.data[col + 1].row; j++) {
            int bRow = B.data[j].row;
            int bVal = B.data[j].val;
            for (int k = C.data[row].col; k != -1; k = C.data[k].col) {
                if (C.data[k].col == bRow) {
                    C.data[k].val += val * bVal;
                    break;
                }
            }
            SparseNode node = {row, bRow, val * bVal};
            node.col = C.data[row].col;
            C.data[row].col = C.count;
            C.data[C.count++] = node;
        }
    }
    free(rowBegin);
    C.data = (SparseNode *) realloc(C.data, sizeof(SparseNode) * C.count);
    return C;
}

// 矩阵转置
DenseMatrix transpose(DenseMatrix A) {
    DenseMatrix B;
    B.rows = A.cols;
    B.cols = A.rows;
    B.data = (int **) malloc(sizeof(int *) * B.rows);
    for (int i = 0; i < B.rows; i++) {
        B.data[i] = (int *) malloc(sizeof(int) * B.cols);
        for (int j = 0; j < B.cols; j++) {
            B.data[i][j] = A.data[j][i];
        }
    }
    return B;
}

int main() {
    // 两个稀疏矩阵相加
    SparseMatrix A = {
            3,
            3,
            3,
            (SparseNode[]) {{0, 0, 1}, {1, 1, 2}, {2, 2, 3}}
    };
    SparseMatrix B = {
            3,
            3,
            3,
            (SparseNode[]) {{0, 1, 2}, {1, 2, 3}, {2, 0, 4}}
    };
    SparseMatrix C = addSparseMatrix(A, B);
    for (int i = 0; i < C.count; i++) {
        printf("(%d,%d)=%d\n", C.data[i].row, C.data[i].col, C.data[i].val);
    }
    printf("\n");

    // 两个稀疏矩阵相减
    SparseMatrix D = subSparseMatrix(A, B);
    for (int i = 0; i < D.count; i++) {
        printf("(%d,%d)=%d\n", D.data[i].row, D.data[i].col, D.data[i].val);
    }
    printf("\n");

    // 两个稀疏矩阵相乘
    SparseMatrix E = {
            3,
            3,
            3,
            (SparseNode[]) {{0, 0, 2}, {1, 1, 3}, {2, 2, 4}}
    };
    SparseMatrix F = {
            3,
            3,
            4,
            (SparseNode[]) {{0, 0, 1}, {0, 1, 2}, {1, 0, 3}, {2, 2, 4}}
    };
    SparseMatrix G = mulSparseMatrix(E, F);
    for (int i = 0; i < G.count; i++) {
        printf("(%d,%d)=%d\n", G.data[i].row, G.data[i].col, G.data[i].val);
    }
    printf("\n");

    // 稠密矩阵转置
    DenseMatrix H = {
            3,
            3,
            (int *[]) {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
    };
    DenseMatrix I = transpose(H);
    for (int i = 0; i < I.rows; i++) {
        for (int j = 0; j < I.cols; j++) {
            printf("%d ", I.data[i][j]);
        }
        printf("\n");
    }

    return 0;
}