C语言归并排序调用free(right)触发段错误，求解决方案

常见错误原因及修复步骤 #

1. 内存分配大小计算错误 #

拆分左右数组时，若分配的内存长度与实际需要存储的元素数量不匹配，会导致后续越界写入破坏堆结构，最终触发free时的段错误。

• 修复：严格按照拆分后的元素数量分配内存。例如数组总长度为n，左半部分长度mid = n / 2，则左数组分配mid * sizeof(int)，右数组分配(n - mid) * sizeof(int)，避免少算或多算字节数。

2. 未检查malloc返回值 #

当内存分配失败时malloc会返回NULL，直接对NULL指针进行写入操作会破坏内存空间，即使后续free(NULL)本身安全，之前的越界操作已经损坏了堆元数据。

• 修复：每次调用malloc后必须检查返回值：

int *right = malloc((n - mid) * sizeof(int));
if (right == NULL) {
    perror("malloc right failed");
    free(left); // 释放已分配的左数组，避免内存泄漏
    return;
}

3. 重复释放或指针被篡改 #

如果right指针被意外赋值为已释放的地址，或是在递归过程中被提前释放，再次调用free会触发段错误。

• 修复：确保每个malloc对应唯一的free操作，递归层内分配的数组仅在当前层排序完成后释放，不要将指针传递到外层函数。

4. 数组拷贝索引越界 #

拷贝元素到左右数组时，索引超出数组范围会破坏堆的管理结构。

• 修复：严格控制拷贝时的索引范围：

// 拷贝左半部分
for (int i = 0; i < mid; i++) {
    left[i] = arr[i];
}
// 拷贝右半部分，通过i - mid将原数组索引转换为右数组的起始索引
for (int i = mid; i < n; i++) {
    right[i - mid] = arr[i];
}

修复后的归并排序核心代码示例 #

void merge(int arr[], int left[], int left_len, int right[], int right_len) {
    int i = 0, j = 0, k = 0;
    while (i < left_len && j < right_len) {
        arr[k++] = left[i] <= right[j] ? left[i++] : right[j++];
    }
    // 拷贝剩余元素
    while (i < left_len) arr[k++] = left[i++];
    while (j < right_len) arr[k++] = right[j++];
}

void merge_sort(int arr[], int n) {
    if (n <= 1) return;

    int mid = n / 2;
    int *left = malloc(mid * sizeof(int));
    if (left == NULL) {
        perror("malloc left failed");
        return;
    }
    int *right = malloc((n - mid) * sizeof(int));
    if (right == NULL) {
        perror("malloc right failed");
        free(left);
        return;
    }

    // 正确拷贝元素到左右数组
    for (int i = 0; i < mid; i++) left[i] = arr[i];
    for (int i = mid; i < n; i++) right[i - mid] = arr[i];

    merge_sort(left, mid);
    merge_sort(right, n - mid);
    merge(arr, left, mid, right, n - mid);

    // 安全释放内存
    free(left);
    free(right);
}

额外调试技巧 #

• 使用valgrind检测内存问题：运行valgrind --leak-check=full ./your_program，它会精准定位越界写入、重复释放等内存错误的具体位置。
• 在GDB中查看指针状态：通过p right查看指针地址，x/10x right查看指针指向的内存内容，确认free前指针是否被意外修改。

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