1

これはばかげた質問のように思えるかもしれません。私は頻繁に混乱することを知っていますが、コードに執着するのをやめて、なぜそれを使用する必要があるかという本当の問題に集中できるように、コードを理解する必要があります。

したがって、コードでは、次のようないくつかの割り当てが表示されます。

struct bst_node** node = root;
node = &(*node)->left;
node = &(*node)->right;

is there an invisible parenthesis here?

node = &((*node)->right);

この例は、literateprograms.org から取得したものです。

だから私には &(*node) は不要なようで、代わりに node->left と書いた方がいいかもしれませんが、コードは私が理解できない場所で機能しているようで、それは私がそれらの行で何が起こっているのかを誤解しています。特に、「削除された」データを常にツリーの一番下に移動してノードを削除しているコードのある場所で、「物事を壊す」ことなくノードを安全に削除する必要があります。入手方法

old_node = *node;
if ((*node)->left == NULL) {
    *node = (*node)->right;
    free_node(old_node);
else if ((*node)->right == NULL) {
    *node = (*node)->left;
    free_node(old_node);
} else {
    struct bst_node **pred = &(*node)->left;
    while ((*pred)->right != NULL) {
        pred = &(*pred)->right;
    }
    psudo-code: swap values of *pred and *node when the 
    bottom-right of the left tree of old_node has been found.
    recursive call with pred;
}

ツリー構造をそのまま維持できます。これにより構造が完全であることを確認する方法がわかりません。何が起こっているのかを知っている人からの助けをいただければ幸いです。node は、関数呼び出しで作成されたスタック上のローカル変数であると解釈します。これはダブルポインターであるため、スタック内の場所を指します（関数呼び出しの前に &(*node) を実行したため、これを想定しています）、それ自体のスタックまたは前の関数のいずれかであり、そのノードを指しますヒープ上。

上記のサンプルコードでは、どちらかが NULL であるため、左または右のいずれかを切り替えてから、そうでない方を切り替えます (もう一方が NULL ではないと仮定しますか?) 私が言ったように、これがどのように機能するかはわかりません。私の質問は、主に &(*node) <=> ノードだと思うという事実に関連していますが、そうでないかどうかなどを知りたい.

4

2 に答える 2

2

node = &(*node)->right;

ここに見えない括弧がありますか？

node = &((*node)->right);

はい。rightのメンバーのアドレスを取得しています*node。は;->よりも優先されます。C++ 演算子の優先順位(そのリストでは 2 と3 です)&を参照してください (Cと同じ一般的な優先順位です)。->&

だから私には &(*node) は不要なようで、代わりに node->left と書いたほうがいいかもしれません。

あなたの前提は外れています。&(*node)上で説明したように、式はありません。は ではなく&全体に適用されます。(*node)->left(*node)

そのコードでは、ダブルポインターはポインターへのポインターです。これが機能するのと同じように：

   int x = 0;
   int *xptr = &x;
   *xptr = 5;
   assert(x == 5);

これは同じで、ポインター x の値を変更します。

   int someint;
   int *x = &someint;
   int **xptr = &x; 
   *xptr = NULL;
   assert(x == NULL);

投稿したそのコード スニペットでは、ポインターを割り当てると、指すポインター*nodeの値が変更さnodeれます。たとえば、（疑似コード）：

   typedef struct bst_node_ {
     struct bst_node_ *left;
     struct bst_node_ *right;
   } bst_node;

   bst_node * construct_node () {
     return a pointer to a new bst_node;
   }

   void create_node (bst_node ** destination_ptr) {
     *destination_ptr = construct_node();
   }

   void somewhere () {
     bst_node *n = construct_node();
     create_node(&n->left);  // after this, n->left points to a new node
     create_node(&n->right); // after this, n->right points to a new node
   }

優先順位規則のため、これ&n->leftは と同じであることに再度注意してください。&(n->left)それが役立つことを願っています。

C++ では、参照によって関数に引数を渡すことができます。これは、構文的に少し読みやすいコードになることを除けば、ポインタを渡すのと本質的に同じです。

于 2014-02-19T21:27:37.657 に答える