c - 链表栈实现中的双指针

Question

最近在看一本书，这是关于在链表中实现堆栈的解释。下面是解释:

typedef struct Element { 
    struct Element *next; 
    void *data;
} Element;

push 和 pop 对应的原型(prototype)如下:

void push( Element *stack, void *data );
void *pop( Element *stack );

现在考虑在正确的功能和错误处理方面这些例程中发生了什么。 这两个操作都会更改列表的第一个元素。必须修改调用例程的堆栈指针以反射(reflect)此更改，但您对传递给这些函数的指针所做的任何更改都不会传播回调用例程。您可以通过让两个例程都采用指向堆栈指针的指针来解决此问题。这样，您可以更改调用例程的指针，使其继续指向列表的第一个元素。实现此更改会产生以下结果:

void push( Element **stack, void *data );
void *pop( Element **stack );

不过，我想知道的是，栈有什么必要放双指针的？我了解双指针的概念，但是，当使用创建新节点时 Element *node1 = (Element *) malloc (sizeof(Element));，我们已经有了指向节点的指针。为什么不直接发送这个指针本身而不是使用双指针？

Answer 1

由于 指针 和按引用传递 概念的常见混淆，这有点令人困惑。

让我们看一下原始的push 函数。 stack 参数表示指向堆栈开头的指针。该指针由调用者提供。如果堆栈的开头需要修改，push 函数将无法执行此操作，因为它是按值传递的，即在函数体内它是一个原件的副本。 pop 也是如此。

举个例子最容易理解。假设堆栈的开头位于地址 0x1234。当调用 push 时，value 0x1234 由调用者传递给它。 push 可以用这个值做任何它想做的事，但它不会改变原始指针的数据，而且改变也不会反射(reflect)在调用者上下文中。

为什么不发送您在 push 中创建的 node1 指针:Element *node1 = (Element *) malloc (sizeof(Element)); ？这正是你应该做的，但你仍然需要双指针:

void push( Element **stack, void *data )
{
    Element *node1 = (Element *) malloc (sizeof(Element));
    node1->data = data;
    node1->next = *stack;
    *stack = node1;
}

如果您尝试在没有双指针的情况下实现此目的，调用者将看不到更改并将保留旧的堆栈指针:

void push( Element *stack, void *data )
{
    Element *node1 = (Element *) malloc (sizeof(Element));
    node1->data = data;
    node1->next = stack;
    stack = node1;         //The data structure was updated but caller won't see it!
}