c - 为什么点在释放时会崩溃？

Question

在下面的代码中，结果是可以的，但是执行finish时代码会崩溃，并且增加一个错误:Heap corruption detected, the free list is damaged at 0x600000008f50

int *mergeSort(int *a,int count) {

    int leftCount  = count / 2;
    int rightCount = count - leftCount;
    int *leftData  = getData(a, 0, leftCount);
    int *rightData = getData(a, leftCount, count);

    int *sortedLeftData  = mergeSort(leftData, leftCount);
    int *sortedRightData = mergeSort(rightData, rightCount);

    int *resultData = mergeData(sortedLeftData, sortedRightData, leftCount,
                                rightCount);

    return resultData;
}

int *getData(int *a,int from, int to) {

    if (from > to) { return nil; }
    int *res = malloc(to - from + 1);
    for (int index = from; index < to; index ++) {

        int value = a[index];
        res[index-from] = value;
    }
    return res;
}

int *mergeData(int *a, int *b, int acount, int bcount) {

    int *result = malloc(acount + bcount);

    int aindex,bindex,rindex;
    aindex = bindex = rindex = 0;

    while (aindex < acount | bindex < bcount) {

        int value,avalue = INT_MAX,bvalue = INT_MAX;
        if (aindex < acount) { avalue = a[aindex]; }
        if (bindex < bcount) { bvalue = b[bindex]; }
        // get value from a point.
        if (avalue <= bvalue) {

            value = avalue;
            aindex ++;
        }else {
            // get value from b point.
            value = bvalue;
            bindex ++;
        }

        result[rindex] = value;
        rindex ++;
    }

    return result;
}

我不明白为什么在释放点时会崩溃，任何答案都会有帮助，谢谢。

Answer 1

您的所有分配都太小，因此您溢出了缓冲区。

malloc 函数分配请求的字节数。如果您的元素是 int 类型，则需要将所需元素的数量乘以 sizeof(int)。 例如

int *result = malloc((acount + bcount) * sizeof(int));

我在阅读您的代码时发现的其他潜在问题是:

1. 使用按位或运算符代替逻辑或:

   while (aindex < acount | bindex < bcount)
                       // ^ should be ||
   

2. 您永远不会释放您的临时缓冲区，因此您的程序会疯狂地泄漏以耗尽内存。您必须在 mergeSort 函数之后释放 leftData、rightData、sortedLeftData 和 sortedRightData你已经完成了它们。

   注意归并排序其实不需要那么多分配。这样做会对性能产生巨大影响。一个高效的实现只需要一个额外的缓冲区用于临时操作，可以在开始时分配。