奇怪的堆栈实现错误

Question

只是为了好玩，我实现了自己的堆栈，但是，没有使用链表，但它仍然是动态的，因为每次你推入它或弹出它时，它都会 malloc 是一个更大或更小的新数组，并且然后用已经存在的东西填充它（少一或多一）。我知道这是非常缓慢且愚蠢的方法，但是，我只是想看看它是否有效。

代码有点长，所以我将其粘贴到此处：

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

typedef struct {
    int size;
    int *stack_array;
}stack;

void newStack(stack *a) {
    a->size = 0;
    a->stack_array = malloc(sizeof(int) * 1); 
}

void push(stack *a, int x) {
    int *new_array = malloc(sizeof(int) * a->size);
    int i;
    for(i=0; i < a->size; i++) {
        new_array[i] = a->stack_array[i]; 
    }

    new_array[i] = x;

    a->stack_array = new_array;

    a->size += 1;
}

int pop(stack *a) {
    if(a->size <= 0) {
        printf("CALL POP() WITH FILLED STACK");
        exit(1);
    }
    int *new_array = malloc(sizeof(int) * (a->size)-1);
    int i;
    for(i=0; i < a->size-1; i++) {
        new_array[i] = a->stack_array[i];
    }

    int popped = a->stack_array[i];

    a->stack_array = new_array;
    a->size -= 1;   
    return popped;
}   

void printStack(stack *a) {
    int i;
    printf("{");
    for(i=0; i<a->size-1; i++) {
        printf("%d, ", (a->stack_array)[i]);
    }
    printf("%d}\n", (a->stack_array)[i]);
}

int main (void) {
    stack a;
    newStack(&a);

    push(&a, 6);
    push(&a, 12);
    push(&a, 13);

    printStack(&a);

    printf("Popped: %d\n", pop(&a));

    printStack(&a);
    return 0;
}

而且，如您所见，它工作得很好。

现在，当我向它添加一个循环时，要向堆栈中添加更多内容（粘贴此处）：

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

typedef struct {
    int size;
    int *stack_array;
}stack;

void newStack(stack *a) {
    a->size = 0;
    a->stack_array = malloc(sizeof(int) * 1); 
}

void push(stack *a, int x) {
    int *new_array = malloc(sizeof(int) * a->size);
    int i;
    for(i=0; i < a->size; i++) {
        new_array[i] = a->stack_array[i]; 
    }

    new_array[i] = x;

    a->stack_array = new_array;

    a->size += 1;
}

int pop(stack *a) {
    if(a->size <= 0) {
        printf("CALL POP() WITH FILLED STACK");
        exit(1);
    }
    int *new_array = malloc(sizeof(int) * (a->size)-1);
    int i;
    for(i=0; i < a->size-1; i++) {
        new_array[i] = a->stack_array[i];
    }

    int popped = a->stack_array[i];

    a->stack_array = new_array;
    a->size -= 1;   
    return popped;
}   

void printStack(stack *a) {
    int i;
    printf("{");
    for(i=0; i<a->size-1; i++) {
        printf("%d, ", (a->stack_array)[i]);
    }
    printf("%d}\n", (a->stack_array)[i]);
}

int main (void) {
    stack a;
    newStack(&a);

    int i = 0;
    for(i = 0; i<12; i++) {
        push(&a, i);
    }

    printStack(&a);

    return 0;
}

它运行在键盘上很好（这让我更加困惑），但是，在我的机器上，它给了我这个错误（我以前从未见过，这是在运行时给出的）：

a.out: malloc.c:3096: sYSMALLOc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 * (sizeof(size_t))) - 1)) & ~((2 * (sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long)old_end & pagemask) == 0)' failed.
Aborted

它可能会或可能不会产生影响机器运行这是一个 VirtualBox Linux 机器。另外，我显然没有很好地编写实现，因为它没有释放任何指针或空间，也没有检查许多错误。

Answer 1

在newStack中，你这样说：

void newStack(stack *a) {  
    a->size = 0;  
    a->stack_array = malloc(sizeof(int) * 1);   
}

所以a->size是最后一个元素的索引，而不是元素的数量。然后，在 push 中，您执行以下操作：

int *new_array = malloc(sizeof(int) * a->size);  
int i;  
for(i=0; i < a->size; i++) {  
    new_array[i] = a->stack_array[i];   
}
new_array[i] = x;

第一次，为 new_array malloc 零字节，运行 for< /code> 循环零次，然后将 x 分配给 new_array[0]。现在，您的堆因缓冲区溢出而损坏。你应该这样说：

int *new_array = malloc(sizeof(int) * (a->size + 1));

你也应该释放你的内存，也许你应该了解 realloc 和 memcpy。

Answer 2

当您将某些内容压入堆栈时，您分配的项目太少了。 push() 可能看起来像：

void push(stack *a, int x) {
    int *new_array = malloc(sizeof(int) * (a->size + 1));  // <=== changed
    int i;
    for(i=0; i < a->size; i++) {
        new_array[i] = a->stack_array[i]; 
    }

    new_array[i] = x;

    a->stack_array = new_array;

    a->size += 1;
}

在 pop() 中，即使在执行新分配时减一，由于运算符优先级，您也无法正确执行算术。这并不是一个真正的问题（就堆损坏而言），因为它会导致您的分配太大一点；您只是分配了一些您永远不会实际使用的字节。更不用说您的示例程序从未调用过它。尝试：

int pop(stack *a) {
    if(a->size <= 0) {
        printf("CALL POP() WITH FILLED STACK");
        exit(1);
    }
    int *new_array = malloc(sizeof(int) * ((a->size)-1));  // <=== changed
    int i;
    for(i=0; i < a->size-1; i++) {
        new_array[i] = a->stack_array[i];
    }

    int popped = a->stack_array[i];

    a->stack_array = new_array;
    a->size -= 1;   
    return popped;
}   

您在评论中提到您尚未释放任何内存，因此下一步是正确释放不再使用的内存块，这样就不会泄漏......