CでのスタックのPop（）関数

Question

私はpop（）関数を正しく動作させるためにしばらく時間をかけてきましたが、何か奇妙な理由は何もありません。 ここに私のスタック宣言& function.L.Eがあります。私はまた、プッシュ機能を追加しました。

typedef struct node 
{ 
    int v; 
    struct node* next; 
}Node; 

void push(Node **l,int val) 
{ 
    Node *p = (Node *)calloc(1,sizeof(Node)); 
    p->v = val; 
    Node *aux=*l; 
    if(aux == NULL) 
    { 
     *l = p; 
     return; 
    } 
    while(aux->next != NULL) 
     aux = aux->next; 
    aux->next = p; 
} 

void pop(Node **l) 
{ 
    if(*l != NULL) 
    { 
    Node *aux,*prev; 
    prev = *l; 
    aux = prev->next; 
    if(aux == NULL) 
     free(prev); 
    else 
    { 
     while(aux->next != NULL) 
     { 
     prev = aux; 
     aux = aux->next; 
     } 
     prev->next = NULL; 
     free(aux); 
    } 
    } 
} 

と私はそれはあなたがスタックにアイテムをプッシュする方法を確認するために役立つだろう

Node *stack = NULL; 
pop(&stack); 

Answer 1

でそれを呼び出します。最初にpushがない場合popと呼んでいる場合は、とは思わないでしょうか。は何ですか？

このビットは、私が神経質になります：

あなたは*stackからprevを設定し、何もprevを以下のなかった場合、あなたはそれを解放します。 prev == *stack以降、*stackも解放されているため、ポインタはで無効になります。です。呼び出し元のポインタにアクセスしようとすると、未定義動作が呼び出されます。

リストの先頭をスタックの先頭にしているようです。

bool push(Node **l, int val) 
{ 
    Node *p = calloc(1, sizeof *p); 
    if (p) 
    { 
    p->v = val; 
    p->next = *l; // set p to point to the current head of the list 
    *l = p;   // make p the new head of the list 
    } 
    return p != NULL; // will return false if the calloc (and by extenion, 
}     // the push operation) fails. 

bool pop(Node **l, int *v) 
{ 
    Node *p = *l;  // p points to head of list 
    if (!p) 
    return false; 

    *v = p->val;  // get value in current node 
    *l = p->next; // make the next element the new list head 
    p->next = NULL; // sever the old list head 
    free(p);  // and deallocate it 

    return true; 
} 

：私は今あなたがリストに ヘッドスタックの先頭を作る場合、あなたのプッシュとポップは、以下のように見えるようにあなたの人生が ずっとに簡単になりますことを伝えるつもりです

リストのトラバーサルがないため、現在および前のノードを追跡する必要はありません。あなたが気にするのはヘッドノードだけです。ステートメントp->next = NULL;は、その後すぐにpを解放するため、厳密には必要ありません。 がリストから削除されていることが明らかになったので、私はそれが好きです。しかし、サイクルをスペアしたくない場合は、省略することができます。p

編集

私はそのコード神経質であることが正しかったです。 *l、あなたがスタックに正確に一つのアイテムを持っているとき、あなたはリストの先頭、を解放いますが、元のコードにリストポインタ（*stackの値を更新しない - だからここ

は何が起こっているのか、基本的です最新の編集で）。 mainのstack変数の値は変更されていません。現在はが無効です。 - そのアドレスのメモリは割り当てられなくなりました。したがって、次にpushと呼ぶと、*lはNULLではないとみなされ、（存在しない）リストを横断しようとします。

この時点での動作は未定義です。文字通り何かが起こる可能性があります。最初のpushの後の私のシステムでは、stackの値は0x501010です。私はpopを実行しますが、そのメモリはfreeですが、stackの値は変更されません。次のpushでは、*lはNULLではないので、私は(*l)->nextをmallocが返すものに設定します。これは私の場合です...0x501010を再度入力します。従って*lは0x501010であり、(*l)->nextは0x501010である。別のアイテムをプッシュしようとすると、無限ループ（p == p->next）になります。この問題を解決するには

、あなたがfreeした後NULLにそれをリストポインタを設定する必要があります。

Node *aux,*prev; 
prev = *l; 
aux = prev->next; 
if(aux == NULL) 
{ 
    free(prev); 
    *l = NULL; 
    return; 
}