2012-07-09 69 views
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'指向的相同位置。另外,我将它解除引用来移动“左”或“右”,所以我认为它应该起作用。

我认为这是通过值vs指针传递指针的一个基本问题,但我找不到一个清晰的解释,为什么我不能使用指针的局部变量来更改树。

+8

你确定这是C吗? 'new'是一个C++关键字。 – C0deH4cker 2012-07-09 04:13:42

+4

除此之外,“C或C++”的东西是不言而喻的。本代码中的指针误解同样适用于这两种语言。 – MatthewD 2012-07-09 06:29:38

回答

1

假设你有

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

你会想到, x还包含3478
我知道你不会,对你的rootitr也是如此。

这是一个经典的铅笔和纸张问题(大多数指针问题),当遇到像这样的问题时,绝对值得拔出一些死树。

下面是您的其中一种情况的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 ____ 
      | | 
       ---- 

铅笔和纸是要弄清楚指针的最佳方式。

+0

感谢您的详细视觉答案。 – codereviewanskquestions 2012-07-10 06:43:16

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); 
    } 
} 
+0

只需要添加,'insert'签名就会'insert(node *&root,int val);'。为第一个选项。 – Naveen 2012-07-09 04:20:08

+0

这并没有从根本上回答提出的问题:为什么不更新树? – 2012-07-09 04:37:28

+0

@jMerliN为什么不呢?我正在处理的主要问题是调用者的根目录不是一个常量。 – 2012-07-09 04:39:41

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

虽然仍有插入相同数量的两倍的问题,这是不处理正确在这里。为了测试,最好避免在像这样的函数中创建新的节点。创建节点然后给节点插入新值并让插入找出将其链接到树(包括头部)的位置会更好。

+0

您仍然无视示例代码中的返回值,因此新元素会泄露,并且从不会显示在列表中。 – 2012-07-09 05:38:32

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()imain()值叫什么名字?

A.i被传递到由foo()值,所以在该main()i不受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; 
} 

问:什么将foo()imain()值叫什么名字?

A.i被传递到由foo()值,所以在该main()i不受foo()修改。 i仍然是0.

换句话说,没有什么改变! i现在是一个指针的事实并没有改变,它是通过值传递的。

实际上,在C中,所有的函数参数都是按值计算的。那么,我们如何获得修改变量的函数呢?

如果要将变量传递给该函数的某个函数进行修改,则必须将该变量的地址传递给该函数。 (此为C.是真正的在C++中,你也可以使用引用,但我在这里只谈到指针。)

当你传递一个变量的地址,你正在做两件事情:

  • 您正在计算的可变

  • 存储器地址,则通过值顺便指出存储器地址给该函数。

内存地址可用于修改内存地址指向的内存。由于函数内部的内存地址与函数调用外部的内存地址相同(因为它是按值传递的),所以它们指向的变量是相同的!

这真的是最棘手的概念,所以让我们画一些ascii。

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

让我来向您介绍int ii是从内存地址0x04762198开始的4字节(在该系统上)。所有变量都存储在内存中的某个地方,并且将存储在像这样的内存地址中。

如果我们为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)。

0

你做了一个节点但没有将它插入到树中。试试这个代码:

内嵌无效插入(节点*根,int值)

{

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

}

相关问题