2

我正在学习 C 并在我的 C 书中找到了一个基本的树实现：

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

struct tree_node {
  int data;
  struct tree_node *left_p, *right_p;
};

struct tree_node *t_search(struct tree_node *root, int v) {

  while (root) {
    printf("Looking for %d, looking at %d\n", v, root->data);
    if (root->data == v)
      return root;
    if (root->data > v)
      root = root->left_p;
    else
      root = root->right_p;
  }

  return 0;
}

int t_insert(struct tree_node **root, int v) {

  while (*root) {
    if ((*root)->data == v)
      return 1;
    if ((*root)->data > v)
      root = &((*root)->left_p);
    else
      root = &((*root)->right_p);
  }

  if ((*root = (struct tree_node *) malloc(sizeof(struct tree_node))) == 0)
    return 2;

  (*root)->data = v;
  (*root)->left_p = 0;
  (*root)->right_p = 0;

  return 0;
}

int main(void) {

  struct tree_node *tp, *root_p = 0;
  int i;

  t_insert(&root_p, 4);
  t_insert(&root_p, 2);
  t_insert(&root_p, 6);
  t_insert(&root_p, 1);
  t_insert(&root_p, 3);
  t_insert(&root_p, 4);
  t_insert(&root_p, 7);

  for (i = 0; i < 9; i++) {
    tp = t_search(root_p, i);
    if (tp)
      printf("%d found\n", i);
    else
      printf("%d not found\n", i);
  }

  return 0;
}

虽然代码看起来很简单，但我很难理解这个t_insert功能。为什么它需要 astruct tree_node **root而不是struct tree_node *root？t_serach几乎是相同的代码，但只使用指针而不是指针指针。也许另一个例子可以更好地解释这个问题。

对于它的价值：我来自 Java 背景。

注意：是的，我知道插入时树没有重新平衡。

4

5 回答 5

3

我们需要的一些东西：

#include <stdio.h>
struct thing {
   struct thing *next;
   int value;
   };

struct thing otherthing ={ NULL, 42};
struct thing something ={ &otherthing, 13};
int forty_two = 42;

    void do_the_int(int i);
    void do_the_intp(int *ip);
    void do_the_intpp(int **ipp);
    void do_the_structp(struct thing *p);
    void do_the_structpp(struct thing **pp);

函数可以更改其参数，但调用者不会看到结果，因此：

void do_the_int(int i) {
  i = 42;
}

实际上是一个空操作。要实际更改某些内容，该函数需要一个指向它的指针，例如：

void do_the_intp(int *ip) {
  *ip = 42;
}

现在，ip 指向的值实际上是由函数改变的。接下来，如果要更改指针，该函数将需要一个指向它的指针：指向指针的指针：

int forty_two = 42; // global (or static)
void do_the_intpp(int **ipp) {
  *ipp = &forty_two;
}

对于其他数据类型（除了 int），情况并没有什么不同：如果要更改结构，则函数将需要指向 struct的指针，如果函数需要更改指向 struct 的指针，则需要指向指向的指针结构。所以

void do_the_structp(struct thing *p) {
   p->value = 42;
}

实际上会改变struct 中的*p某些内容，并且

void do_the_structpp(struct thing **pp) {
   *pp = (*pp)->next;
}

实际上会更改位于的指针*pp。

现在，让我们称它们为：

int main(void) {
int zero=0
  , one=1
  , two=2;
int *the_p;
struct thing *tp, *cur;

  the_p = &two;
  tp = &something;

  printf("Before: zero=%d, one=%d, two=%d the_p=%p *the_p=%d\n"
        , zero, one, two, (void*) the_p,*the_p);
  for(cur=tp; cur; cur = cur->next) {
        printf("p=%p Next=%p Val=%d\n"
              , (void*) cur, (void*) cur->next, cur->value );
        }

  do_the_int(zero);
  do_the_intp(&one);
  do_the_intpp(&the_p);
  do_the_structp(tp);
  do_the_structpp( &tp);

  printf("After: zero=%d, one=%d, two=%d the_p=%p *the_p=%d\n"
        , zero, one, two, (void*) the_p,*the_p);
  for(cur=tp; cur; cur = cur->next) {
        printf("p=%p Next=%p Val=%d\n"
              , (void*) cur, (void*) cur->next, cur->value );
        }


  return 0;
}

输出：

Before: zero=0, one=1, two=2 the_p=0x7fff97a7db28 *the_p=2
p=0x601030 Next=0x601020 Val=13
p=0x601020 Next=(nil) Val=42
After: zero=0, one=42, two=2 the_p=0x601040 *the_p=42
p=0x601020 Next=(nil) Val=42
于 2013-04-07T10:44:22.597 回答
1

它传入一个双指针，因为它需要在进程中更改指针。树的所有元素都可以被认为是在调用 insert 时需要更改的指针。如果您不传入双指针，那么您实际上所做的是将指针作为局部变量复制到函数中，并且在插入函数退出时更改无效。如果我错了，请忽略我。

于 2013-04-07T09:45:09.143 回答
0

如果您只想读取指针指向的内容，则您的参数类型为foo*. 如果要更改指针指向的内容，则参数类型为foo *. 但是在那里，您希望能够更改您指向的内容。所以，你需要一个指向你的指针的指针，才能改变它的值。

在java中，任何以a为参数的方法TreeNode都等价于以a为参数的C函数tree_node*；因此，如果您有具有该签名的方法：

// Java code
static void treeInsert (TreeNode t);

在该方法中，您可以从 t 访问可以读取其当前状态的方法，您甚至可以修改 的状态t，即使您离开该方法，该状态也会更改。

但是，如果你正在做类似的事情

t = null;

一旦您离开该方法，这将不会产生影响。这意味着

// Java code
static void treeNull (TreeNode t) {
    t = null;  // Warning, local change only !
}

static void treeChange (TreeNode t) {
    t.changeState();
}

static void foo () {
    t = new TreeNode();
    t.treeChange();   // Ok, t has now an update state
    t.treeNull();     // Warning, t is not null here
}

你不能在java中拥有相当于双指针的东西，所以你不能让它工作。

在 C 中，您可以这样做：

// C code
void updateState(tree_node* t) {
    data = data + 1;  // This is nonsense, just to make the point
}

void localChangePointer(tree_node* t) {
    t = NULL;
}

void changePointer(tree_node** t) {
    free_and_clean(*t);
    *t = NULL;
}

void sillyStuff() {
    tree_node* t;
    // Initialize t
    ...

    updateState(t); // (*t).data changed
    localChangePointer(t);  // Warning : t is not null yet !
    changePointer(&t);      // This time, we gave the address of t, not t itself

    // Now t == NULL;
}
于 2013-04-07T09:57:12.820 回答
0

也许你会喜欢这样的变体：

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

typedef struct btree_node{
    int data;
    struct btree_node *left, *right;
} BTree;

// get tree leaf nearest to v
BTree *bt_get(BTree *root, int v){
    if(!root) return NULL;
    int D = root->data;
    if(D == v) return root;
    if(root->data > v) return root->left;
    else return root->right;
}

// find leaf with v or nearest to it (prev)
BTree *bt_search(BTree *root, int v, BTree **prev){
    if(!root){
        if(prev) *prev = NULL;
        return NULL;
    }
    BTree *p;
    do{
        p = root;
        root = bt_get(root, v);
    }while(root && root->data != v);
    if(prev) *prev = p;
    return root;
}

BTree *bt_create_leaf(int v){
    BTree *node = calloc(1, sizeof(BTree));
    if(!node) return NULL;
    node->data = v;
    return node;
}

// insert new leaf (or leave it as is, if exists)
// return root node
BTree *bt_insert(BTree *root, int v){
    BTree *closest, *node;
    node = bt_search(root, v, &closest);
    if(node) return node; // value exists
    if(!closest) // there's no values at all!
        return bt_create_leaf(v); // create root node
    // we have a closest node to our data, so create node and insert it:
    node = bt_create_leaf(v);
    if(!node) return NULL;
    int D = closest->data;
    if(D > v) // there's no left leaf of closest node, add our node there
        closest->left = node;
    else
        closest->right = node;
    return root;
}

int main(void){
    BTree *tp, *root_p = NULL;
    int i, ins[] = {4,2,6,1,3,4,7,14,0,12};
    for(i = 0; i < 10; i++)
        if(!(root_p = bt_insert(root_p, ins[i]))) err(1, "Malloc error"); // can't insert
    for(i = 0; i < 15; i++){
        tp = bt_search(root_p, i, NULL);
        printf("%d ", i);
        if(!tp) printf("not ");
        printf("found\n");
    }
    return 0;
}

// 我之前的回答错了，正确

于 2013-04-07T13:04:24.597 回答
0

这里将在没有双指针的情况下进行。我看不出有什么不同。

int t_insert(struct tree_node *root, int v) {
  while (root) {
    if (root->data == v)
      return 1;
    if (root->data > v)
      root = &(root->left_p);
    else
      root = &(root->right_p);
  }

  if ((root = (struct tree_node *) malloc(sizeof(struct tree_node))) == 0)
    return 2;

  root->data = v;
  root->left_p = 0;
  root->right_p = 0;

  return 0;
}
于 2013-04-08T03:13:32.677 回答