鏈表棧用C

Question

我在看這本書的下段在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); 

有人能解釋，在不同的話，爲什麼我們需要在這裏使用一個雙指針？我對所提供的解釋有點不確定。

Answer 1

它類似於著名的互換在C

（）函數

案例1：

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

案例2：

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

，我們調用交換這樣的：

int x = 10; 
int y = 20; 

案例1：

swapFails(x, y); 

案例2：

swapOk(&x, &y); 

請記住，我們想改變x和y的值。對於更改數據類型的值，我們需要指針。把這個指向下一個級別。對於更改指針的值，我們需要雙指針。

對於堆棧使用鏈表： 如果按值分別爲10,20和30，它們存儲這樣的：

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

所以你看從堆棧，這是你推每次或流行值鏈接列表，鏈接列表的頂部或第一個節點發生更改。因此你需要雙重指針。

Answer 2

第一個版本將指針的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 

但是，第二個版本將指針傳遞給堆棧指針，所以當它改變時，它會改變調用函數中的堆棧指針。

Answer 3

在C一切是按值傳遞，讓我們說，我有這樣的功能：

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

如果調用主這種方法，你通過指針不爲NULL（除非它笏已經NULL）。因爲如果要修改它的價值指針的副本將它傳遞給function.So之前提出的，你必須通過一個雙指針：

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

同樣是有效的堆棧，您要修改其中的值。

Answer 4

隨着單指針簽名，你可以想像使用的代碼如下

Element *myStack = NULL ; 

.... bla bla bla .... 

push(myStack, something); 

然後在push調用你告訴堆棧實現中堆棧的老頭元素了，不過push的執行沒有辦法告訴你哪裏的頭是。它不能改變你的myStack變量，因爲在C中傳遞的參數總是按值 - 即push函數被告知什麼值恰好是myStack，但沒有機會改變調用者的變量。

爲了讓事情工作，你需要告訴推動原始局部變量的地址，它需要改變：

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

，自myStack本身的類型爲Element *，一個指針到myStack變量的類型爲Element **。