c - 使用列表进行堆栈操作

Question

我正在尝试使用链表在 C 上编写堆栈。我的 CreateStack 函数有问题。当我创建一个堆栈时，一切看起来都很好，但当我尝试创建另一个堆栈时，程序就会崩溃。这是我的代码的一部分

#include <stdio.h>
#include <stdlib.h>

struct StackData{
    int data;
    struct StackData* prev;
    struct StackPoint* point;
};

struct StackPoint{
    struct StackData* basePointer;
    struct StackData* stackPointer;
    char exists;
};

int CreateNewStack(struct StackData** newPointer){
    if((*newPointer)->point->exists=='Y') //i'm trying to check whether the list with the same adress has been already created and i think this is the part which causes error
        return 1; //if error
    else{
        (*newPointer)=(struct StackData*)malloc(sizeof(struct StackData));
        (*newPointer)->data=NULL;
        (*newPointer)->prev=NULL;
        (*newPointer)->point=(struct StackPoint*)malloc(sizeof(struct StackPoint));
        (*newPointer)->point->basePointer=newPointer;
        (*newPointer)->point->stackPointer=newPointer;
        (*newPointer)->point->exists='Y';
        return 0;
    }
}

int main()
{
    struct StackData *pointeris, *temp;
    int state;
    state=CreateNewStack(&pointeris);  //state 0

    state=CreateNewStack(&pointeris);  //state 1


    CreateNewStack(&temp);            //crash
    return 0;
}

Answer 1

此代码有编译器警告。

test.c:21:28: warning: incompatible pointer to integer conversion assigning to 'int' from 'void *'
      [-Wint-conversion]
        (*newPointer)->data=NULL;
                           ^~~~~
test.c:24:42: warning: incompatible pointer types assigning to 'struct StackData *' from
      'struct StackData **'; dereference with * [-Wincompatible-pointer-types]
        (*newPointer)->point->basePointer=newPointer;
                                         ^~~~~~~~~~~
                                          *
test.c:25:43: warning: incompatible pointer types assigning to 'struct StackData *' from
      'struct StackData **'; dereference with * [-Wincompatible-pointer-types]
        (*newPointer)->point->stackPointer=newPointer;
                                          ^~~~~~~~~~~
                                           *

修复这些问题后，最直接的问题是这一行:

if((*newPointer)->point->exists=='Y')

*newPointer 可能为 null。 *newPointer->point 可能是垃圾。 *newPointer->point->exists 可能是垃圾。

问题的一部分是 CreateNewStack 实际上是“如果堆栈尚不存在，则可能创建一个新堆栈”。如果将“创建新堆栈”与“如果尚不存在则创建新堆栈”分开，您的代码将会简单得多。事实上，每个结构体都应该有自己的创建和销毁函数。

我还冒昧地为您的结构添加了 typedef。我已从 malloc 切换到 calloc，以确保分配的结构在创建时清零。这意味着即使您忘记初始化每个成员，结构体的成员中也永远不会有任何垃圾。

typedef struct StackData {
    int data;
    struct StackData* prev;
    struct StackPoint* point;
} StackData;

typedef struct StackPoint {
    struct StackData* basePointer;
    struct StackData* stackPointer;
    char exists;
} StackPoint;

StackPoint *CreateStackPoint() {
    StackPoint *point = calloc(1, sizeof(StackPoint));

    point->exists = 'Y';

    return point;
}

StackData *CreateStackData() {
    StackData *data = calloc(1, sizeof(StackData));

    data->point = CreateStackPoint();
    data->point->basePointer  = data;
    data->point->stackPointer = data;

    return data;
}

现在，CreateNewStack 变为 MaybeCreateStackData，并且更加简单。

int MaybeCreateStackData(StackData **maybeStack_p) {
    if( maybeStack_p == NULL ) {
        fprintf(stderr, "The stack double pointer cannot be null");
        exit(1);
    }

    StackData *maybeStack = *maybeStack_p;

    if( maybeStack && maybeStack->point && maybeStack->point->exists == 'Y' ) {
        return 1;
    }
    else {
        *maybeStack_p = CreateStackData();
        return 0;
    }
}

老实说，这个计划过于复杂。在 C 语言中，很难知道指针何时已正确初始化，而不是仅指向随机内存。您的 exists 成员尝试解决这个问题，但垃圾仍然可能出现 Y。

相反，我会放弃整个想法，让调用者决定他们是否有有效的结构。既然您已经有了可靠的初始化函数，那么有人拥有错误初始化的指针的可能性就小了。