c - C 语言栈的 Pop() 函数

Question

我已经尝试了一段时间让我的 pop() 函数正常工作，但一些奇怪的原因是它所做的一切都是......什么也没有。这是我的堆栈声明和函数。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

这将有助于了解如何将项目插入堆栈。如果您确实首先调用 pop 而没有 push，那么它就不会应该执行任何操作，是吗？

这让我很紧张:

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

您将 prev 设置为 *stack，如果 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，但如果您不想节省周期，则可以忽略它。

编辑

我对这段代码感到紧张是对的。

所以这基本上是发生的事情 - 当堆栈中只有一项时，您释放列表的头部，但不更新列表指针的值( *stack 在原始代码中，*l 在最新编辑中)。 main 中的 stack 变量的值未更改，现在它无效 - 该地址处的内存不再分配。因此，下次调用 push 时，它会发现 *l 不是 NULL，并尝试向下遍历(不存在的)列表。

此时行为未定义；从字面上看，任何事情都可能发生。在我的系统上，第一次push后，stack的值为0x501010。我执行了一次pop，它释放该内存，但不会更改stack的值。在下一次 push 时，*l 不是 NULL，因此我将 (*l)->next 设置为无论 malloc 返回什么，在我的例子中又是......0x501010。因此，*l 为 0x501010，(*l)->next 为 0x501010。如果我尝试推送另一个项目，我会陷入无限循环(p == p->next)。

要解决此问题，您需要在释放列表指针后将其设置为NULL:

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