2

我正在查看“Programming Interviews Exposed”一书中的以下段落，参考了 C 中链表堆栈的实现：

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

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

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

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

有人可以用不同的语言解释为什么我们需要在这里使用双指针吗？我对所提供的解释有点不确定。

4

4 回答 4

3

It is similar to the famous swap() function in C.

Case 1:

void swapFails(int x, int y) {
    int temp = x;
    x = y;
    y = temp;
}

Case 2:

void swapOk(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

and we invoke swap like this:

int x = 10;
int y = 20;

Case 1:

swapFails(x, y);

Case 2:

swapOk(&x, &y);

Remember, we wanted to CHANGE the values of x and y. For CHANGING values of a datatype, we need pointers. Take this to the next level for pointers. For CHANGING values of a pointer, we would need double pointers.

For Stack using linked list: If you push values 10, 20 and 30, they are stored like this:

top --- bottom
30 -> 20 -> 10

So you see every time you push or pop values from the stack, which is a linked list, the top or the first node of the linked list changes. Hence you need double pointers.

于 2012-11-05T21:26:26.137 回答
1

使用单指针签名，您可以想象使用如下代码

Element *myStack = NULL ;

.... bla bla bla ....

push(myStack, something);

然后在push调用中，您将告诉堆栈实现堆栈的旧头元素在哪里，但是实现push无法告诉您新头在哪里。它不能更改您的myStack变量，因为在 C 中传递的参数始终是按值传递的——即，push函数被告知恰好是什么值，myStack但没有机会更改调用者的变量。

为了使事情正常工作，您需要告诉 push 原语它需要更改的局部变量的地址：

....
push(&myStack, something);

并且由于myStack它本身具有 type Element *，指向myStack变量的指针具有type Element **。

于 2012-11-05T21:20:31.080 回答
1

第一个版本发送一个copy指针，如果它在函数内部被改变，那么本地副本只会被改变，当函数返回给调用者时，调用者仍然有一个指向旧地址的指针。

Element *stack =...
push (stack)
void push( Element *stack, void *data ) {
  stack = ... // this changes the local pointer allocated on the function's stack
}
//call returns
stack //still points to old memory

然而，第二个版本将一个指针传递给堆栈指针，因此当它更改时，它会更改调用函数中的堆栈指针。

于 2012-11-05T21:17:32.220 回答
1

In C everything is passed by value, let's say that I have this function: 

void foo(void* ptr)
{
    ptr=NULL;
}

If you call this method in the main, the pointer that you pass will not be NULL (unless it wat already NULL).Because a copy of the pointer is made before passing it to the function.So if you want to modify it's value, you have to pass a double pointer: 

void foo(void** ptr)
{
    *ptr=NULL;
}

The same is valid for the stack, of which you want to modify the value.

于 2012-11-05T21:19:48.483 回答