1

この minheap コードについて助けが必要です:

#include < vector>

using namespace std;

class heap {

    vector <int> v;

    public:

        int hSize()
        {
            return v.size();
        }

        int rsize()
        {
            return  hSize() - 1;
        }    

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

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

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

        void swap(int i, int j)
        {
            int temp = v[j];
            v[j] = v[i];
            v[i] = temp;
        }

        void push(int e)
        {

            v.push_back(e);
            int id = rsize(); 

            if (hSize() > 1)
                while (v[parent(id)] > v[id]) {               
                    swap(parent(id), id);
                    id = parent(id);
                }
        }

        int pop ()
        {

          int f = 0;  
          int p = v[0];

          v[0] = v[rsize()];

          if (hSize() > 1) {
              while (v[left(f)] < v[f] || v[right(f)] < v[f]) {
                    if (v[left(f)] < v[f] && v[right(f)] < v[f]) {
                        if (v[left(f)] < v[right(f)]) {
                            swap(left(f), f);
                            f = left(f);
                    }
                    else { 
                            swap(right(f), f);
                            f = right(f);
                    }
                }

                else {
                    if (v[left(f)] < v[f]){
                         swap(left(f), f);
                         f = left(f);
                    }
                    else {
                         swap(right(f), f);
                         f = right(f);
                        }
                    }
                } 
          }
          else { }

          v.resize(rsize());
          return p;
        }

        void show()
        {
            if (hSize() > 0) {
                cout << "Heap content: ";
                for (int i = 0; i < hSize(); i++) cout << v[i] << " ";
            }
            else cout << "\nHeap successfully emptied!";  
            cout << "\n";          
        }

        bool Empty()
        {
            return v.empty();
        }

        ~heap()
        {
            v.clear();
        }

    };

このコードは、画面上の最後の要素をポップするときに乱数を出力することを除いて、ほとんどすべてを正しく実行します。あなたの意見は何ですか？

ありがとう！

4

2 に答える 2

2

push()に 1 つ、に 1つ、2 つの同様の問題がありpop()ます。id != 0プッシュでは、を見る前にそれを確認する必要がありますv[parent(id)]。ルートにいる場合id == 0は停止する必要があります。同様に、 ( or ) にアクセスする前に、 (or ) がベクトル内にあるpop()かどうかを確認する必要があります。そうでない場合は、ヒープの最下部に達しているため、停止する必要があります。right(f)left(f)v[right(f)]v[left(f)]

于 2010-02-25T12:29:16.800 に答える
1

デバッグ

  • valgrindを使用してコードを実行し、エラーが報告されるかどうかを確認できます。
  • デバッガー内でコードを実行できます（デバッグには時間がかかりますが、成功する可能性が高くなります）。

コーディング アサーションを使用する必要があります。たとえば、swap関数の最初の行は、assert(i >= 0 && i < v.size());と同様にj。これらの2つのアサーションを入れると、エラーがわかると思います。完了したら、必要に応じてアサーションをコメントアウトできます（ただし、一部のアサーションは常にオンのままにしておくことを好む人もいます）。

更新 あなたのコードは大丈夫でした。スワップ内に境界チェックを追加し、満たされない場合は返す必要があります。コードとテストケース（実行時に合格）は次のとおりです。

#include <vector>
#include <iostream>
#include <cassert>
#include <cstdlib>

using namespace std;

class heap {

    vector <int> v;

    public:

        int hSize()
        {
            return v.size();
        }

        int rsize()
        {
            return  hSize() - 1;
        }

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

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

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

        void swap(int i, int j)
        {
            //assert(i >= 0 && i < v.size()); 
            //assert(j >= 0 && j < v.size()); 
            if(i >= v.size() || j >= v.size()) return;
            int temp = v[j];
           v[j] = v[i];
            v[i] = temp;
        }

        void push(int e)
        {

            v.push_back(e);
            int id = rsize();

            if (hSize() > 1)
                while (v[parent(id)] > v[id]) {
                    swap(parent(id), id);
                    id = parent(id);
                }
        }

        int pop ()
        {

          int f = 0;
          int p = v[0];

          v[0] = v[rsize()];

          if (hSize() > 1) {
                  while (v[left(f)] < v[f] || v[right(f)] < v[f]) {
                          if (v[left(f)] < v[f] && v[right(f)] < v[f]) {
                                  if (v[left(f)] < v[right(f)]) {
                                          swap(left(f), f);
                                          f = left(f);
                                  }
                                  else {
                                          swap(right(f), f);
                                          f = right(f);
                                  }
                          }

                          else {
                                  if (v[left(f)] < v[f]){
                                          swap(left(f), f);
                                          f = left(f);
                                  }
                                  else {                                         swap(right(f), f);
                                          f = right(f);
                                  }
                          }
                  }
          }
          else { }

          v.resize(rsize());
          return p;
        }

        void show()
        {
                if (hSize() > 0) {
                        cout << "Heap content: ";
                        for (int i = 0; i < hSize(); i++) cout << v[i] << " ";
                }
                else cout << "\nHeap successfully emptied!";
                cout << "\n";
        }

        bool Empty()
        {
                return v.empty();
        }

        ~heap()
        {
                v.clear();
        }

};


int main()
{
        heap h;
        for(int i = 0; i < 10; i++) {
        h.push(rand()%10);
        h.push(4);
        h.push(3);
        h.push(2);
        h.push(1);
        h.push(0);
        h.push(5);
        h.push(-6);
        h.push(7);
        h.show();
        h.pop();
        h.pop();
        h.pop();
        h.pop();
        h.pop();
        h.pop();
        h.pop();
        h.pop();
        h.pop();
        h.show();
        }
}

アサーションを挿入した後、デバッガーでコードを実行して、クラッシュが行swap(right(f), f);で発生しright(f)、範囲外であることを確認しました。

于 2010-02-25T09:28:55.503 に答える