4

構造リストに似たものを作成しています。main の先頭で、null ポインターを宣言します。次に、insert() 関数を数回呼び出し、そのポインターへの参照を渡し、新しい要素を追加します。

しかし、何かが間違っているようです。リストの要素を表示できstd::coutず、警告なしでコンパイルされたとしても、プログラムを壊すだけです。

#include <iostream>

struct node {
    node *p, *left, *right;
    int key;
};

void insert(node *&root, const int key)
{
    node newElement = {};
    newElement.key = key;

    node *y = NULL;
    std::cout << root->key; // this line
    while(root)
    {
        if(key == root->key) exit(EXIT_FAILURE);
        y = root;
        root = (key < root->key) ? root->left : root->right;
    }

    newElement.p = y;

    if(!y) root = &newElement;
    else if(key < y->key) y->left = &newElement;
    else y->right = &newElement;
}

int main()
{
    node *root = NULL;
    insert(root, 5);
        std::cout << root->key; // works perfectly if I delete cout in insert()
    insert(root, 2);
        std::cout << root->key; // program breaks before this line
    return 0;
}

ご覧のとおり、挿入関数で新しい構造要素を作成し、ルート ポインター内に保存します。最初の呼び出しでは while ループは開始されていないので機能し、メイン関数でルートの要素を表示できます。

しかし、2 番目の呼び出しでは、while ループは既に機能しており、説明した問題が発生します。

root->keyこれを最初の呼び出しに配置しても機能しないため、構文に問題があります。

何が問題で、その理由は何ですか?

また、次のようなポインターを介して新しいリストの要素を挿入することを常に見てきました。

node newElement = new node();
newElement->key = 5;
root->next = newElement;

このコードは次と同じですか:

node newElement = {};
newElement.key = 5;
root->next = &newElement;

? 少しきれいになり、メモリを削除する必要がなくなります。

4

4 に答える 4

2

問題は、関数からローカル変数へのポインターを渡しているためです。このようなポインターの逆参照は、未定義の動作です。で割り当てる必要newElementがありnewます。

このコード

node newElement = {};

ローカル変数を作成しますnewElement。関数が終了すると、 のスコープはnewElement終了し、そのメモリは破棄されます。ただし、その破棄されたメモリへのポインターを関数の外部に渡しています。そのメモリへのすべての参照は、関数が終了するとすぐに無効になります。

一方、このコードは

node *newElement = new node(); // Don't forget the asterisk

フリーストアにオブジェクトを割り当てます。このようなオブジェクトはdelete、明示的に指定するまで引き続き使用できます。そのため、それらを作成する関数が終了した後にそれらを使用できます。もちろん、はポインタであるため、そのメンバーにアクセスnewElementするには を使用する必要があります。->

于 2013-04-20T10:35:50.033 に答える
1

ここで学ぶ必要がある重要なことは、スタック割り当てオブジェクトとヒープ割り当てオブジェクトの違いです。挿入関数でnode newElement = {}は、スタックが割り当てられます。つまり、その寿命は、囲んでいるスコープによって決定されます。この場合、関数が終了するとオブジェクトが破棄されることを意味します。それはあなたが望むものではありません。ツリーのルートをnode *rootポインターに格納する必要があります。そのためには、ヒープからメモリを割り当てる必要があります。C++ では、通常は new 演算子で行われます。これにより、ある関数から別の関数にポインターを渡すことができ、ポインターの有効期間がそのポインターのスコープによって決定されることはありません。これは、ヒープに割り当てられたオブジェクトの有効期間の管理に注意する必要があることも意味します。

于 2013-04-20T10:50:06.887 に答える
0

あなたのAlsoコメントには 1 つの問題があります。2 番目の方がきれいかもしれませんが、それは間違っています。新しいメモリを削除する必要があります。そうしないと、存在しなくなったオブジェクトへのポインターになってしまいます。それこそが、new が解決する問題です。

別の問題

void insert(node *&root, const int key)
{
    node newElement = {};
    newElement.key = key;

    node *y = NULL;
    std::cout << root->key; // this line

最初の挿入ルートではまだ NULL であるため、このコードはプログラムをクラッシュさせます。

于 2013-04-20T10:35:34.550 に答える