我已经尝试了一段时间,以使我的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;
}