-1

このコードは、本「アルゴリズム入門」に記載されています。このために、1つのインデックス付き配列を使用しました

#include <cstdlib>
#include <iostream>

using namespace std;
int n=6;
int x[1000];

void max_heapify(int a[],int i)
{
    int left=2*i;
    int right=2*i+1;
    int largest=i;
    if( left<=n && a[left]>a[largest]){
        largest=left;

    }
    if(right<=n &&  a[right]>a[largest])
    {
        largest=right;

    }
    if(largest!=i)
    {
        int t=a[i];
        a[i]=a[largest];
        a[largest]=t;

    }
    max_heapify(a,largest);
}
void max_heap(int a[])
{
    int heap_length=n;
    for(int i=n/2;i>=1;i--)
        max_heapify(a,i);

}
int main(int argc, char *argv[])
{
    for(int i=1;i<=n;i++)
        cin>>x[i];
    max_heap(x);
    cout<<endl;

    for(int i=1;i<=n;i++)
        cout<<x[i]<<"  ";
    // system("PAUSE");
    //return EXIT_SUCCESS;
    return 0;
}

この入力について

1 5 7 8 3 9

ideone.com では、「時間制限を超えました」と書かれています。Visual Studio でデバッガーを試してみたところ、次の結果が得られました。

max_heap.exe の 0x001c14d9 で初回例外: 0xC00000FD: スタック オーバーフロー。
max_heap.exe の 0x001c14d9 で未処理の例外: 0xC00000FD: スタック オーバーフロー。
max_heap.exe の 0x001c14d9 での初回例外: 0xC0000005: アクセス違反書き込み場所 0x002c0ffc.
max_heap.exe の 0x001c14d9 で未処理の例外: 0xC0000005: アクセス違反の書き込み場所 0x002c0ffc.
プログラム '[6044] max_heap.exe: Native' はコード -1073741819 (0xc0000005) で終了しました。

なにが問題ですか？

4

1 に答える 1

6

あなたmax_heapifyは常に別の再帰で終わります。どの制御パスでも終了は発生しません。これにより、スタック オーバーフローが発生します。

于 2012-03-17T21:47:27.463 に答える