如何修复代码中的运行时间错误（堆损坏）？

Question

这是基于书中算法（那不勒斯）的快速排序代码。结果是正确的，但在调试结束时它有一个运行时间错误，我无法修复它。错误是 heap corruption 请帮助我修复或改进它（如果它是错误的）。谢谢大家的回答。

#include <conio.h>
#include <iostream>
using namespace std;

int partition( int *A, int p, int q)
{
    int x = A[p];
    int i = p;
    for (int j = p+1; j <= q; j++)
    {
        if (A[j] <= x)
        {
            i++;
            swap (A[j],A[i]);
        }
    }
    swap (A[i],A[p]);
    return i;
}

void Quick_sort( int *A, int p, int r)
{
    int q;
    if( p<r)
    {
        q = partition(A,p,r);
        Quick_sort( A, p, q-1);
        Quick_sort( A, q+1, r);
    }
}

void main()
{
    int n;
    cout << "How many elements do you want to sort(quicksort)? ";
    cin >> n;
    int *A;
    A = new int [n];
    for (int k=0;k<n;k++)
    {
        cout << "A["<<k<<"]= ";
        cin >> A[k];
    }

    cout << endl;

    Quick_sort(A,1,n);

    cout << "\nsorted array: " <<endl;
    for (int i = 1; i < n+1; i++)
    {
        cout << A[i]<<"\t";
    }
    cout << endl;
    delete A;
}

问题是：为什么这段代码会出错？您在其中看到了多少个错误？

Answer 1

您有一个所谓的 "fence post error"，其中您的数组索引相差一个。行数

A =(int *) malloc(n * sizeof(int));

和

for (int k=1;k<=n;k++)
{
    cout << "A["<<k<<"]= ";
    cin >> A[k];
}

可能会导致错误，您以 1 而不是 0 开始索引。代码应该是

for (int k=0;k<n;++k)
{
    cout << "A["<<k<<"]= ";
    cin >> A[k];
}

请注意，您在第二个 for 循环中也有同样的错误

Answer 2

代码应为：for (int k=1;k<=n;k++) 而不是 for(int k=0;k<n;++k) 并更改行： A = new int [n]; 与 A = new int [n+1]; 我调试它没有错误！祝你好运

如何修复代码中的运行时间错误（堆损坏）？

How can I fix the run time error (Heap corruption) in my code?

c++

algorithm

debugging

runtime-error

如何修复代码中的 运行 时间错误（堆损坏）？

How can I fix the run time error (Heap corruption) in my code?

c++

algorithm

debugging

runtime-error

如何修复代码中的运行时间错误（堆损坏）？