1

我最近一直在研究链表和树。但我不确定何时将函数声明为：

preorder(struct node* root); 
or
preorder(struct node** root);

当两者的工作方式完全相同时。更准确地说，我什么时候必须将我的函数设计为双指针和单指针。

谢谢。

PS：在链表中插入节点需要有双指针，如：

insert(struct node** root,int value);

除非根节点被定义为全局值。虽然预购使用单个指针效果很好。如果有人可以以此为例进行解释，那将非常有帮助。

4

5 回答 5

5

这取决于做什么preorder()。如果它在不修改列表/树的情况下打印一些东西，你只需要一个指针。如果有可能必须替换根，则需要一个双指针。

这是因为在 C 中参数是按值传递的。如果将原始变量的副本传递给您的函数，则无法修改原始变量：

int inc(int x)
{
    x = x + 1; // this will never work
}

为了解决这个问题，您可以传入该参数的地址（指向它的指针），而不是传入参数。然后该函数可以取消引用指针并修改它指向的值。

// usage: inc(&x) where x is an int
int inc(int *ptr)
{
    *ptr = *ptr + 1; // this will work
}

使用您的列表/树，您已经在使用指针。这使您可以访问和修改指向的对象（例如获取/设置next根的成员），但不允许您修改指针本身（例如用不同的节点替换根）。为此，需要引入另一个级别，即指向节点的指针。

于 2013-09-29T05:54:02.177 回答
2

这有点令人困惑，但我会试一试，也许我的解释方式会对某人有意义:)

函数范围内的每个变量都以标准方式定义，本质上是..（变量类型）（变量名）。无论是：

int foo; // an int called foo

或者

char *bar; // a char * called bar

或者

struct xyz *blah; // a struct xyz * called blah

当您将它们作为参数传递给另一个函数时，您对待foo,bar和的方式是相同的。blah如果您希望被调用的函数只查看或使用变量，您可以按原样（按值）传递它们，从而创建值的副本（int，或 char 的地址，或 a 的地址struct xyz） . 因此，如果您更改 int 的值或被调用struct xyz函数中的地址，则只会更改原始变量的本地副本。

如果您希望被调用函数实际更改原始变量的值（增加 foo、bar 的 malloc 内存，或更改列表 blah 指向的哪个元素），您需要告诉被调用函数 WHERE 进行更改（通过引用传递它们）这导致被调用的函数被声明为f(int *foo)orf(char **bar)或f(struct xyz **blah)。

人们陷入了间接级别，但是当您调用另一个函数时，真正重要的是您在使用或更改本地范围内的变量方面的意图。

于 2013-09-29T06:57:12.553 回答
2

preorder(struct node** root);

在这里传递 的地址root，因为您可能希望使用该函数对其进行更新。

preorder(struct node* root);

在这里你只是简单的使用root横向的数据结构，而不用修改root.

于 2013-09-29T05:56:16.233 回答
1

当你想改变传递给例程的东西时，你传递一个指针。你的困惑出现了，因为这个东西也是一个指针。

因此，如果您想将指针传递给例程，并且还想（可能）修改指针本身，请使用双指针。

如果您想将一个指针传递给一个例程，但您想要做的就是更改或查询指针指向的内容以使用单个指针。

这就是区别，您是要更改指针还是要访问指针指向的内容。

于 2013-09-29T07:56:43.630 回答
0

由于 question 被标记为 C 和 C++，因此从这个角度看一下不同之处。这个答案不涉及 C++ 容器类或智能指针，这在 C++ 代码中通常应该是首选。下面是 4 种情况，两种可以修改调用者的结构和调用者的指针，两种只能修改给定结构的内容。

C++修改指针

当您希望函数修改指针并将指针值返回给 C++ 中的调用者时，您可以使用对指针的引用来执行此操作：

void clearNode(struct node *&n){
    n->field = 0; // modify caller's struct
    n = nullptr; // set caller's pointer to NULL (C++11)
}
...
struct node n; // value
struct node *np = &n; // pointer to node
clearNode(np); // OK, np becomes null, n.field becomes 0
clearNode(&np); // will not compile, &np is not right type
clearNode(&n); // will not compile, &n is not lvalue

C修改指针

在 C 中，相同的代码将是这样的（也适用于 C++，尽管上面的版本会更好更干净）：

void clearNode(struct node **n){
    (*n)->field = 0; // modify caller's struct
    *n = NULL; // set caller's pointer to NULL
}
...
struct node n; // value
struct node *np = &n; // pointer to node
clearNode(np); // will not compile, np is not right type
clearNode(&np); // OK, np becomes NULL, n.field becomes 0
clearNode(&n); // will not compile, &n is not of right type

C只修改结构

但是如果我们只用指针编写相同的代码，它的工作方式会有点不同：

void clearNode(struct node *n){
    n->field = 0; // modify caller's struct
    n = NULL; // change local parameter, which in this case has no effect anywhere
}
...
struct node n; // value
struct node *np = &n; // pointer to node
clearNode(np); // OK, except np is not modified, n.field becomes NULL
clearNode(&np); // will not compile, &np is not of right type
clearNode(&n); // OK, n.field becomes NULL

C++ 只修改结构

最后，C++ 中的相同代码这样会更干净：

void clearNode(struct node &n){
    n.field = 0; // modify caller's struct
    // no pointer, nothing to set to NULL
}
...
struct node n; // value
struct node *np = &n; // pointer to node
clearNode(np); // will not compile, np is not of right type
clearNode(&np); // will not compile, &np is not of right type
clearNode(&n); // will not compile, &n is not of right type
// these work, n.field becomes 0:
clearnode(n);
clearnode(*np);

你的问题

因此，从上面可以看出，如果您需要修改调用者指针，请将指针传递给指针（C 和 C++）或引用指针（C++）。这是有代价的：你必须总是传递一个可修改的指针变量，而且双间接也有很小的开销。两者的语法如上所示。

如果您不需要修改调用者指针，但需要修改 struct 内容，请将指针（C 和 C++）或引用（C++）传递给 struct。两者的语法如上所示。

第三种情况，当您不需要修改任何内容时，上面没有介绍，但有 3 个基本替代方案：按值传递（C 和 C++，干净的语法但复制整个结构），通过指向 const 的指针传递（C 和 C++，有点丑陋的语法，但只传递地址）或通过 const 引用传递（仅限 C++，语法简洁，只传递地址）。

总而言之，当您需要修改调用者的指针时，使用双指针（或对指针的引用）。否则，传递一个指针（或引用），如果 struct 很小，甚至传递一个值。

于 2013-09-29T15:34:39.953 回答