4
inline void insert(node *root, int value)
{
    if(!root)
    {
        root = new node();
        root->value = value;
    }
    else
    {
        node *itr = root;
        while(1)
        {
            if(itr->value > value)
                itr = itr->left;
            else
                itr = itr->right;
            if(!itr)
            {
                itr = new node();
                itr->value = value; 

                break;
            }

        }
    }
}

// このように挿入関数を呼び出します

node *head = 0;
insert(head, 5);
insert(head, 10);
insert(head, 3);
insert(head, 1);
insert(head, 4);

挿入関数の「itr」はローカル変数であるため、このコードが機能しないことはわかっています。したがって、メソッドの外部のツリーは反映されません。しかし、なぜそれがうまくいかないのか、はっきりとはわかりません。「itr」はローカル変数ですが、「itr」は「root」が指す場所と同じ場所を指します。また、「左」または「右」に移動するために逆参照しているので、うまくいくはずです。

これは、値とポインターでポインターを渡す基本的な問題だと思いますが、ポインターのローカル変数を使用してツリーを変更できない理由の明確な説明が見つかりませんでした。

4

5 に答える 5

1

はい、このc++コードでは実際に参照を使用する必要があります。

node * treeRoot = 0;
insert( treeRoot , 4 );  // treeRoot needs to be changed for this to work. So a reference is required. 

この場合、関数は次のように宣言する必要があります。

void insert(node* &root, int value);

別の方法は、ダブルポインタを使用することです。

node * treeRoot = 0;
insert( &treeRoot , 4 );  // treeRoot needs to be changed for this to work. So a pointer to the pointer will work. 

この場合、関数は次のように宣言する必要があります。

void insert(node** root, int value);

また、これはコンパクトでエレガントな再帰的ソリューションを探索する絶好の機会です。(ただし、ここではインライン化は機能しません)

void insert(node* &root, int value)
{
    if(!root)
    {
        root = new node();
        root->value = value;
    }
    else
    {
        if(root->value > value)
            insert( root->left, value );
        else
            insert( root->right, value);
    }
}
于 2012-07-09T04:18:17.730 に答える
1

ここには2つの問題があります。まず、使用例では、次のようになります。

node *head = 0;

これを実行すると、呼び出しごとに新しいノードが作成されることになります。

if (!root) {}

常に真実になります。次に、ご指摘のとおり、ツリーを更新すると、新しいノードが作成されますが、実際にはツリーに挿入されません。これらの問題の両方を修正するには、次のようにします。

node* insert(node *root, int value) {
    if(!root) {
        root = new node();
        root->value = value;
    } else {
        node *itr = root;
        node **where = 0;
        while(1) {
            if(itr->value > value) {
                where = &itr->left;
                itr = itr->left;
            } else {
                where = &itr->right;
                itr = itr->right;
            }
            if(!itr) {
                itr = new node();
                itr->value = value; 
                // Insert the new node, to fix the second issue
                *where = itr;
                break;
            }
            prev = itr;    
        }
    }
    return root; // This always returns the tree, solves problem 1, which can also be solved using references or ptr-to-ptr as other people have mentioned
}

次に、あなたの例は次のようになります。

node* head = insert(0, 5);
insert(head, 10);
insert(head, 3);
insert(head, 1);
insert(head, 4);

同じ番号を2回挿入するという問題はまだありますが、ここでは適切に処理されません。また、テストのために、このような関数内に新しいノードを作成しないようにすることをお勧めします。ノードを作成してから、挿入する新しい値をノードに指定し、挿入によって、ツリー(ヘッドを含む)のどこにリンクするかを判断できるようにすることをお勧めします。

于 2012-07-09T04:20:29.840 に答える
1

C (および C++) のポインターは、正しく考えればそれほど難しくありません。

次のコードでデモンストレーションしましょう。

void foo(int i) {
    i = i + 5;
}

int main()
{
    int i = 5;

    foo(i);
    printf("i is %d\n", i);

    return 0;
}

Q.呼ばれた後のiinの値はどうなりますか?main()foo()

A. iは に値渡しさfoo()れるため、iinmain()は によって変更されませんfoo()iまだ5です。

それでは、コードを少し変更しましょう。

void foo(int* i) {
    i = malloc(sizeof(int));
}

int main()
{
    int *i = 0;

    foo(i);
    printf("i is %p\n", i); /* printf a pointer with %p */

    return 0;
}

Q.呼ばれた後のiinの値はどうなりますか?main()foo()

A. iは に値渡しさfoo()れるため、iinmain()は によって変更されませんfoo()iはまだ 0 です。

つまり、何も変わっていません!ポインタであることiは、値渡しであることには変わりありません。

実際、C では、すべての関数パラメーターは値渡しです。では、変数を変更する関数を取得するにはどうすればよいでしょうか。

関数に変数を渡して変更する場合は、その変数のアドレスを関数に渡す必要があります。(これは C にも当てはまります。C++ でも参照を使用できますが、ここではポインターについてのみ話します。)

変数のアドレスを渡すときは、次の 2 つのことを行います。

  • 変数のメモリアドレスを計算しています

  • そのメモリアドレスを値で関数に渡しています。

メモリ アドレスを使用して、メモリ アドレスが指すメモリを変更できます。関数内のメモリ アドレスは関数呼び出しの外のアドレスと同じであるため (値渡しであるため)、それらが指す変数は同じです!

これは本当に最も難しい概念なので、ASCII を描いてみましょう。

|            |
+------------+ <- 0x04762198
|            |
|     i      |
|            |
|            |
+------------+ <- 0x0476219C
|            |

を紹介しますint iiは、メモリ アドレス から始まる 4 バイト (このシステムでは)0x04762198です。すべての変数はメモリ内のどこかに保存され、このようなメモリ アドレスになります。

に値を割り当てるとi、その値は上記のメモリ ブロックに格納されます。

関数に渡すiと、関数で使用するために、の値がiメモリ内の別の場所にコピーされます。そのメモリの値は元の と同じになりますiが、その変数のメモリ アドレスは別の場所になります。

ここに独創的なビットがあります。代わりに関数に渡す0x04762198と、その関数は元のi!のメモリ位置にアクセスできるようになります。これはポインタであり、メモリ内のアドレスを指すことからそう呼ばれています。iポインターを使用して関数内のオリジナルを変更したい場合は、それを逆参照します (例: *ptr = 5;)。私たちが実際に行っているのは、 「この値 (5) を が指すメモリに格納してくださいptr ) ということです。

これを実装するためにコードをもう一度変更しましょう。

/*
 * The address of an int* is int**
 */
void foo(int** i) {
    /* dereference to access and modify the original `i` */
    *i = malloc(sizeof(int));
}

int main()
{
    int *i = 0;

    /*
     * Pass the address of i, so foo() can modify i
     */    
    foo(&i);
    printf("i is %p\n", i); /* printf a pointer with %p */

    return 0;
}

違いを見ます?

さて、自分のプログラムで何が間違っているかがわかりますか?

注: 簡潔にするために、通常のエラー チェック (たとえば、malloc() が NULL を返さないことのチェック) は省いています。

于 2012-07-09T05:24:10.677 に答える
1

あなたが持っていたとしましょう

int x = 0;
int y = x;
y = 3478;

x にも が含まれていると思います3478か?
私はあなたがそうしないことを知っていました、そして同じことがあなたのrootitr.

これは古典的な鉛筆と紙の問題 (ほとんどのポインターの問題) であり、このような問題に遭遇した場合は、枯れ木を取り除く価値があります。

これは、右に挿入したいケースの 1 つの ASCII バージョンで、右が NULL です。
矢印は、それぞれの変数が指している場所を示しています。

関数の開始:

           ____
root ---> |    |
          ------
           / \
          /   \
       left   NULL

itr = root;    
           ____
root ---> |    | <--- itr
          ------
           / \
          /   \
       left   NULL

itr = itr->right;
           ____
root ---> |    | 
          ------
           / \
          /   \
       left   NULL <--- itr

if (!itr)
    itr = new node();

           ____
root ---> |    | 
          ------
           / \
          /   \                   ____
       left   NULL      itr ---> |    |
                                  ----

ご覧のとおり、入力ツリーはまったく変更されていません。新しいノードを外部に割り当ててそこに残しただけです。

これはうまくいきます:

           ____
root ---> |    | <--- itr
          ------
           / \
          /   \
       left   NULL

   if (!itr->right)
   {
       itr->right = new node()
   }


           ____
root ---> |    | <--- itr
          ------
           / \
          /   \
       left   ____
             |    |
              ----

鉛筆と紙は、ポインターを把握するための最良の方法です。

于 2012-07-09T09:26:29.760 に答える
0

ノードを作成しましたが、ツリーに挿入していません。このコードを試してください:

inline void insert(node *root, int value)

{

if(!root)

{
    root = new node();
    root->value = value;
}
else
{
    node *itr = root , *prev;
    while(itr)
    {
        prev=itr;
        if(itr->value > value)
            itr = itr->left;

        else
            itr = itr->right;
    }

        itr = new node();
        itr->value = value;

        if(value < prev->value)
        prev->left=itr;
        else
        prev->right=itr;
}

}

于 2012-07-09T08:03:02.190 に答える