logo标签列表

为什么使用本地指针不起作用

c++cpointers
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);

我知道这个代码不会起作用，因为insert函数中的'itr'是一个局部变量，所以它不会反映方法之外的树。然而，我不清楚为什么它不起作用。尽管'itr'是一个局部变量，但'itr'指向与'root'相同的位置。此外，我正在取消引用它来移动'left'或'right'，所以我认为它应该工作。
我认为这是传递指针的基本问题，即指针按值传递和指针，但我找不到一个清晰的解释，说明为什么不能使用指针的局部变量来更改树。
8
你确定这是 C 语言吗？new 是 C++ 的关键字。 - C0deH4cker
4
"C或C++"这个东西与本质无关。在这段代码中，指针的误解同样适用于这两种语言。 - MatthewD
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);
    }
}
只是补充一下，第一个选项中insert的签名将会是insert(node*& root, int val);。 - Naveen
这并没有从根本上回答所提出的问题：为什么树没有被更新？ - Justin Summerlin
@jMerliN 为什么不呢？我要解决的主要问题是调用者根不是常量。 - Captain Giraffe
能够修改头节点并不是树没有被修改的原因；将新叶节点链接到树中的代码不存在。虽然我同意这是问题的一部分。 - Justin Summerlin
1

这里有两个问题。首先，在您的示例用法中，您有：

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);

虽然这里仍然存在同一数字插入两次的问题，而且处理不当。为了测试的缘故，最好避免在函数内部创建新节点。最好先创建节点，然后将具有新值的节点提供给insert，并让insert找出将其链接到树中（包括头节点）的位置。

你在示例代码中仍然忽略了返回值，因此新元素会泄漏并且永远不会显示在列表中。 - Ben Voigt
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;
}

问：foo() 被调用后，main() 中的 i 的值是多少？

答：i 是按值传递给 foo() 的，因此 foo() 不会修改 main() 中的 i。 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;
}

问：在调用foo()后，main()中的i的值是多少？

答：i被按值传递给foo()，因此foo()不会修改main()中的i。 i仍然为0。

换句话说，没有任何改变！i现在是指针并不改变它被按值传递的事实。

实际上，在C语言中，所有函数参数都是按值传递的。那么，我们如何让函数修改一个变量呢？

如果你想将一个变量传递给一个函数以便该函数修改它，你必须将该变量的地址传递给函数。（这对于C语言是正确的。在C++中，你也可以使用引用，但我这里只谈论指针。）

当你传递一个变量的地址时，你正在做两件事：

  • 你正在计算一个变量的内存地址

  • 你正在通过值传递该内存地址到函数中。

内存地址可用于修改内存指向的内存。由于函数内部的内存地址与函数调用外部的内存地址相同（因为它是按值传递的），它们所指向的变量是相同的！

这确实是最棘手的概念，让我们画一些ASCII图。

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

让我介绍一下int i。在这个系统上，i占用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）。

1
假设您有：
int x = 0;
int y = x;
y = 3478;

你会期望x也包含3478吗？
我知道你不会，同样的情况也适用于你的root和itr。

这是一个经典的纸笔问题（大多数指针问题都是如此），当你遇到这种问题时，拿出一些纸张来解决它绝对是值得的。

这里有一个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   ____
             |    |
              ----

铅笔和纸是解决指针问题的最佳方式。

感谢您以详细的图示回答。 - codereviewanskquestions
0
你创建了一个节点，但没有将其插入到树中。尝试使用以下代码：
内联 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;
}

}

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接