Странная ошибка реализации стека

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;

В первый раз вы malloc обнуляете байты для new_array, проходите через цикл for ноль раз, а затем присваиваете 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;
}   

Вы упоминаете в комментарии, что еще не освобождаете память, поэтому ваш следующий шаг - правильно освободить блоки памяти, которые вы больше не используете, чтобы не было утечек ...