malloc：释放对象的校验和不正确

Question

下面是做归并排序的函数。但是我在执行时遇到错误。分配的内存(aux)在函数中每次都释放了merge，为什么释放后还要修改？

a.out(65287,0x1112bedc0) malloc: Incorrect checksum for freed object
0x7ff9a4c05888: probably modified after being freed. Corrupt value:
0xb00000003 a.out(65287,0x1112bedc0) malloc: *** set a breakpoint in
malloc_error_break to debug Abort trap: 6

void merge(int arr[], int lo, int mid, int hi) {
    int i = lo; 
    int j = mid + 1;
    int *aux = (int *)malloc((hi - lo + 1) * sizeof(int));
    for (int k = lo; k <= hi; k++) {
        aux[k] = arr[k];
    }   
    for (int k = lo; k <= hi; k++) {
        if (i > mid)
            arr[k] = aux[j++];
        else if (j > hi)
            arr[k] = aux[i++];
        else if (aux[i] > aux[j])
            arr[k] = aux[j++];
        else
            arr[k] = aux[i++];
    } 
    free(aux);
}

void mergesort1(int arr[], int lo, int hi) {
    if (lo >= hi)
        return;
    int mid = lo + (hi - lo) / 2;
    mergesort1(arr, lo, mid);
    mergesort1(arr, mid + 1, hi);
    merge(arr, lo, mid, hi);
}

致电：

mergesort1(arr, 0, 9);

Answer 1

malloc((hi - lo + 1) * sizeof(int)) 为索引从 0 到 hi-lo 的元素分配 space，但是 for (int k = lo; k <= hi; k++) … aux[k] = … 访问索引从 lo 到 [=14= 的元素], 从而写入分配的内存之外。

Answer 2

aux 数组未正确初始化：for (int k = lo; k <= hi; k++) { aux[k] = arr[k]; } 应该是：

    for (int k = lo; k <= hi; k++) {
        aux[k -lo] = arr[k];
    }

您的代码写入超出分配数组的末尾，可能导致 malloc() 和 free() 用来跟踪分配内存的数据损坏。

请注意，i 和 j 也应进行不同的初始化，并且在合并排序算法中包含上限会造成混淆。如果排除 hi，代码更简单，因为不需要 +1/-1 调整：

void merge1(int arr[], int lo, int mid, int hi) {
    int i = 0; 
    int j = mid -= lo;
    int n = hi - lo;
    int *aux = (int *)malloc(n * sizeof(int));
    for (int k = 0; k < n; k++) {
        aux[k] = arr[lo + k];
    }   
    for (int k = lo; k < hi; k++) {
        if (i >= mid)
            arr[k] = aux[j++];
        else if (j >= n)
            arr[k] = aux[i++];
        else if (aux[i] > aux[j])
            arr[k] = aux[j++];
        else
            arr[k] = aux[i++];
    } 
    free(aux);
}

void mergesort1(int arr[], int lo, int hi) {
    if (hi - lo < 2)
        return;
    int mid = lo + (hi - lo) / 2;
    mergesort1(arr, lo, mid);
    mergesort1(arr, mid, hi);
    merge1(arr, lo, mid, hi);
}

调用：mergesort1(arr, 0, 10);，这更简单，因为 10 是数组长度。

可以使用指针算法进一步简化代码：

void merge2(int arr[], int mid, int hi) {
    int *aux = malloc(n * sizeof(*aux));
    for (int i = 0; i < n; i++) {
        aux[i] = arr[i];
    }   
    for (int i = 0, j = mid, k = 0; i < mid;) {
        if (j >= n || aux[i] <= aux[j])
            arr[k++] = aux[i++];
        else
            arr[k++] = aux[j++];
    } 
    free(aux);
}

void mergesort2(int arr[], int n) {
    if (n < 2)
        return;
    int mid = n / 2;
    mergesort2(arr, mid);
    mergesort2(arr + mid, n - mid);
    merge2(arr, mid, n);
}

调用：mergesort2(arr, 10);，其中 10 是数组长度。

malloc：释放对象的校验和不正确

malloc: Incorrect checksum for freed object

c

malloc

recursion

mergesort