0

我已经使用指针实现了堆栈。我一直在尝试将其概括为与任意数据类型一起使用。我已经尝试过，但无法弄清楚不正确的数据被推入堆栈的原因。

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

enum action {START, PUSH, POP, TOP, LENGTH, QUIT, END};
enum status {SUCCESS, FAILURE};

typedef struct node {
    void *data;
    struct node *lower;
} stack_node;

typedef struct stack {
    size_t elem_size;
    size_t stack_size;
    stack_node *top;
} stack_struct;

void clear_screen(void)
{
    system("cls");
}

static enum action get_user_action(void)
{
    int choice = START;
    do {
        clear_screen();
        printf("%d Push data\n"
               "%d Pop Data\n"
               "%d See the top of the stack\n"
               "%d See the length of the stack\n"
               "%d Exit\n\n"
               "Enter your choice -> ", PUSH, POP, TOP, LENGTH, QUIT);
        scanf("%d", &choice);
    } while (!(START < choice && choice < END));
    return (enum action) choice;
}

enum status stack_create(stack_struct **stack, size_t elem_size)
{
    (**stack).elem_size = elem_size;
    (**stack).stack_size = 0;
    (**stack).top = NULL;
    return SUCCESS;
}

enum status push(stack_struct **stack, void *data)
{
    stack_node *node = malloc(sizeof(node));
    if (node == NULL) {
        return FAILURE;
    }

    node->data = malloc(sizeof((**stack).elem_size));
    if (node->data == NULL) {
        return FAILURE;
    }
    memcpy(node->data, data, (**stack).elem_size);

    if ((**stack).top == NULL) {
        node->lower = NULL;
    } else {
        node->lower = (**stack).top;
    }
    (**stack).top = node;
    (**stack).stack_size += 1;
    return SUCCESS;
}

enum status pop(stack_struct *stack, void *data)
{
    if (stack->top == NULL) {
        return FAILURE;
    }
    stack_node *node = stack->top;
    memcpy(data, node->data, stack->elem_size);
    stack->top = node->lower;

    free(node->data);
    free(node);

    stack->stack_size -= 1;
    return SUCCESS;
}

enum status peek(stack_struct *stack, void *data)
{
    if (stack->top == NULL) {
        return FAILURE;
    }
    memcpy(data, stack->top->data, stack->elem_size);
    return SUCCESS;
}

void stack_delete(stack_struct *stack)
{
    while (stack->top != NULL)
    {
        stack_node *node = stack->top;
        stack->top = stack->top->lower;
        free(node->data);
        free(node);
    }
}

int main(void)
{
    enum action choice;
    stack_struct *stack = malloc(sizeof(stack_struct));
    if (stack == NULL)
    {
        printf("Not enough memory\n");
        return 1;
    }
    stack_create(&stack, sizeof(int));

    while ((choice = get_user_action()) != QUIT) {
        clear_screen();
        int data;
        switch (choice) {

            case PUSH:
                printf("Enter data to be pushed -> ");
                scanf("%d", &data);
                if (push(&stack, &data) == SUCCESS){
                    printf("%d pushed onto the stack", (int)stack->top->data);
                } else {
                    printf("Not enough memory\n");
                }
                break;

            case POP:
                if (pop(stack, &data) == SUCCESS){
                    printf("The data is %d\n", data);
                } else {
                    printf("Stack underflow\n");
                }
                break;

            case TOP:
                if (peek(stack, &data) == SUCCESS){
                    printf("The data at top is %d\n", data);
                } else {
                    printf("Nothing in the stack\n");
                }
                break;

            case LENGTH:
                printf("Length is %d\n", stack->stack_size);
                break;

            default:
                assert(!"You should not have reached this.\n");

        }
        stack_delete(stack);
        getchar();
        getchar();
    }
}

我按下 234 并得到一个垃圾值。

更新 1

我有一个使用指针的堆栈的工作副本。它不适用于任意数据类型，而仅适用于int. 可以在 codereview上查看它，在那里我想到了将其用于任意数据。

更新 2

在 p0w 指出printfinmain不正确后，我更正了这一点。我还更改了pop,peek和stack_delete函数，以便struct传递指向指针的指针。

printf表明正在传递正确的数据，但pop不peek这么认为。

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

enum action {START, PUSH, POP, TOP, LENGTH, QUIT, END};
enum status {SUCCESS, FAILURE};

typedef struct node {
    void *data;
    struct node *lower;
} stack_node;

typedef struct stack {
    size_t elem_size;
    size_t stack_size;
    stack_node *top;
} stack_struct;

void clear_screen(void)
{
    system("cls");
}

static enum action get_user_action(void)
{
    int choice = START;
    do {
        clear_screen();
        printf("%d Push data\n"
               "%d Pop Data\n"
               "%d See the top of the stack\n"
               "%d See the length of the stack\n"
               "%d Exit\n\n"
               "Enter your choice -> ", PUSH, POP, TOP, LENGTH, QUIT);
        scanf("%d", &choice);
    } while (!(START < choice && choice < END));
    return (enum action) choice;
}

enum status stack_create(stack_struct **stack, size_t elem_size)
{
    (**stack).elem_size = elem_size;
    (**stack).stack_size = 0;
    (**stack).top = NULL;
    return SUCCESS;
}

enum status push(stack_struct **stack, void *data)
{
    stack_node *node = malloc(sizeof(node));
    if (node == NULL) {
        return FAILURE;
    }

    node->data = malloc(sizeof((**stack).elem_size));
    if (node->data == NULL) {
        return FAILURE;
    }
    memcpy(node->data, data, (**stack).elem_size);

    if ((**stack).top == NULL) {
        node->lower = NULL;
    } else {
        node->lower = (**stack).top;
    }
    (**stack).top = node;
    (**stack).stack_size += 1;
    return SUCCESS;
}

enum status pop(stack_struct **stack, void *data)
{
    if ((**stack).top == NULL) {
        return FAILURE;
    }
    stack_node *node = (**stack).top;
    memcpy(data, node->data, (**stack).elem_size);
    (**stack).top = node->lower;
    node->lower = NULL;

    free(node->data);
    free(node);

    (**stack).stack_size -= 1;
    return SUCCESS;
}

enum status peek(stack_struct **stack, void *data)
{
    if ((**stack).top == NULL) {
        return FAILURE;
    }
    memcpy(data, (**stack).top->data, (**stack).elem_size);
    return SUCCESS;
}

void stack_delete(stack_struct **stack)
{
    while ((**stack).top != NULL)
    {
        stack_node *node = (**stack).top;
        (**stack).top = (**stack).top->lower;
        free(node->data);
        free(node);
    }
}

int main(void)
{
    enum action choice;
    stack_struct *stack = malloc(sizeof(stack_struct));
    if (stack == NULL)
    {
        printf("Not enough memory\n");
        return 1;
    }
    stack_create(&stack, sizeof(int));

    while ((choice = get_user_action()) != QUIT) {
        clear_screen();
        int data;
        switch (choice) {

            case PUSH:
                printf("Enter data to be pushed -> ");
                scanf("%d", &data);
                if (push(&stack, &data) == SUCCESS){
                    printf("%d pushed onto the stack\n", *(int *)stack->top->data);
                    printf("%u is top of stack", stack->top);
                } else {
                    printf("Not enough memory\n");
                }
                break;

            case POP:
                if (pop(&stack, &data) == SUCCESS){
                    printf("The data is %d\n", data);
                } else {
                    printf("Stack underflow\n");
                }
                break;

            case TOP:
                if (peek(&stack, &data) == SUCCESS){
                    printf("The data at top is %d\n", data);
                } else {
                    printf("Nothing in the stack\n");
                }
                break;

            case LENGTH:
                printf("Length is %d\n", stack->stack_size);
                break;

            default:
                assert(!"You should not have reached this.\n");

        }
        stack_delete(&stack);
        getchar();
        getchar();
    }
}
4

2 回答 2

3

你的结构data是void *如此固定printf

printf("%d pushed onto the stack", *(int *)stack->top->data);

但是，其他堆栈操作似乎也存在其他问题。

此外，如果您打算将其作为通用堆栈，为什么%d在printf？

这您可能需要重新访问。

于 2013-08-04T10:27:57.780 回答
1

除了 P0W 和我提到的几点之外，您的代码中存在导致崩溃VS2010但不会在GCC.

在push函数中动态创建 stack_node 对象时，您传递的sizeof(node)wherenode是一个指针，stack_node而不是您应该传递的sizeof(stack_node).

malloc在这两种情况下分配的内存量是不同的。在第一个你得到4 bytes（因为指针的大小），在第二个你得到8 bytes（因为 stack_node 的大小）。

在这种情况下，您无法访问stack_node对象的第二个成员，即 struct node *lower. 此外，当您访问未分配的内存时，这可能需要未定义的行为。

最后在声明中free(node)它崩溃了。

我不知道为什么会发生这种情况的确切原因，也不知道free幕后是如何运作的。

我想知道这种情况的原因。

于 2013-08-04T13:20:36.303 回答