c - 为什么我用链表实现的栈程序会出现堆损坏？以及如何解决？

Question

我为我在学校上的数据结构类(class)创建了一个 C 头文件。我在 C 和 C++ 方面的编码经验有限。它包含使用链接列表构建堆栈以进行数据存储的代码。当我尝试使用 Visual Studio 2013 运行驱动程序以测试实现是否有效时，它会引发以下错误:

检测到堆损坏:在 0x006F8178 处的正常 block (#68) 之后。CRT 检测到应用程序在堆缓冲区结束后写入内存。

上述头文件中的代码如下:

#include <stdlib.h>
#include <stdbool.h>

//type definition for a single stack data node
typedef struct node
{
    void *dataPtr; //create void pointer to user data
    struct node *link; //create pointer to next node in stack
}STACK_NODE;

//type definition for stack head structure
typedef struct stack
{
    int count; //location to hold number of entries in stack
    STACK_NODE *top; //create pointer to top of stack
}STACK;

//function to create empty stack
STACK* createStack()
{
    STACK *stack; //create a stack head node

    stack = (STACK*)malloc(sizeof(STACK));
    if (stack){
        stack->count = 0; //set stack count to zero
        stack->top = NULL; //initialize top pointer to null
    }
    return stack; //return address of node in dynamic memory
}

//function to push data onto stack
bool pushStack(STACK *stack, void *dataInPtr)
{
    STACK_NODE *newPtr;

    newPtr = (STACK_NODE*)malloc(sizeof(STACK_NODE*));
    //if out of memory
    if (!newPtr)
        return false;

    newPtr->dataPtr = dataInPtr; //assign data pointer to node
    newPtr->link = stack->top; //set link to point to node currently indicated as stack top
    stack->top = newPtr; //set top node to point to data in new node

    ++(stack->count); //add one to stack count
    return true;
}

//function to pop data off the stack and recycle node
void* popStack(STACK *stack)
{
    void *dataOutPtr;
    STACK_NODE *temp;

    //if stack is empty, return NULL
    if (stack->count == 0)
        dataOutPtr = NULL;
    else{
        temp = stack->top; //set temp to point to top node to be recycled
        dataOutPtr = stack->top->dataPtr; //set dataOutPtr to point to value currently stored in the top node
        stack->top = stack->top->link; //set top pointer to point to next node in stack
        free(temp); //delete top node
        --(stack->count);
    }
    return dataOutPtr; //return address of popped data
}

//function to retrieve data in top node
void* stackTop(STACK *stack)
{
    //if stack is empty, return NULL
    if (stack->count == 0)
        return NULL;
    //if top node contains data, return dataPtr
    else
        return stack->top->dataPtr;
}

//function to test if stack contains data
bool emptyStack(STACK *stack)
{
    return (stack->count == 0);
}

//function to delete nodes in stack
STACK* destroyStack(STACK *stack)
{
    STACK_NODE *temp;

    //if stack is not empty
    if (stack){
        //delete all nodes in stack
        while (stack->top != NULL){
            //delete data entry in top node
            free(stack->top->dataPtr);

            temp = stack->top; //set temp to point to top node to be recycled
            stack->top = stack->top->link; //set top node to point to next node
            free(temp); //destroy top node
        }
        //stack now empty, destroy stack head node
        free(stack);
    }
    return NULL;
}

驱动程序代码如下:

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

int main()
{
    int a = 4;
    int *dataPtr, *result, *popped;

    STACK *stack1;

    //create stack
    stack1 = createStack();

    //push value in a onto stack and output value on stack top
    dataPtr = malloc(sizeof(int));
    *dataPtr = a;
    pushStack(stack1, dataPtr);
    result = (int*)stackTop(stack1);
    printf("Value in stack is: %d\n", *result);

    //pop stack and output popped value
    popped = (int*)popStack(stack1);
    printf("Value popped off is: %d\n", *popped);

    destroyStack(stack1);
    return 0;
}

TBH，当我第一次看到错误消息时，我不知道它是什么意思。在做了一些初步研究后，我现在明白这是由于将数据写入堆缓冲区而没有首先分配足够的内存造成的。

虽然我不完全确定，但我相信错误发生在 popStack 和 destroyStack 函数中的行:

temp = stack->top;

并在以下行检测并报告:

free(temp);

我的想法是将当前栈顶节点(stack->top)包含的地址传递给一个临时节点，然后调用free()释放临时节点中的内存。由于两个指针的类型相同(即都是 STACK_NODE 类型)，我不明白为什么赋值操作会触发堆损坏错误。

如果您能帮助解决问题，我们将不胜感激!

Answer 1

  newPtr = (STACK_NODE*)malloc(sizeof(STACK_NODE*));

正在为“STACK_NODE 指针”分配足够的存储空间 - 通常为 4 个字节 - 但 sizeof (STACK_NODE) 为 8 个字节，因此当您使用 newPtr 时，您将覆盖内存。

正确的形式是

  newPtr = (STACK_NODE*)malloc(sizeof(STACK_NODE));