C中的链接堆栈Pop导致分段错误，但Push不行！

Question

我正在做一些简单的事情，所以希望这个问题可以很容易地回答。我使用gcc编译。推送工作非常好。问题是流行。每当我编译和运行它时，我都会遇到分段错误。

这里是流行音乐和推功能：

int push(stack *stk, int data) 
{ 
    stk->head = makeNode(data, stk->head); 
    stk->length += 1; 
    return data; 
} 

int pop(stack *stk) 
{ 
    //Returns popped item 
    //Returns -1 if stack length is zero 
    if (stk->length < 1) 
    { 
     printf("No items to pop."); 
     return -1; 
    } 
    int data = stk->head->value; 
    struct node *toBeFreed = stk->head; 
    stk->head = stk->head->ptr; 
    free(toBeFreed); 
    stk->length -= 1; 
    return data; 
} 

老实说，我不知道是什么问题，因为代码是相似的。我在推送函数中重新分配堆栈中的头部变量，但会导致pop函数中的错误。数据分配也给我一个seg故障。除了返回和堆栈长度赋值语句之外，几乎所有东西都会导致分段错误。你们能帮助我弄清楚吗？什么导致这些seg故障？

这里是整个程序：

#include <stdio.h> 
#include <stdlib.h> 
struct node 
{ 
    int value; 
    struct node *ptr; 
}; 

struct node *makeNode(int value, struct node *ptr) 
{ 
    struct node *newNode = malloc(sizeof(struct node)); 
    newNode->value = value; 
    newNode->ptr = ptr; 
    return ptr; 
} 

typedef struct stack 
{ 
    struct node *head; 
    int length; 
} stack; 

stack makeStack() 
{ 
    stack stk; 
    stk.head=NULL; 
    stk.length = 0; 
    return stk; 
} 

int push(stack *stk, int data) 
{ 
    stk->head = makeNode(data, stk->head); 
    stk->length += 1; 
    return data; 
} 

int pop(stack *stk) 
{ 
    if (stk->length < 1) 
    { 
     printf("No items to pop."); 
     return -1; 
    } 
    int data = stk->head->value; 
    struct node *toBeFreed = stk->head; 
    stk->head = stk->head->ptr; 
    free(toBeFreed); 
    stk->length -= 1; 
    return data; 
} 

int main() 
{ 
    stack s = makeStack(); 
    printf("Pushing ints one through five. Should display ints one through five on separate lines: \n"); 
    int i; 
    for (i = 1; i <= 5; i++) 
      printf("%d\n",push(&s, i)); 
    printf("Popping ten values. Should display ints one through five in reverse order on separate lines along with 5 error statements.\n"); 
    for (i = 0; i <= 10; i++) 
      printf("%d\n",pop(&s)); 
    return 0; 
} 

Answer 1

struct node *makeNode(int value, struct node *ptr) 
{ 
    struct node *newNode = malloc(sizeof(struct node)); 
    newNode->value = value; 
    newNode->ptr = ptr; 
    return ptr; 
} 

要返回newNode，不ptr。

你得到段错误的原因是由于makeNode中的错误，堆栈将保持为空，但size将增加到5，所以当你pop堆栈不知道它是空的，它试图解引用一个空指针。

Answer 2

在makeNode中，您正在创建一个新节点，并将该节点指向传入的值，然后返回值为的，而不是新节点。由于您传入stk->head（开头为NULL），因此每次推送都将始终创建一个指向NULL的新节点，然后返回NULL，因此stk->head不会像您期望的那样发生更改。当你弹出时，你试图访问NULL->ptr和NULL->value，这显然不起作用。

如果更改makeNode到：

struct node *makeNode(int value, struct node *ptr) 
{ 
    struct node *newNode = malloc(sizeof(struct node)); 
    newNode->value = value; 
    newNode->ptr = ptr; 
    return newNode; // pass back the new node 
} 

它会奏效。

Answer 3

我建议你在pop和push上添加NULL指针检查。 makeStack函数让我很生气，因为它返回一个局部变量。

另外，我建议以下变化：当你调用函数makeNode

struct stack * makeStack() 
{ 
    struct stack * p_stk = 0; 
    p_stk = (struct stack *) malloc(sizeof(struct stack); 
    if (p_stk) 
    { 
     p_stk->head=NULL; 
     p_stk->length = 0; 
    } 
    return p_stk; 
} 

或者

void makeStack(stuct stack * p_stack) 
{ 
// Initialize the stack ... 
} 

Answer 4

你的头指针不会改变。 您必须将头指向新创建的节点。

Answer 5

我不认为你在makeode函数中返回正确的节点。 尝试

ptr = newNode; 

返回之前。

Answer 6

sepp2k已经给出了正确的答案。所以我只是添加一些有用的建议。

一种可以帮助您在较大程序中发现这些问题的方法是名为valgrind的工具。例如，如果您编译：

$ gcc -Wall -Wextra -g linked_stack.c -o linked_stack 

，然后运行：

$ valgrind ./linked_stack 

你会得到下面的输出：

==1503== Invalid read of size 4 
==1503== at 0x80484C6: pop (linked_stack.c:62) 
==1503== by 0x8048584: main (linked_stack.c:79) 
==1503== Address 0x0 is not stack'd, malloc'd or (recently) free'd 
==1503== 
==1503== Process terminating with default action of signal 11 (SIGSEGV) 
==1503== Access not within mapped region at address 0x0 
==1503== at 0x80484C6: pop (linked_stack.c:62) 
==1503== by 0x8048584: main (linked_stack.c:79) 

此用途不同告诉你，上线62的声明：

int data = stk->head->value; 

正在尝试要使用值为0x0的无效指针。在这一点上，你只需要追溯并找出为什么该指针是无效的。

通过编译-g为调试符号提供的额外信息，然后在valgrind下运行，可以真正帮助您追踪更大程序中的这些问题。