调试断言失败 _crtisValidHeapPointer(block)

Debug assertion failed _crtisValidHeapPointer(block)

我正在尝试在 c/c++ 中实现快速排序,但我一直收到此错误,"Debug assertion failed _crtisValidHeapPointer(block)" 每当我 运行 代码时。

我的代码是:

void QuickSort(int *A, int size) {
if (size < 2) return;
int *L = NULL, *R = NULL, RSize = 0, LSize = 0;

R = (int *)malloc(sizeof(int));
L = (int *)malloc(sizeof(int));

for (int i = 0; i < size; i++) {
    if (A[size - 1] <= A[i]) 
        if( ((int *)realloc(R, (sizeof(int) * (RSize + 2) ))) != NULL )
            R[RSize++] = A[i];
    else 
        if ( ((int *)realloc(L, (sizeof(int) * (LSize + 2) ))) != NULL )
            L[LSize++] = A[i];
}

    QuickSort(L, LSize);
    QuickSort(R, RSize);
    Merge(A, L, R, LSize, RSize);
    free(L);
    free(R);
    return;
}

我知道这与我的数组 L 和 R 的内存分配有关,但我似乎无法弄清楚问题到底是什么。

编辑:找到解决方案

代码:

void QuickSort(int *A, int size) {
if (size < 2) return;
int *L = NULL, *R = NULL, RSize = 0, LSize = 0;

for (int i = 0; i < size; i++) {
    if (A[size - 2] < A[i]) {
        if ((R = (int *)realloc(R, (sizeof(int) * (RSize + 1)))) != NULL) 
            R[RSize++] = A[i];
    }
    else {
        if ((L = (int *)realloc(L, (sizeof(int) * (LSize + 1)))) != NULL) 
            L[LSize++] = A[i];
    }
}
     QuickSort(L, LSize);
     QuickSort(R, RSize);
     Merge(A, L, R, LSize, RSize);
     free(L);
     free(R);
     return;
}

嗯,只有单个 int 分配给两个变量 LR。但稍后在代码中,随着 LSizeRSize 递增,您分配了许多整数。好吧,我看到 realloc 被调用了,但结果没有分配回 LR,所以这会导致问题。

无论如何,快速排序算法在原始数组上可能工作得很好,没有理由为其分配新的临时数组。

问题出在这里:

if( ((int *)realloc(R, (sizeof(int) * (RSize + 2) ))) != NULL )
    R[RSize++] = A[i];

realloc函数returns新数组指针,与if里面的NULL比较,然后丢弃。然后取消引用原始(无效)指针,破坏堆。

要修复,一定要将realloc的结果赋值给指针。

if( (R = (int *)realloc(R, (sizeof(int) * (RSize + 2) ))) != NULL )

您还应该包括一些错误检查以中止循环,以防分配失败,以 else 语句的形式对此 if。如当前所写,如果 realloc 失败,则循环将继续完成,每次迭代都会跳过数组,然后 return 损坏的结果。