2

我最近在读一本书，这是在链接列表中实现堆栈的解释。以下是解释：

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

push 和 pop 对应的原型如下：

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

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

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

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

4

2 回答 2

0

因为您没有独立的 Stack 对象，所以每次更改堆栈中的顶部节点时，对该堆栈的主要引用都需要更改以用于使用它的所有内容。这就是为什么需要双指针的原因——因为旧的栈顶不再有效。

如果您创建了一个顶级堆栈对象，它有一个指向元素的指针，可能还有一些其他数据，如元素计数，那么您将能够将其作为单个指针发送到 push/pop，因为该对象/结构将保持不变，只有里面的数据会改变。

// pseudocode
struct Stack {
  Element * top = NULL;
  int size = 0;
}

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

function push(Stack * stack, void * data) {
  Element * element = new Element(data);
  element->next = stack->top;
  stack->top = element;
  size++;
}

// pop left as an exercise to the reader.. :)

int main(void*) {
    Stack * stack = new Stack;
    push(stack, "foo"); <== no need for double pointer
    pop(stack); 
    printf("%d\n", stack->size);
}
于 2013-05-04T06:25:27.597 回答
0

pointers由于和的概念经常混淆，这有点令人困惑passing by reference。

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

举个例子最容易理解。假设堆栈的开头位于 address 0x1234。当push被调用时，调用者将值 0x1234传递给它。push可以用这个值做任何它想做的事情，但它不会改变原始指针的数据，并且改变不会反映在调用者上下文中。

为什么不发送node1您在push:中创建的指针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!
}
于 2013-05-04T06:33:29.670 回答