为何矩阵链乘法代码运行时出现Segmentation Fault错误？

核心问题分析与修复步骤 #

1. 数组索引越界（最直接的段错误原因） #

你的m和s数组使用1-based索引（代码中i从1开始），但分配内存时只申请了n个元素的空间（索引范围0~n-1），当j=i+l-1达到n时，访问m[n][...]会直接越界触发段错误。

修复：
将m和s的内存分配改为n+1个元素，适配1-based索引：

// 调整分配大小为n+1，覆盖1~n的索引
long long **m = (long long **)calloc(n+1, sizeof(long long *));
int **s = (int **)calloc(n+1, sizeof(int *));
// 循环范围改为0到n，初始化所有行
for (int i = 0; i <= n; i++) {
    m[i] = (long long *)calloc(n+1, sizeof(long long));
    s[i] = (int *)calloc(n+1, sizeof(int));
    if (m[i] == NULL || s[i] == NULL) {
        printf("Error: memory allocation failed\n");
        exit(1);
    }
}

2. 维度数组p构造错误 #

矩阵链乘法的维度数组p应该是n+1个元素：A₁是p[0]×p[1]，A₂是p[1]×p[2]，…，Aₙ是p[n-1]×p[n]。你当前的代码错误地为每个矩阵单独存储行和列，导致计算q时索引越界。

修复：
重新构造p数组，确保相邻矩阵维度连续：

// main函数中，p的大小改为n+1
int *p = (int *)malloc(sizeof(int) * (n+1));
if (p == NULL) {
    printf("Error: memory allocation failed\n");
    exit(1);
}
srand(time(NULL));
p[0] = rand() % 1001 + 1000; // 第一个矩阵的行数
for (int i = 1; i <= n; i++) {
    // 前一个矩阵的列数 = 当前矩阵的行数，直接继承后生成当前矩阵的列数
    p[i] = rand() % 1001 + 1000;
}

同时修改matrix_chain_multiply中计算q的代码：

long long q = m[i][k] + m[k+1][j] + (long long)p[i-1] * p[k] * p[j];

3. 整数溢出问题 #

矩阵维度为1000~2000，三个数相乘最大值为2000*2000*2000=8e9，远超过INT_MAX（约2.1e9），会导致整数溢出，引发未定义行为（可能表现为段错误或计算结果异常）。

修复：
将m数组的类型改为long long，避免溢出：

// 替换int为long long存储计算结果
long long **m = (long long **)calloc(n+1, sizeof(long long *));
for (int i = 0; i <= n; i++) {
    m[i] = (long long *)calloc(n+1, sizeof(long long));
}
// 初始化时使用LLONG_MAX替代INT_MAX
m[i][j] = LLONG_MAX;
// 计算q时强制转换为long long避免溢出
long long q = m[i][k] + m[k+1][j] + (long long)p[i-1] * p[k] * p[j];

4. 内存释放的对应调整 #

因为m和s的大小改为了n+1，释放时也要循环到n：

for (int i = 0; i <= n; i++) {
    free(m[i]);
    free(s[i]);
}
free(m);
free(s);

完整修复后的代码 #

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
#include <omp.h>

void matrix_chain_multiply(int *p, int n, int num_threads) {
    // Allocate memory for matrix chain and auxiliary arrays (1-based indexing)
    long long **m = (long long **)calloc(n+1, sizeof(long long *));
    int **s = (int **)calloc(n+1, sizeof(int *));
    if (m == NULL || s == NULL) {
        printf("Error: memory allocation failed\n");
        exit(1);
    }
    for (int i = 0; i <= n; i++) {
        m[i] = (long long *)calloc(n+1, sizeof(long long));
        s[i] = (int *)calloc(n+1, sizeof(int));
        if (m[i] == NULL || s[i] == NULL) {
            printf("Error: memory allocation failed\n");
            exit(1);
        }
    }

    // Set the number of threads
    omp_set_num_threads(num_threads);

    // Compute the matrix chain product using dynamic programming
    for (int l = 2; l <= n; l++) {
        #pragma omp parallel for schedule(dynamic)
        for (int i = 1; i <= n - l + 1; i++) {
            int j = i + l - 1;
            m[i][j] = LLONG_MAX;
            for (int k = i; k <= j - 1; k++) {
                long long q = m[i][k] + m[k+1][j] + (long long)p[i-1] * p[k] * p[j];
                if (q < m[i][j]) {
                    m[i][j] = q;
                    s[i][j] = k;
                }
            }
        }
    }

    // Free memory
    for (int i = 0; i <= n; i++) {
        free(m[i]);
        free(s[i]);
    }
    free(m);
    free(s);
}

int main() {
    int n = 10; // number of matrices
    int num_threads = 4; // number of threads to use
    int *p = (int *)malloc(sizeof(int) * (n+1));
    if (p == NULL) {
        printf("Error: memory allocation failed\n");
        exit(1);
    }
    srand(time(NULL));
    p[0] = rand() % 1001 + 1000; // rows of first matrix
    for (int i = 1; i <= n; i++) {
        p[i] = rand() % 1001 + 1000; // columns of current matrix (rows of next)
    }

    double start_time = omp_get_wtime();
    matrix_chain_multiply(p, n, num_threads);
    double end_time = omp_get_wtime();
    double time = end_time - start_time;
    printf("Time: %f\n", time);

    // Free memory
    free(p);

    return 0;
}

内容的提问来源于stack exchange，提问作者phoenixshoxx