抛出未处理的异常：写入访问冲突

Question

我正在用 100 000 个元素分析 Merge Sort 算法，运行很好用 10 000 元素。它向我显示异常。这是我的代码：

void Merge(int *array, int leftIndex, int middleIndex, int rightIndex) {
    int *temp = (int *)calloc(rightIndex, sizeof(int));
    int i = leftIndex, j = middleIndex + 1, k = 0;
    while (i <= middleIndex && j <= rightIndex) {
        if (array[i] < array[j]) {
            temp[k++] = array[i++]; // Here it is showing me exception
        } else {
            temp[k++] = array[j++];
        }
    }
    while (i <= middleIndex) {
        temp[k++] = array[i++];
    }
    while (j <= rightIndex) {
        temp[k++] = array[j++];
    }
    for (i = leftIndex, j = 0; i <= rightIndex; i++, j++) {
        array[i] = temp[j];
    }
}

void MergeSort(int *array, int leftIndex, int rightIndex) {
    if (leftIndex < rightIndex) {
        int middleIndex = (leftIndex + rightIndex) / 2;
        MergeSort(array, leftIndex, middleIndex);
        MergeSort(array, (middleIndex + 1), rightIndex);
        Merge(array, leftIndex, middleIndex, rightIndex);
    }
}

void main() {
    for (long size = 10; size <= 100000; size *= 10) {
        int *array = RandomArray(size);
        MergeSort(array, 0, size - 1);
    }
    _getch();
}

Unhandled exception thrown: write access violation. temp was 0x1110112. occurred

Answer 1

行

    int *temp = (int *) calloc(rightIndex, sizeof(int));

错了。

索引范围从leftIndex到rightIndex，两端都包含在内，所以会处理rightIndex - leftIndex + 1个元素，这种指定元素个数会导致缺少leftIndex 为零时的元素。

越界访问缓冲区将调用未定义的行为，似乎它恰好适用于较少的元素。

该行应该是

    int *temp = (int *) calloc(rightIndex - leftIndex + 1, sizeof(int));

您还应该释放数组：在函数 Merge.

的末尾添加 free(temp);

Answer 2

错误不明显：为临时数组分配的大小不正确。而不是 calloc(rightIndex, sizeof(int)); 你应该有 calloc(rightIndex - leftIndex + 1, sizeof(int)); 在大多数情况下，分配的大小会太大，这可能会造成问题，因为你永远不会释放这些临时数组，但是当 leftIndex 为 0 时，分配的块太短，当您将元素存储在 temp[rightIndex].

时会导致未定义的行为

在许多情况下，未定义的行为可能会被忽视：存储超出数组末尾的值可能会导致 malloc 区域损坏，但分配的 space 可能会有些松弛出于对齐目的而结束，因此这种损坏是无害的。对于较大的块（通常 > 128KB）malloc 可能会将内存映射为一个单独的段，导致此写入尝试落在可访问内存之外，从而导致崩溃。

另请注意，您的错误是将 rightIndex 作为最后一个元素的索引传递而不是将索引传递到切片末尾后容易出错的约定的副作用。这种有害的约定在编程中被广泛教授类，在学生中引起了很多混乱。它需要在代码中进行 +1/-1 调整，这很容易忘记。

这是一个修改后的版本，具有更惯用的 C 语言：

#include <stdio.h>
#include <stdlib.h>

int *RandomArray(long size);

void Merge(int *array, int leftIndex, int middleIndex, int rightIndex) {
    int *temp = calloc(rightIndex - leftIndex, sizeof(int));
    int i = leftIndex, j = middleIndex, k = 0;
    while (i < middleIndex && j < rightIndex) {
        if (array[i] <= array[j]) {
            temp[k++] = array[i++];
        } else {
            temp[k++] = array[j++];
        }
    }
    while (i < middleIndex) {
        temp[k++] = array[i++];
    }
    /* no need to copy the remaining elements from array[j] */
    for (i = leftIndex, k = 0; i < j; i++) {
        array[i] = temp[k++];
    }
    free(temp);
}

void MergeSort(int *array, int leftIndex, int rightIndex) {
    if (rightIndex - leftIndex > 1) {
        int middleIndex = leftIndex + (rightIndex - leftIndex) / 2;
        MergeSort(array, leftIndex, middleIndex);
        MergeSort(array, middleIndex, rightIndex);
        Merge(array, leftIndex, middleIndex, rightIndex);
    }
}

int main() {
    for (long size = 10; size <= 100000; size *= 10) {
        int *array = RandomArray(size);
        MergeSort(array, 0, size);
        free(array);
    }
    _getch();
    return 0;
}

抛出未处理的异常：写入访问冲突

Unhandled exception thrown: write access violation

c

mergesort