链表实现的堆栈错误

Question

我正在尝试使用链表实现来实现堆栈。它给我“分段错误”。请帮我找出错误。这是我的代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100

struct NODE {
    char word;
    struct NODE *next;
};

struct STACK {
    struct NODE *head;
    int size;
};

void pushStack(struct STACK *stack, char s);
void makeStack(struct STACK *stack, char *s);
void printStack(struct STACK *stack);

int main(){
    char *s;
    fgets(s,100,stdin);
    struct STACK stack;
    stack.head = NULL;
    makeStack(&stack,s);
    printStack(&stack);
    return 0;
}

void pushStack(struct STACK *stack, char s){
    struct NODE temp;
    temp.word = s;
    temp.next = stack->head;
    stack->head = &temp;
}

void makeStack(struct STACK *stack, char *s){
    char temp[MAX];
    strcpy(temp,s);
    for(int i=0; i<MAX; i++){
        if(temp[i]=='[=10=]') break;
        pushStack(stack,temp[i]);
    }
}

void printStack(struct STACK *stack){
    struct NODE *trav = stack->head;
    while (trav != NULL){
        printf("%c", trav->word);
        trav = trav->next; 
    }
}

MAX=100 是我对字符串输入的限制。我还没有添加增加大小，因为我现在只是忽略了大小的增加。在我完善实施之前

Answer 1

在 main 中，s 指针未初始化，它指向任何地方。

int main(){
   char *s;   // <<< this is wrong, you want 'char s[100]' instead
   fgets(s,100,stdin);
   ...

然而，最安全的选择是：

 int main(){
   char s[100];                 // declare array of 100 chars
   fgets(s, sizeof(s), stdin);  // sizeof(s) is the actual size of s (100 here)
   ...

这也是错误的：您存储了指向局部变量 temp 的指针，但是一旦您从 pushStask 函数中 return，该变量就不再存在。

void pushStack(struct STACK* stack, char s) {
  struct NODE temp;
  temp.word = s;
  temp.next = stack->head;
  stack->head = &temp;
}

相反，您需要像这样创建一个新的 struct NODE：

void pushStack(struct STACK* stack, char s) {
  struct NODE* temp = malloc(sizeof *temp);
  temp->word = s;
  temp->next = stack->head;
  stack->head = temp;
}

你可以写 sizeof(struct NODE) 而不是 malloc(sizeof *temp)，它是一样的，但是它不那么简单，因为你可能会错误地写 sizeof(struct STACK)，这样编译会很好，但是分配的内存是错误的。

另一个问题：你没有给struct STACK的size字段赋值，现在这不是问题，但以后可能会成为问题。

Answer 2

您的堆栈实现有几个缺点。

第一个是您正在使用具有不确定值的指针来读取字符串

char *s;
fgets(s,100,stdin);

因此 fgets 的调用调用了未定义的行为。

此外还使用了一个幻数100。

您需要分配一个字符数组并使用它来读取字符串。

#define MAX 100

//...

char s[MAX];
fgets( s, MAX, stdin );

请注意类型 char 的对象的名称 word 令人困惑

struct NODE {
    char word;
    struct NODE *next;
};

你可以像这样定义结构

struct NODE {
    char c;
    struct NODE *next;
};

或

struct NODE {
    char item;
    struct NODE *next;
};

而不是像你那样将声明和初始化分开

struct STACK stack;
stack.head = NULL;

忘记初始化数据成员size（顺便说一句应该有一个无符号整数类型，例如size_t）你可以只写例如

struct STACK stack = { NULL, 0 };

或

struct STACK stack = { .head = NULL, .size = 0 };

在函数的声明中 makeStack 第二个参数应该有限定符 const 因为传递的字符串在函数中没有被改变。由于内存分配通常会失败，因此该函数应报告字符串的所有字符是否都已成功推送。所以函数声明应该是这样的

int makeStack( struct STACK *stack, const char *s );

在函数内声明局部数组temp没有意义

void makeStack(struct STACK *stack, char *s){
    char temp[MAX];
    //...

使用索引变量i是多余的。此外，函数 fgets 可以将换行符 '\n' 附加到您不应压入堆栈的输入字符串。

函数可以这样定义

int makeStack( struct STACK *stack, const char *s )
{
    int success = 1;

    for ( ; *s && success; ++s )
    {
        if ( *s != '\n' )
        {
            success = pushStack( stack, *s );
        }
    }

    return success;
}

另一种方法是在将输入字符串传递给函数 makeStack.

之前从输入字符串中删除换行符

例如

s[ strcspn( s, "\n" ) ] = '[=21=]';
makeStack( &stack, s );

如果由用户负责是否将新行字符压入堆栈，那么函数makeStack可以简化

int makeStack( struct STACK *stack, const char *s )
{
    int success = 1;

    for ( ; *s && success; ++s )
    {
        success = pushStack( stack, *s );
    }

    return success;
}

相应的函数pushStack也需要重新定义

对于初学者来说，它应该动态分配一个新节点。否则，您将尝试添加函数的本地节点，并且在退出函数后将不再存在，这将再次导致未定义的行为。

函数pushStack可以这样定义。

int pushStack( struct STACK *stack, char c )
{
    struct NODE *temp = malloc( sizeof( struct NODE ) );
    int success = temp != NULL;

    if ( success )
    {
        temp->word = c;
        temp->next = stack->head;

        stack->head = temp;
        ++stack->size;
    }

    return success;
}

函数的参数 printStack 应该有限定符 const 因为函数中的堆栈本身没有被改变。

函数至少可以这样定义

void printStack( const struct STACK *stack )
{
    for ( const struct NODE *trav = stack->head; trav != NULL; trav = trav->next )
    {
        printf( "%c", trav->word );
    }
}

链表实现的堆栈错误

Error in stack with linked list implementation

c

implementation

stack

struct

data-structures