C类型栈:链表实现

Question

我有一个计算机科学考试，其中很大一部分是关于c++编程的。我是C的新手，作为复习，我尝试使用链表实现堆栈。我的代码可以编译，但没有按预期运行。

我相信我的push()函数有错误。我假设我的堆栈引用没有被正确更新。

我从零开始编写了下面的代码来学习/实践。任何关于如何修复我的代码或改进我的编程风格的建议将非常感激。

谢谢你们了!

---

stack.h

#ifndef __STACK__
#define __STACK__
#include <stdlib.h>
#include "bool.h"
#define EMPTY -1
typedef struct Node {
    int index;
    enum { INT = 0, CHAR, STRING } type;
    union {
        int i;
        char c;
        char* s;
    } value;
    struct Node* prev;
} Node;
typedef Node* Stack;
Stack init();
void push(Stack stack, int type, void* value);
void pop(Stack stack, Node* node);
void empty(Stack stack);
Bool isempty(Stack stack);
#endif

stack.c

#include <stdlib.h>
#include <string.h>
#include "stack.h"
Stack init() {
    Stack stack = (Node*) malloc(sizeof(Node));
    stack->index = EMPTY;
    stack->type = INT;
    stack->value.i = 0;
    stack->prev = 0;
    return stack;
}
void push(Stack stack, int type, void* value) {
    int length;
    Node* node = (Node*) malloc(sizeof(Node));
    node->index = stack->index + 1;
    node->type = type;
    switch(node->type) {
        case INT:
            node->value.i = *((int*) value);
        break;
        case CHAR:
            node->value.c =  *((char*) value);
        break;
        case STRING:
            length = strlen((char*) value) + 1;
            node->value.s = (char*) malloc(length * sizeof(char));
            strcpy(node->value.s, value);
        break;
    }       
    node->prev = stack;
    stack = node;
}
void pop(Stack stack, Node* node) {
    int length;
    Node* temp = stack;
    if (!isempty(stack)) {
        node->index = stack->index;
        node->type = stack->type;
        switch(stack->type) {
            case INT:
                node->value.i = stack->value.i;
            break;
            case CHAR:
                node->value.c = stack->value.c;
            break;
            case STRING:
                length = strlen(stack->value.s) + 1;
                node->value.s = (char*) malloc(length * sizeof(char));
                strcpy(node->value.s, stack->value.s);
                free(stack->value.s);
            break;
        }
        node->prev = 0;
        stack = stack->prev;
        free(temp); 
    } else {
        /*TODO: handle empty case */    
        puts("Stack empty!");
    }
}
void empty(Stack stack) {
    while (!isempty(stack)) {
        Node* temp = malloc(sizeof(Node));
        pop(stack, temp);
        free(temp);
    }
}
Bool isempty(Stack stack) {
    return stack->index == EMPTY ? TRUE : FALSE;
}

bool.h

#ifndef __BOOL__
#define __BOOL__
typedef int Bool;
#define FALSE 0
#define TRUE 1
#endif

c

#include <stdlib.h>
#include <stdio.h>
#include "stack.h"
int main() {
    Stack stack = init();
    Node* node = malloc(sizeof(Node));
    int i = 5;
    push(stack, 0, &i);
    pop(stack, node);
    printf("Node value: %dn", node->value.i);
    free(node);
    empty(stack);
    puts("done.");
    return 0;
}

Answer 1

你真的没有修改堆栈。对于push, pop和empty方法，必须使用&stack。他们将有以下签名:

void push(Stack * stack, int type, void* value);
void pop(Stack * stack, Node* node);
void empty(Stack *stack);

，当然，在这些方法中使用指针内容，如:

void push(Stack * stack, int type, void* value) {
    int length;
    Node* node = (Node*) malloc(sizeof(Node));
    node->index = (*stack)->index + 1;
    node->type = type;
    switch(node->type) {
        case INT:
            node->value.i = *((int*) value);
        break;
        case CHAR:
            node->value.c =  *((char*) value);
        break;
        case STRING:
            length = strlen((char*) value) + 1;
            node->value.s = (char*) malloc(length * sizeof(char));
            strcpy(node->value.s, value);
        break;
    }
    node->prev = *stack;
    *stack = node;
}
void pop(Stack * stack, Node* node) {
    int length;
    Node* temp = *stack;
    if (!isempty(*stack)) {
        node->index = (*stack)->index;
        node->type = (*stack)->type;
        switch((*stack)->type) {
            case INT:
                node->value.i = (*stack)->value.i;
            break;
            case CHAR:
                node->value.c = (*stack)->value.c;
            break;
            case STRING:
                length = strlen((*stack)->value.s) + 1;
                node->value.s = (char*) malloc(length * sizeof(char));
                strcpy(node->value.s, (*stack)->value.s);
                free((*stack)->value.s);
            break;
        }
        node->prev = 0;
        *stack = (*stack)->prev;
        free(temp);
    } else {
        /*TODO: handle empty case */
        puts("Stack empty!");
    }
}
void empty(Stack *stack) {
    while (!isempty(*stack)) {
        Node* temp = malloc(sizeof(Node));
        pop(stack, temp);
        free(temp);
    }
}