2

バイナリ ツリーをテストするプログラムを作成しましたが、実行するとプログラムがクラッシュするようです (btree.exe が動作を停止し、Windows が解決策を確認しています ...)。

デバッガーで実行し、原因と思われる関数 destroy_tree() にブレークポイントを設定すると、期待どおりに実行され、メイン関数に戻りました。Main はプログラムから戻りましたが、カーソルは destroy_tree() に戻り、再帰的にループしました。

最小限のコード サンプルを以下に示しますので、すぐに実行できます。私のコンパイラは MinGW で、デバッガは gdb です (Code::Blocks を使用しています)。

#include <iostream>

using namespace std;

struct node
{
    int key_value;
    node *left;
    node *right;
};

class Btree
{
public:
    Btree();
    ~Btree();
    void insert(int key);
    void destroy_tree();

private:
    node *root;

    void destroy_tree(node *leaf);
    void insert(int key, node *leaf);
};

Btree::Btree()
{
    root = NULL;
}

Btree::~Btree()
{
    destroy_tree();
}

void Btree::destroy_tree()
{
    destroy_tree(root);

    cout<<"tree destroyed\n"<<endl;
}

void Btree::destroy_tree(node *leaf)
{
  if(leaf!=NULL)
  {
    destroy_tree(leaf->left);
    destroy_tree(leaf->right);
    delete leaf;
  }
}

void Btree::insert(int key, node *leaf)
{
    if(key < leaf->key_value)
    {
        if(leaf->left!=NULL)
            insert(key, leaf->left);
        else
        {
            leaf->left = new node;

            leaf->left->key_value = key;
            leaf->left->left = NULL;
            leaf->left->right = NULL;
        }
    }
    else if (key >= leaf->key_value)
    {
        if(leaf->right!=NULL)
            insert(key, leaf->right);
        else
        {
            leaf->right = new node;

            leaf->right->key_value = key;
            leaf->right->left = NULL;
            leaf->right->right = NULL;
        }
    }
}

void Btree::insert(int key)
{
    if(root!=NULL)
    {
        insert(key, root);
    }
    else
    {
        root = new node;

        root->key_value = key;
        root->left = NULL;
        root->right = NULL;
    }
}

int main()
{
    Btree tree;
    int i;

    tree.insert(1);

    tree.destroy_tree();

    return 0;
}

余談ですが、これらの問題をデバッグするために、Code::Blocks 組み込みデバッガーから DDD に切り替える予定です。DDD は、ポインターのアドレスを表示するだけでなく、オブジェクトへのポインターを視覚的に表示できると聞きました。このような問題 (データ構造やアルゴリズムの問​​題) の解決に、切り替えが役立つと思いますか?

4

4 に答える 4

4

destroy_tree() は 2 回呼び出されます。1 回呼び出すと、実行がデストラクタから main() を離れた後に呼び出されます。

leaf!=NULL かどうかをチェックするため、とにかく動作するはずだと思うかもしれませんが、delete はポインターを NULL に設定しません。したがって、destroy_tree() が 2 回目に呼び出されたとき、ルートは NULL ではありません。

于 2009-06-14T19:46:51.253 に答える
0

問題に直接関係していません (または関係している可能性があります) が、構造体にコンストラクターを与えることをお勧めします。例えば：

struct node
{
    int key_value;
    node *left;
    node *right;

    node( int val ) : key_val( val ), left(NULL), right(NULL) {}
};

これを行うと、ノードを作成するときにポインターの設定を気にする必要がなくなり、初期化を忘れることがなくなるため、コードが簡単になります。

DDDに関しては、立派なデバッガですが、率直に言ってデバッグの秘訣はそもそも正しいコードを書くことなので、それをしなくてもいいのです。C++ はこの方向で (コンストラクターの使用のように) 多くの助けを提供しますが、C++ が提供する機能を理解して使用する必要があります。

于 2009-06-14T19:50:32.493 に答える
0

Btree::destroy_tree は、ツリーの nuking に成功した後、'root' を 0 に設定しません。その結果、デストラクタ クラス destroy_tree() が再び呼び出され、すでに破棄されたオブジェクトを破棄しようとしています。

それは未定義の動作になります:)。

于 2009-06-14T19:58:03.303 に答える
0

いったん根を破壊します。
NULL であることを確認して、(デストラクタから) 再試行しないようにします。

void Btree::destroy_tree(node *leaf)
{
  if(leaf!=NULL)
  {
    destroy_tree(leaf->left);
    destroy_tree(leaf->right);
    delete leaf;

    leaf = NULL; // add this line
  }
}
于 2009-06-14T20:02:28.283 に答える