为什么在这个prog中使用指针指针？
以下程序显示了如何在C程序中构建二叉树。 它使用动态内存分配，指针和递归。 二叉树是一种非常有用的数据结构，因为它允许在排序列表中进行有效的插入，搜索和删除。 因此，树本质上是递归定义的结构，递归编程是处理它的自然而有效的方式。
tree empty node left-branch right-branch left-branch tree right-branch tree 这是代码：
#include #include 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->valval) 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;ileft = curr->right = NULL; curr->val = rand(); insert(&root, curr); } printout(root); }
为什么使用指针指针？
因为insert方法需要修改树的根。
白板吧。 或者修改示例代码以执行此操作：
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”的值赋给该内部指针。
在一般情况下，指针就像int或char。 您按值传递指针。 如果取消引用它，您可以修改它指向的内容，但不能修改指针本身。 如果传递指针指针，则可以更改内部指针，但外部指针不能。
这里有一些咀嚼的指针示例代码：
#include #include 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 #include 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 #include 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) }
一个更精确的答案是：因为函数需要替换给定字段的内容（指针）
“输入”参数的替代 – 返回值，需要在每个访问级别中进行额外分配：
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 ); }