面试题：C语言多维数组指针在稀疏矩阵存储与运算中的优化

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

// 定义三元组结构体
typedef struct {
    int row;
    int col;
    int value;
} Triple;

// 定义稀疏矩阵结构体
typedef struct {
    Triple *data;
    int rows;
    int cols;
    int num_nonzero;
} SparseMatrix;

// 初始化稀疏矩阵
SparseMatrix* createSparseMatrix(int rows, int cols, int num_nonzero) {
    SparseMatrix *matrix = (SparseMatrix*)malloc(sizeof(SparseMatrix));
    matrix->rows = rows;
    matrix->cols = cols;
    matrix->num_nonzero = num_nonzero;
    matrix->data = (Triple*)malloc(num_nonzero * sizeof(Triple));
    return matrix;
}

// 释放稀疏矩阵内存
void freeSparseMatrix(SparseMatrix *matrix) {
    free(matrix->data);
    free(matrix);
}

// 输入稀疏矩阵数据
void inputSparseMatrix(SparseMatrix *matrix) {
    printf("请输入 %d 个非零元素的行、列和值:\n", matrix->num_nonzero);
    for (int i = 0; i < matrix->num_nonzero; i++) {
        scanf("%d %d %d", &matrix->data[i].row, &matrix->data[i].col, &matrix->data[i].value);
    }
}

// 打印稀疏矩阵
void printSparseMatrix(SparseMatrix *matrix) {
    for (int i = 0; i < matrix->rows; i++) {
        for (int j = 0; j < matrix->cols; j++) {
            int found = 0;
            for (int k = 0; k < matrix->num_nonzero; k++) {
                if (matrix->data[k].row == i && matrix->data[k].col == j) {
                    printf("%d ", matrix->data[k].value);
                    found = 1;
                    break;
                }
            }
            if (!found) {
                printf("0 ");
            }
        }
        printf("\n");
    }
}

// 稀疏矩阵乘法
SparseMatrix* multiplySparseMatrices(SparseMatrix *matrix1, SparseMatrix *matrix2) {
    if (matrix1->cols != matrix2->rows) {
        printf("矩阵维度不匹配，无法相乘\n");
        return NULL;
    }

    SparseMatrix *result = createSparseMatrix(matrix1->rows, matrix2->cols, 0);
    int **resultArray = (int**)malloc(matrix1->rows * sizeof(int*));
    for (int i = 0; i < matrix1->rows; i++) {
        resultArray[i] = (int*)calloc(matrix2->cols, sizeof(int));
    }

    for (int i = 0; i < matrix1->num_nonzero; i++) {
        int row1 = matrix1->data[i].row;
        int col1 = matrix1->data[i].col;
        int val1 = matrix1->data[i].value;
        for (int j = 0; j < matrix2->num_nonzero; j++) {
            int row2 = matrix2->data[j].row;
            int col2 = matrix2->data[j].col;
            int val2 = matrix2->data[j].value;
            if (col1 == row2) {
                resultArray[row1][col2] += val1 * val2;
            }
        }
    }

    // 统计结果矩阵中的非零元素个数
    int nonZeroCount = 0;
    for (int i = 0; i < matrix1->rows; i++) {
        for (int j = 0; j < matrix2->cols; j++) {
            if (resultArray[i][j] != 0) {
                nonZeroCount++;
            }
        }
    }

    result->num_nonzero = nonZeroCount;
    result->data = (Triple*)malloc(nonZeroCount * sizeof(Triple));
    int index = 0;
    for (int i = 0; i < matrix1->rows; i++) {
        for (int j = 0; j < matrix2->cols; j++) {
            if (resultArray[i][j] != 0) {
                result->data[index].row = i;
                result->data[index].col = j;
                result->data[index].value = resultArray[i][j];
                index++;
            }
        }
        free(resultArray[i]);
    }
    free(resultArray);

    return result;
}

// 性能优化点解释：
// 1. **减少不必要的内存访问**：
//    - 使用三元组存储稀疏矩阵，仅存储非零元素，减少了存储开销。在矩阵乘法过程中，只对非零元素进行操作，减少了大量无效的零元素访问。
//    - 在计算结果矩阵时，通过提前判断矩阵维度是否匹配，避免了无效的乘法运算，减少了不必要的内存访问。
// 2. **减少不必要的计算**：
//    - 仅对非零元素进行乘法运算，跳过了零元素之间以及零元素与非零元素之间的乘法计算，大大减少了计算量。
//    - 在结果矩阵生成过程中，使用calloc初始化结果数组，减少了手动初始化的操作。同时通过一次遍历统计非零元素个数，然后再填充结果矩阵的三元组数据，避免了重复判断是否为零元素的操作。

int main() {
    int rows1, cols1, num_nonzero1;
    printf("请输入第一个稀疏矩阵的行数、列数和非零元素个数:\n");
    scanf("%d %d %d", &rows1, &cols1, &num_nonzero1);
    SparseMatrix *matrix1 = createSparseMatrix(rows1, cols1, num_nonzero1);
    inputSparseMatrix(matrix1);

    int rows2, cols2, num_nonzero2;
    printf("请输入第二个稀疏矩阵的行数、列数和非零元素个数:\n");
    scanf("%d %d %d", &rows2, &cols2, &num_nonzero2);
    SparseMatrix *matrix2 = createSparseMatrix(rows2, cols2, num_nonzero2);
    inputSparseMatrix(matrix2);

    SparseMatrix *result = multiplySparseMatrices(matrix1, matrix2);
    if (result) {
        printf("结果稀疏矩阵:\n");
        printSparseMatrix(result);
        freeSparseMatrix(result);
    }

    freeSparseMatrix(matrix1);
    freeSparseMatrix(matrix2);

    return 0;
}
星途面试题库

面试题：C语言多维数组指针在稀疏矩阵存储与运算中的优化

知识考点

面试题答案
