两个稀疏矩阵的乘积C语言实现

两个稀疏矩阵的乘积可以通过稀疏矩阵的压缩存储方式来实现。以下是C语言实现的代码：

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

// 稀疏矩阵的压缩存储结构体
typedef struct {
    int row;  // 行数
    int col;  // 列数
    int num;  // 非零元素个数
    int *rpos;  // 每行第一个非零元素在value中的位置
    int *cidx;  // 非零元素所在的列
    double *value; // 非零元素的值
} SparseMatrix;

// 构建稀疏矩阵
SparseMatrix *createSparseMatrix(int row, int col, int num) {
    SparseMatrix *matrix = (SparseMatrix *)malloc(sizeof(SparseMatrix));
    matrix->row = row;
    matrix->col = col;
    matrix->num = num;
    matrix->rpos = (int *)malloc(sizeof(int) * (row + 1));
    matrix->cidx = (int *)malloc(sizeof(int) * num);
    matrix->value = (double *)malloc(sizeof(double) * num);
    return matrix;
}

// 释放稀疏矩阵
void freeSparseMatrix(SparseMatrix *matrix) {
    free(matrix->rpos);
    free(matrix->cidx);
    free(matrix->value);
    free(matrix);
}

// 填充稀疏矩阵
void fillSparseMatrix(SparseMatrix *matrix) {
    for (int i = 0; i < matrix->row; i++) {
        matrix->rpos[i] = -1;
    }
    matrix->rpos[matrix->row] = matrix->num;

    for (int i = 0; i < matrix->num; i++) {
        int row, col;
        double value;
        printf("Enter the row, col and value of element %d: ", i);
        scanf("%d %d %lf", &row, &col, &value);

        matrix->cidx[i] = col;
        matrix->value[i] = value;

        if (matrix->rpos[row] == -1) {
            matrix->rpos[row] = i;
        }
    }

    for (int i = matrix->row - 1; i >= 0; i--) {
        if (matrix->rpos[i] == -1) {
            matrix->rpos[i] = matrix->rpos[i + 1];
        }
    }
}

// 输出稀疏矩阵
void printSparseMatrix(SparseMatrix *matrix) {
    for (int i = 0; i < matrix->row; i++) {
        for (int j = 0; j < matrix->col; j++) {
            double value = 0;
            for (int k = matrix->rpos[i]; k < matrix->rpos[i + 1]; k++) {
                if (matrix->cidx[k] == j) {
                    value += matrix->value[k];
                }
            }
            printf("%.2f ", value);
        }
        printf("\n");
    }
}

// 稀疏矩阵乘法
SparseMatrix *sparseMatrixMultiply(SparseMatrix *matrix1, SparseMatrix *matrix2) {
    if (matrix1->col != matrix2->row) {
        printf("Error: The number of columns of matrix1 must be equal to the number of rows of matrix2!\n");
        return NULL;
    }

    SparseMatrix *result = createSparseMatrix(matrix1->row, matrix2->col, 0);

    for (int i = 0; i < matrix1->row; i++) {
        for (int j = 0; j < matrix2->col; j++) {
            double value = 0;
            for (int k = matrix1->rpos[i]; k < matrix1->rpos[i + 1]; k++) {
                int col1 = matrix1->cidx[k];
                for (int l = matrix2->rpos[col1]; l < matrix2->rpos[col1 + 1]; l++) {
                    if (matrix2->cidx[l] == j) {
                        value += matrix1->value[k] * matrix2->value[l];
                    }
                }
            }
            if (value != 0) {
                result->num++;
            }
        }
    }

    result->rpos[0] = 0;
    for (int i = 0; i < result->row; i++) {
        int count = 0;
        for (int j = 0; j < matrix2->col; j++) {
            double value = 0;
            for (int k = matrix1->rpos[i]; k < matrix1->rpos[i + 1]; k++) {
                int col1 = matrix1->cidx[k];
                for (int l = matrix2->rpos[col1]; l < matrix2->rpos[col1 + 1]; l++) {
                    if (matrix2->cidx[l] == j) {
                        value += matrix1->value[k] * matrix2->value[l];
                    }
                }
            }
            if (value != 0) {
                result->cidx[result->num - count - 1] = j;
                result->value[result->num - count - 1] = value;
                count++;
            }
        }
        result->rpos[i + 1] = result->num - count;
    }

    return result;
}

int main() {
    int row1, col1, num1;
    printf("Enter the row, col and num of matrix1: ");
    scanf("%d %d %d", &row1, &col1, &num1);
    SparseMatrix *matrix1 = createSparseMatrix(row1, col1, num1);
    printf("Enter the elements of matrix1:\n");
    fillSparseMatrix(matrix1);

    int row2, col2, num2;
    printf("Enter the row, col and num of matrix2: ");
    scanf("%d %d %d", &row2, &col2, &num2);
    SparseMatrix *matrix2 = createSparseMatrix(row2, col2, num2);
    printf("Enter the elements of matrix2:\n");
    fillSparseMatrix(matrix2);

    SparseMatrix *result = sparseMatrixMultiply(matrix1, matrix2);
    printf("The result of matrix multiplication is:\n");
    printSparseMatrix(result);

    freeSparseMatrix(matrix1);
    freeSparseMatrix(matrix2);
    freeSparseMatrix(result);

    return 0;
}

该程序首先定义了一个稀疏矩阵的压缩存储结构体，包含了行数、列数、非零元素个数、每行第一个非零元素在value中的位置、非零元素所在的列和非零元素的值等信息。然后，通过createSparseMatrix函数创建了一个稀疏矩阵，并通过fillSparseMatrix函数填充了非零元素的值。接着，通过sparseMatrixMultiply函数实现了稀疏矩阵的乘法，并通过printSparseMatrix函数输出了结果。最后，通过freeSparseMatrix函数释放了内存空间。