2

Cでのリンクリストスタックの実装に関連して、「ProgrammingInterviewsExposed」という本の次の段落を見ています。

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

これは、Cの有名なswap（）関数に似ています。

ケース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

したがって、リンクリストであるスタックから値をプッシュまたはポップするたびに、リンクリストの最上位または最初のノードが変更されます。したがって、ダブルポインタが必要です。

于 2012-11-05T21:26:26.137 に答える
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

ただし、2番目のバージョンは、スタックポインターにポインターを渡すため、それが変更されると、呼び出し元の関数のスタックポインターが変更されます。

于 2012-11-05T21:17:32.220 に答える
1

Cでは、すべてが値によって渡されます。たとえば、次の関数があるとします。 

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

このメソッドをメインで呼び出すと、渡されるポインターはNULLになりません（既にNULLでない限り）。ポインターのコピーが作成されてから関数に渡されるため、その値を変更する場合は、ダブルポインタを渡す必要があります： 

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

値を変更するスタックについても同じことが言えます。

于 2012-11-05T21:19:48.483 に答える
1

シングルポインタ署名を使用すると、次のようなコードを使用することを想像できます。

Element *myStack = NULL ;

.... bla bla bla ....

push(myStack, something);

次に、呼び出しで、スタックの古いヘッド要素がpushどこにあったかをスタック実装に通知しますが、実装が新しいヘッドの場所を通知する方法はありません。Cで渡されるパラメーターは常に値であるため、変数を変更することはできません。つまり、関数はの値が何であるかを通知されますが、呼び出し元の変数を変更する機会はありません。pushmyStackpushmyStack

動作させるには、プッシュプリミティブにローカル変数のアドレスを変更する必要があることを伝える必要があります。

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

また、myStackそれ自体の型Element *は、であるため、変数へのポインターの型はです。myStackElement **

于 2012-11-05T21:20:31.080 に答える