C中的通用堆栈

Question

我试图使用void指针在C中实现一个通用堆栈，并试图通过将所有责任委托给函数调用方并避免更复杂的方法来保持它尽可能简单。

stack.h

#ifndef STACK_H
#define STACK_H

#include <stdbool.h>

struct Stack {
    void *data;
    struct Stack *next;
};

/*
 * We declare a pointer to a Stack structure thereby making use of incomplete
 * types. Clients that pull in stack.h will be able to declare variables of type
 * pstack which are pointers to pointers to Stack structures.
 * */
typedef struct Stack *pstack;

bool is_empty(pstack *s);
void make_empty(pstack *s);
void push(struct Stack **s, void *new_num);
void *pop(pstack *s);

#endif /* STACK_H */

stack.c

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

bool is_empty(pstack *s) { return !s; }

void make_empty(pstack *s)
{
    if (!is_empty(s))
        pop(s);
}

void *pop(pstack *s)
{
    struct Stack *tmp;
    void *i;

    if (is_empty(s))
        exit(EXIT_FAILURE);

    tmp = *s;
    i = (*s)->data;
    *s = (*s)->next;
    free(tmp);
    return i;
}

void push(struct Stack **s, void *new_num)
{
    struct Stack *new_node = malloc(sizeof(struct Stack));
    if (!new_node)
        exit(EXIT_FAILURE);

    new_node->data = new_num;
    new_node->next = *s;
    *s = new_node;
}

stackclient.c

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

int main(void)
{
    pstack s1;
    void *n;
    int i = 1;
    int j = 2;

    push(&s1, &i);
    push(&s1, &j);

    n = pop(&s1);
    printf("Popped %d from s1\n", *((int *)n));
    n = pop(&s1);
    printf("Popped %d from s1\n", *((int *)n));

    exit(EXIT_SUCCESS);
}

Answer 1

/*
 * We declare a pointer to a Stack structure thereby making use of incomplete
 * types. Clients that pull in stack.h will be able to declare variables of type
 * pstack which are pointers to pointers to Stack structures.
 * */

这里有几个问题。首先，pstack类型的变量只是指向Stack结构的指针，而不是注释声明中指向指针的指针。其次，您没有按预期使用不完全类型:客户端仍然看到struct Stack的实现，实现中的任何更改都会导致客户端代码无缘无故地重新编译。处理它的一个标准方法是离开。

typedef struct Stack stack;

在头文件stack.h中，并声明

struct Stack {
    ...
};

在实现文件stack.c中。

Answer 2

这不是一个有效的程序，您有几个bug。另外，程序设计不是实现不透明类型的正确方法。

程序设计

• 不透明类型不应该是指向指针类型的typedef:ed。通常，将指针隐藏在类型防御后面是非常糟糕的做法，因为它严重降低了可读性。相反，类型为不透明类型为不完整的结构。typedef struct stack_t stack_t;
• 不透明类型意味着结构定义不应该对调用者可见，所以它不应该在“公共”头文件中！而是在“私有”c文件中。
• 真正的不透明类型意味着ADT负责分配所有对象，因为调用方不能创建不完整类型的对象。因此，您需要一个create()函数和一个delete()函数来创建/删除stack_t类型的对象。
• 您可能希望以某种方式跟踪数据的大小，例如，在结构中使用数据大小成员。
• 函数中间的exit(EXIT_FAILURE);是非常值得怀疑的实践。相反，您应该使用返回的错误代码来实现您的函数，并让调用方担心要采取的操作。

Bugs

• make_empty()不会像人们通过读取堆栈名称时所想的那样，清空堆栈。if(!is_empty(s))必须是while (!is_empty(s))。
• 这将导致下一个错误，pop不会修改指针(它不能)，因此空指针永远不会设置为NULL。
• 在某个地方，第一个/最后一个指针必须设置为空。

风格细节

• 小问题:由于struct标记和typedefs位于不同的作用域(名称空间)，所以您可以使用相同的名称来表示struct标记和ty胡枝子。然后，代码就会变得不那么让人困惑了。
• 通常惯例是将类型命名为stack_t。取决于编码风格。所以在h文件中应该有类似于typedef struct stack_t stack_t;的东西
• 阅读关于康斯特正确性的文章。不修改指向对象的函数应该将指针声明为指针到-const。
• 由于公开文档中的h文件是c文件所做的，所以最好将所有#include放在h文件中，以显示模块对其他库的依赖关系。
• 不要使用布尔逻辑而不是!运算符来比较整数或指针，它应该只用于布尔逻辑。相反，对于指针的空检查应该是显式的，s == NULL。
• 在每一个{ }或循环之后始终使用大括号if (又称“复合语句”)。不这么做的人迟早会写错误。把苹果的"goto fail“错误看作一个完美的例子。我不认为那个写了10亿美元的错误的人是个新手，而是一个傲慢的老兵，他坚持不使用牙套，没有什么好的理由。
• 尽管C允许安全地省略return语句，但main()中的返回始终是正确的。