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) <=> node 但我想知道是否不是这种情况等有关。

4

2 回答 2

2

这很有用

&(*node)->left<=>&((*node)->left)

此代码编辑的变量是*node. 我需要此代码的上下文以提供更多信息

于 2014-02-19T21:09:26.813 回答
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 回答