我已经尝试了一段时间,以使我的pop()函数正常工作,但奇怪的原因是……什么也没有。
这是我的堆栈声明和函数。我还添加了推送功能。

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);

最佳答案

这将有助于了解如何将项目推入堆栈。如果您真的是在没有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中的stack变量的值保持不变,现在是无效的-该地址处的内存不再分配。因此,下次调用main时,它会看到push不是*l,并尝试遍历(不存在)列表。

在这一点上,行为是不确定的。实际上什么都可能发生。在我的系统上,第一个NULL之后,push的值为stack。我执行一个0x501010,该pop是该内存,但是不更改free的值。在下一个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;
}

10-06 05:24
查看更多