Проблемы с push в стеке - PullRequest
Новая
       26

Проблемы с push в стеке

0 голосов
/ 30 января 2019

Для стека, который я реализовал в C, у меня есть некоторые вопросы с добавлением элементов.Стек был инициализирован с размером init_size, но когда вершина указателя достигает вершины стека, я увеличиваю размер стека, когда новый элемент будет помещен в стек.

Код работает нормально, если я передаю ссылку на структуру sqStack sq на функцию push;если я передам указатель sqStack * st, код с ошибкой в ​​строке "* sq-> top ++ = e;"в функции push, как вы можете видеть в следующем коде (хотя иногда он работал нормально).А что касается функции pop, я не освобождаю каждый элемент, который мне показывал, это нормально?Может ли кто-нибудь помочь мне выяснить проблему?Спасибо! 

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

#define init_size 10
#define increment 1

typedef struct sqStack
{
    int* top;
    int* base;
    int stack_size;
}sqStack;

int init_stack(sqStack* sq)
{
    if(sq->base==NULL)
    {
       sq->base = (int*)malloc(init_size*sizeof(int));
    }
    if(sq->base==NULL) exit(-1);
    sq->stack_size=init_size;
    sq->top=sq->base;
    return 1;
}
int push(sqStack* sq, int e)
{
    if(sq==NULL) exit(-1);

    if(sq->top-sq->base==sq->stack_size-1)//pointer top reaches the top of the stack
    {
        int* q = (int*)realloc(sq->base,(init_size+increment)*sizeof(int));
        if(q==NULL)  exit(-1);
            sq->base=q;
        sq->top=sq->base+sq->stack_size-1;
            sq->stack_size += increment;

    }
    *sq->top++=e;//Thread 1: EXC_BAD_ACCESS (code=EXC_I386_GPFLT)
    return 1;
}
int pop(sqStack* sq,int* e)
{
    if(sq==NULL) exit(-1);
    if(sq->base==sq->top)  exit(-1);
    sq->top--;
    *e=*sq->top;
    return *e;
}

int empty(sqStack* sq)
{
    if(sq->base==sq->top) return 1;
    else return 0;
}

int main() {

    /*sqStack sq  ;
    init_stack(&sq);

    int a;
    for(int i=0;i<12;i++)
    {
        push(&sq,i+1);
    }
    for(int i=0;i<12;i++)
    {
        printf("%d\n",pop(&sq,&a));
    }*/
    sqStack* st= (sqStack*)malloc(sizeof(sqStack))  ;
    int e;
    init_stack(st);
    for(int i=0;i<12;i++)
    {
        push(st,i+1);
    }
    for(int i=0;i<12;i++)
    {
        printf("%d\n",pop(st,&e));
    }
    return 0;
}

Если вы хотите проверить справочную часть, просто раскомментируйте первую часть кода в main, а вторую часть main - указатель.

1 Ответ

0 голосов
/ 30 января 2019

Функция malloc не инициализирует выделенную память, она будет иметь неопределенное (и, казалось бы, случайное) содержимое.

Это означает условие if (sq->base==NULL) в init_stack function может быть false , что приводит к неопределенному поведению , когда вы начинаете разыменовывать этот указатель.

Либо все элементы считаются "мусором"msgstr "в функции init_stack и безоговорочно выделять память.Или инициализируйте члены перед вызовом init_stack (например, вместо этого используйте calloc.

Также есть логическая ошибка в функции push, где вы используете init_size+increment для вычисления нового размера в вызове realloc. Проблема в том, что ни init_size, ни increment не изменится, поэтому каждый раз, когда вы вызываете realloc, он будет иметь точно такой же размер.

Это, конечно, означает, что когда вы меняете sq->stack_size, это будет неправильно со второго раза, когда вы звоните realloc. И это приводит к неопределенному поведению снова, так как вы затем рискуете выйти изграницы выделенной памяти.

Использовать текущий размер стека при вычислении нового размера, как в sq->stack_size + increment.

...