爲什麼在這個編程中使用指針指針？

Question

以下程序顯示瞭如何在C程序中構建二叉樹。它使用動態內存分配，指針和遞歸。二叉樹是一個非常有用的數據結構，因爲它允許在排序列表中進行高效插入，搜索和刪除。由於這樣的樹本質上是一個遞歸定義的結構，所以遞歸編程是處理它的自然和有效的方式。

tree 
    empty 
    node left-branch right-branch 

left-branch 
    tree 

right-branch 
    tree 

下面的代碼：

#include <stdlib.h> 
#include <stdio.h> 

struct tree_el { 
    int val; 
    struct tree_el * right, * left; 
}; 

typedef struct tree_el node; 

void insert(node ** tree, node * item) { 
    if(!(*tree)) { 
     *tree = item; 
     return; 
    } 
    if(item->val<(*tree)->val) 
     insert(&(*tree)->left, item); 
    else if(item->val>(*tree)->val) 
     insert(&(*tree)->right, item); 
} 

void printout(node * tree) { 
    if(tree->left) printout(tree->left); 
    printf("%d\n",tree->val); 
    if(tree->right) printout(tree->right); 
} 

void main() { 
    node * curr, * root; 
    int i; 

    root = NULL; 

    for(i=1;i<=10;i++) { 
     curr = (node *)malloc(sizeof(node)); 
     curr->left = curr->right = NULL; 
     curr->val = rand(); 
     insert(&root, curr); 
    } 

    printout(root); 
} 

爲什麼使用指針到指針？

Answer 1

因爲插入方法需要修改樹的根。

Answer 2

更精確的答案將是： 因爲函數需要更換某一領域（指針）

Answer 3

白板它的內容。或修改示例代碼來做到這一點：

for(i=1;i<=10;i++) { 
    curr = (node *)malloc(sizeof(node)); 
    curr->left = curr->right = NULL; 
    curr->val = rand(); 
    printf("before: %d\n", root); 
    insert(&root, curr); 
    printf("after: %d\n", root); 
} 

// printout(root); 

打印結果如下：
前：0
後：3871888
前：3871888
後：3871888
前：3871888
之後：3871888

這是爲什麼？

因爲它改變了你傳遞給它的指針。

如何插入工作：插入遍歷樹。首先訪問當前節點。然後左節點（通過遞歸）。然後右節點（通過遞歸）。如果涉及到一個空的節點（NULL），它會用item替換該節點。

爲此，它取消引用外部指針，並將指針「item」的值分配給該內部指針。

在一般情況下，指針就像int或char。您按值傳遞指針。如果取消引用它，則可以修改它指向的任何內容，但不能修改指針本身。如果傳遞指針指針，則可以更改內部指針，但外部指針不能。

這裏的一些指針示例代碼來啃：

#include <cstdio> 
#include <cstdlib> 

void some_func(int* value) 
{ 
    *value = 12; 
} 

int main(int argc, char* argv[]) 
{ 
    int a = 5; 
    printf("%d\n", a); // prints 5 
    some_func(&a); 
    printf("%d\n", a); // prints 12 

    int b = 7; 
    int* c = &b; 
    printf("%d\n", b); // prints 7 
    printf("%d\n", c); // prints 2029440 (some random memory address) 
    some_func(c); 
    printf("%d\n", b); // prints 12 
    printf("%d\n", c); // prints 2029440 (the same value as before) 
} 

和：

#include <cstdio> 
#include <cstdlib> 

void some_other_func(int** other_value) 
{ 
    *other_value = NULL; 
} 

int main(int argc, char* argv[]) 
{ 
    int b = 7; 
    int* c = &b; 

    printf("%d\n", c); // prints 4718288 (some random memory address) 
    some_other_func(&c); 
    printf("%d\n", c); // prints 0 
} 

最後但並非最不重要的：

#include <cstdio> 
#include <cstdlib> 

void some_third_func(int* third_value) 
{ 
    *third_value = 12; 
    int** lets_modify_third_value = &third_value; 
    *lets_modify_third_value = NULL; 
} 

int main(int argc, char* argv[]) 
{ 
    int b = 7; 
    int* c = &b; 

    printf("%d\n", b); // prints 7 
    printf("%d\n", c); // prints 1637380 (some random memory address) 
    some_third_func(c); 
    printf("%d\n", b); // prints 12 
    printf("%d\n", c); // prints 1637380 (same as before. Note that the pointer was passed by value, so "third_value" was just a COPY of the address) 
} 

Answer 4

的替代的 '在去'參數 - 一個返回值，需要在每個訪問級別進行額外的分配：

typedef node* node_ref; 

node_ref insert (node_ref tree, node_ref item) { 
    if (!tree) 
     return item; 

    if (item -> val < tree -> val) 
     tree -> left = insert (tree -> left, item); 
    else if (item -> val > tree -> val) 
     tree -> right = insert (tree -> right, item); 

    return tree; 
} 

... 
// in the loop 
    root = insert (root, curr); 

該方法（或與原始代碼）的另一個缺點是，無法告訴節點是否被插入;如果添加了一個返回值，以表明它，你不必泄漏curr如果不插入：

typedef node* node_ref; 

bool insert (node_ref *tree, node_ref item) { 
    if (!*tree) { 
     *tree = item; 
     return true; 
    } 

    if (item -> val < (*tree) -> val) 
     return insert (& (*tree) -> left, item); 

    if (item -> val > (*tree) -> val) 
     return insert (& (*tree) -> right, item); 

    return false; 
} 

... 
// in the loop 
for (int i = 1; i <= 10; ++i) { 
    node_ref curr = malloc (sizeof (node)); 

    curr -> left = curr -> right = NULL; 
    curr -> val = rand(); 

    if (! insert (&root, curr)) 
     free (curr); 
}