2

私はこれらの手順を持っています

#include <iostream>
using namespace std;

int parent(int i ){
    return  i/2;
}

int left(int i ){
    return  2*i;
}

int right(int i){
    return 2*i+1;    
}

int a[]={ 27,17,3,16,10,1,5,7,12,4,8,9,10};
int n=sizeof(a)/sizeof(int);

void max_Heapify(int i){
    int largest=0;
    int l=left(i);
    int r=right(i);
    if(l<=n && a[l]>a[i]){
        largest=l;
    }
    else{
        largest=i;
    }
    if(r< n && a[r]>a[largest]){
        largest=r;
    }
    if (largest!=i){
        int t=a[i];
        a[i]=a[largest];
        a[largest]=t;
    }
    max_Heapify(largest);
}

int main(){
     max_Heapify(2);
     for (int i=0;i<n;i++){
         cout<<a[i]<<"  ";
     }    
return 0;
}

実行すると正常にコンパイルされますが、実行が異常に停止した後、なぜ実行されているのですか? このコードを見て助けてください

Max-Heapify[2](A, i):
 left ← 2i
 right ← 2i + 1
 largest ← i
 if left ≤ heap-length[A] and A[left] > A[i] then:
 largest ← left
 if right ≤ heap-length[A] and A[right] > A[largest] then:
 largest ← right
 if largest ≠ i then:
 swap A[i] ↔ A[largest]
 Max-Heapify(A, largest)

ウィキペディアより。

4

5 に答える 5

3

ウィキペディアの記事の疑似コードを C++ コードに変換しましたが、誤ってロジックを変更しました。ウィキペディアの記事では、再帰が条件付きでのみ発生することに気付くでしょう。つまり、if largest ≠ i

if largest ≠ i then:
    swap A[i] ↔ A[largest]
    Max-Heapify(A, largest)

C++ に変換すると、次のようになります。

if (largest != i) {
  swap(a[i], a[largest]);
  Max_Heapify(largest);
}

繰り返しますが、 の再帰呼び出しは条件付きでMax_Heapifyのみ発生することに注意してください。コードでは、unconditionallyを再帰的に呼び出します。つまり、何があっても再帰を続けるということです。したがって、明らかに、プログラムはスタック オーバーフローでクラッシュします。反復とは異なり、スタック スペースがすぐに不足するため、無限に再帰することはできません。 largest != iMax_Heapify

于 2010-11-15T14:38:01.937 に答える
1

再帰を終了する基本的なケースがないため、最終的にスタック オーバーフローが発生していると思います。終わったことをいつ伝えられるかを考えて、優雅にその役割から抜け出すことができるようにします。

于 2010-11-15T14:16:16.090 に答える
0

これが私が書いたバージョンです、あなたは見てみることができます。

http://code.google.com/p/clibutils/source/browse/src/c_heap.c

于 2011-04-18T05:53:51.753 に答える
0

おそらく、常に末尾再帰的に呼び出す必要はありませんmax_Heapifyが、代わりに、ソート ヒープの一番下のサイズに達したときに戻る必要があります。何が起こるかというと、プログラムがスタックを使い果たします。

また、チェックしてくださいstd::swap。

于 2010-11-15T14:16:39.863 に答える
0

関数max_Heapifyは常に無限に再帰します。スタック オーバーフローが発生しています (小さい s、小さい o)。

デバッガーでコードをステップ実行すると、この種のことはすぐに明らかになります。

于 2010-11-15T14:16:57.227 に答える