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

Question

在下面的代码中，结果是可以的，但是代码会在执行finish时崩溃，并增加一个错误：Heap corruption detected, 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));

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

使用按位或运算符代替逻辑或：

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

您永远不会释放临时缓冲区，因此您的程序会疯狂地泄漏，从而耗尽内存。您必须在 mergeSort 函数中释放 leftData、rightData、sortedLeftData 和 sortedRightData。

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

Answer 2

我是用单缓冲区实现归并排序的，代码如下：

void mergeSort(int *a, int count) {

    int *tempBuffer = malloc(count * sizeof(int));
    mergeSortWithBuffer(a, 0, 0, count - 1,tempBuffer);
    free(tempBuffer);
}
void mergeSortWithBuffer(int *a, int leftStart, int rightStart, int end, int *tempBuffer) {

    int leftCount  = rightStart - leftStart;
    int rightCount = end - rightStart + 1;
    if (leftCount + rightCount <= 1) { return; }

    if (leftCount != 0) {

        // left dichotomy
        int lls = leftStart;
        int lrs = leftStart + leftCount/2;
        int lnd = rightStart - 1;
        mergeSortWithBuffer(a, lls, lrs, lnd,tempBuffer);
    }

    if (rightCount != 0) {

        // right dichotomy
        int rls = rightStart;
        int rrs = rightStart + rightCount/2;
        int rnd = end;
        mergeSortWithBuffer(a, rls, rrs, rnd,tempBuffer);
    }

    mergeData(a, leftStart, rightStart, end, tempBuffer);
}

void mergeData(int *a, int leftStart, int rightStart, int end,int *tempBuffer) {

    int leftCount  = rightStart - leftStart;
    int rightCount = end - rightStart + 1;

    int lindex,rindex;
    lindex = rindex = 0;

    while (lindex < leftCount || rindex < rightCount) {

        int lv = INT_MAX,rv = INT_MAX;
        if (lindex < leftCount) { lv = a[leftStart + lindex]; }
        if (rindex < rightCount) { rv = a[rightStart + rindex]; }

        if (lv <= rv) {

            tempBuffer[leftStart + lindex + rindex] = lv;
            lindex ++;
        }else {

            tempBuffer[leftStart + lindex + rindex] = rv;
            rindex ++;
        }
    }

    for (int index = 0; index < end - leftStart + 1; index ++) {

        a[leftStart + index] = tempBuffer[leftStart + index];
    }
}

我以为mergeData函数可以在没有temp buffer的情况下互相替换a点的数据，但是逻辑太复杂，效率不快，所以我在这个函数中加入了temp buffer。

如果愿意，您有更好的建议吗？

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

Why does the point crash when free it?

c

heap-memory

mergesort

heap-corruption