0

A pilha dinâmica funciona normalmente, mas quando tento utilizar o método free() para desalocar a memória dos elementos removidos e reinicializar a estrutura, o compilador não retorna o esperado. Na realidade, não aparece nada, nenhum erro, mas não funciona. O código só passa a funcionar normalmente depois de comentar a função free().

Já procurei onde estaria o possível erro, mas não encontrei. Tenho quase certeza que é falha na estrutura do código. Porém, como eu disse acima, aparentemente funciona exceto quando tento desalocar memória e não sei onde está o erro.

Funções onde aparentemente acontece o problema (pop e restartStack):

int pop (STACK *stack) {

    if (stack->top != NULL) {
        ELEMENT *aux = stack->top;
        stack->top = stack->top->next;
        free(aux);

        return TRUE;
    }

    return FALSE;
}
void restartStack (STACK *stack) {
    ELEMENT *position = stack->top;

    while (position != NULL) {
        ELEMENT *remove = position;
        position = position->next;
        free(remove);
    }

    stack->top = NULL;

}

A estrutura como um todo:

#include <stdio.h>
#include <malloc.h>

#define TRUE 0
#define FALSE 1
#define DEBUG
#undef DEBUG
typedef int TYPEKEY;


typedef struct {
    TYPEKEY key;
    struct ELEMENT* next;
} ELEMENT;

typedef struct {
    ELEMENT *top;
} STACK;

void startStack (STACK *stack) {
    stack->top = NULL;
}

int stackLenght (STACK *stack) {
    ELEMENT *element = stack->top;
    int lenght = 0;

    while (element != NULL) {
        element = element->next;
        lenght++;
    }

    return lenght;
}

int isEmpty (STACK *stack) {
    return stack->top == NULL ? TRUE : FALSE;
}

void showElements (STACK *stack) {
    ELEMENT *element = stack->top;

    while (element != NULL) {
        printf("%d ", element->key);
        element = element->next;
    }

    printf("\n");
}

void push (STACK *stack, ELEMENT *elementToInsert) {

    /* Aloca memória */
    ELEMENT *aux = (ELEMENT*) malloc(sizeof(ELEMENT));
    /* Guarda o antigo topo */
    aux = stack->top;

    /* O novo elemento é o topo*/
    stack->top = elementToInsert;

    /* O antigo topo é o next */
    elementToInsert->next = aux;

}

int pop (STACK *stack) {

    if (stack->top != NULL) {
        ELEMENT *aux = stack->top;
        stack->top = stack->top->next;
        free(aux);

        return TRUE;
    }

    return FALSE;
}

ELEMENT* topStack (STACK *stack) {
    return stack->top != NULL ? stack->top : NULL;
}

void restartStack (STACK *stack) {
    ELEMENT *position = stack->top;

    while (position != NULL) {
        ELEMENT *remove = position;
        position = position->next;
        free(remove);
    }

    stack->top = NULL;

}

main:

int main () {
        ELEMENT ELEMENT, ELEMENT2, ELEMENT3;

        STACK stack;

        ELEMENT.key = 5;
        ELEMENT2.key = 7;
        ELEMENT3.key = 2;

        startStack(&stack);
        push(&stack, &ELEMENT);
        push(&stack, &ELEMENT2);
        push(&stack, &ELEMENT3);
        //pop(&stack); - ERRO, COMPILADOR FICAR EM LOOPING OU RETORNA UM EXIT CODE != 0
        //restartStack(&stack); - ERRO, COMPILADOR FICAR EM LOOPING OU RETORNA UM EXIT CODE != 0

        printf("%d\n", stackLenght(&stack));

        showElements(&stack);
}
6
  • Use nomes mais significativos. Que é essa meiga struct aux? Porque não deixou uma versão de main() com um teste?
    – arfneto
    Commented 30/03/2021 às 3:42
  • Opa. Perdão, eu esqueci de declarar aux em cima da struct. Eu editei. No caso seria uma referência da própria struct. Coloquei um exemplo do main também.
    – Staniack
    Commented 30/03/2021 às 9:11
  • Você alocou memória na stack e está tentando limpar ela.
    – sgtcortez
    Commented 30/03/2021 às 12:17
  • Perdão, não entendi a sua resposta
    – Staniack
    Commented 30/03/2021 às 12:19
  • a memória foi alocada normalmente, no heap por um push anterior... estava errado o sizeof() antes, mas o autor corrigiu
    – arfneto
    Commented 30/03/2021 às 15:10

2 Respostas 2

1

Veja bem, você está deixando com que o compilador faça a alocação, e depois, tenta liberar essa memória(se não me engano, o comportamento disso é indefinido, o que pode dar muitas dores de cabeça).

int pop (STACK *stack) {

    if (stack->top != NULL) {
        ELEMENT *aux = stack->top;
        stack->top = stack->top->next;

        // irá funcionar porque tenho certeza que aloquei memória na heap
        free(aux);

        return TRUE;
    }

    return FALSE;
}
/**
* Apenas espero a chave, a memória irei alocar internamente
 sendo assim, tenho controle de quando devo desalocar
*/ 
void push (STACK *stack, int key) {

    // aloca memória no heap
    ELEMENT *element = malloc(sizeof(ELEMENT));
    element->key = key;
    element->next = stack->top;
    stack->top = element;
}
int main () {

        STACK stack;

        startStack(&stack);
        push(&stack, 5);
        push(&stack, 10);
        push(&stack, 15);
        
        printf("%d\n", stackLenght(&stack));

        showElements(&stack);
        pop(&stack);
        showElements(&stack);
        push(&stack, 900);
        showElements(&stack);
}

Ao compilar com o gcc você verá alguns warnings do compilador como "assignment from incompatible pointer type" isso porque você definiu a struct como ELEMENT e não struct ELEMENT e dentro da própria struct ELEMENT, você está utilizando struct ELEMENT.

Para corrigir:

typedef struct ELEMENT {
    TYPEKEY key;
    struct ELEMENT *next;
} ELEMENT;
3
  • @Staniack corrige um erro de digitação meu na alocacação de memória, eu estava utilizando alocacando memória para um ponteiro, o que daŕa problema no futuro. Também atualizei a resposta por causa de um aviso do compilador(que nao daria problema, mas é chato)
    – sgtcortez
    Commented 30/03/2021 às 15:40
  • Eu corrigi. Esqueci-me de agradecê-lo. Erro bobo meu, mas que compromete todo o funcionamento. Você diz (ELEMENT*) malloc(sizeof(ELEMENT))? Eu eventualmente faço isso, mas qual seria o problema em fazê-lo?
    – Staniack
    Commented 30/03/2021 às 20:34
  • O cast não é necessário, mas se você olhar as minhas edições, verá que eu tinha malloc(sizeof(element)); Só que element era um ponteiro, sendo assim, estava alocando apenas 8 bytes(tamanho de um ponteiro em máquinas 64 bits)
    – sgtcortez
    Commented 30/03/2021 às 23:55
1

Estruturas como essa pilha são chamadas de containers em C++ ou de coleções em java, e na literatura aparecem como ADT, estruturas abstratas de dados. E você tem que aproximar seu programa disso, do lado abstrato. Vou mostrar um exemplo abaixo.

No geral o container é um conjunto S possivelmente vazio de registros X, e cada registro tem um conteúdo que em geral contém uma chave k. E assim você escreve todas as funções em termos de ponteiros para nós e os nós em geral tem apenas um ponteiro para o registro, que por sua vez contem a chave.

Em programas para estudo muitas vezes o registro é a própria chave só, como uma letrinha ou no seu caso um simples int:

typedef int TYPEKEY;

Você não usou um ponteiro mas sim uma chave alocada DENTRO do registro.

Na primeira versão você estava alocando o tamanho errado em push(). Agora parece certo. Mas entenda que ao inserir algo na pilha ou retornar você deve copiar os dados para dentro da pilha e ao retirar você deve retornar uma cópia deles.

O problema é que o usuário da pilha pode passar várias vezes o mesmo registro, ou passar uma chave para key a partir de um ponteiro que veio de sei lá onde. Se você colocar isso na pilha um pop() posterior vai cancelar seu programa. Ou um restart() ou delete(). Não podem haver ponteiros soltos pelo programa se referindo a áreas dentro da pilha. E vice-versa.

Um outro ponto, e que pode ver em uma resposta logo acima, é que o acesso aos elementos da pilha é feito em termos da chave, não em termos do nó em si: a estrutura do nó é uma coisa interna à pilha.

No seu caso, você faz um push() de um TYPEKEY, não de um ELEMENT. E top() retorna um ponteiro para key, não para um nó.

EXEMPLO

alterei um pouco seu programa e pode comparar as funções. Antes de tudo as estruturas

typedef int Key;

typedef struct aux_
{
    Key             key;
    struct aux_*    next;

}   Element;

typedef struct
{
    Element*    top;
    unsigned    size;

}   Stack;

Usei a convenção comum de reservar nomes com a primeira letra em maiúscula para os typedef e, apesar de não ser o comum, mantive no node a chave e não o ponteiro para ela, que é o mais comum. size é uma questão prática: é bom ter um contador atualizado. é normal implementar a pilha usando um vetor alocado dinamicamente e aí teria também o valor da capacidade, e tudo ficaria muito mais rápido, usando ponteiros como índices e não Element*

As funções

int         empty (Stack*);
int         pop   (Stack*);
int         push  (Key*,Stack*);
int         size  (Stack*);
Key*        top   (Stack*); 

Esses são o nomes como usados em C++, por exemplo. Mas note que

  • não há void: sempre retorna um status, negativo para erro, 0 para sucesso, como é comum em C.
  • push() recebe um ponteiro para Key e não para Element: Element é algo interno
  • top() retorna um ponteiro para a chave, mas um ponteiro para uma cópia do registro, e é importante entender isso: você não sabe o que o usuário vai fazer com a chave, e assim tem que retornar uma cópia, e o usuário da API é responsável --- owner --- pelo ponteiro e deve liberar a memória quando não for usar mais o registro. Várias chamadas a top() seguidas retornam ponteiros para cópias do mesmo registro e se o usuário da API liberar um não vai zoar o outro. É importante entender isso. Veja no programa exemplo.

As outras funções

Stack*      deleteStack  (Stack*);
int         restartStack (Stack*); // empties
int         showStack    (Stack*,const char*); // list all
Stack*      startStack   (unsigned); // return new

deleteStack() retorna NULL. Apenas para poder ser usado numa expressão e invalidar o próprio ponteiro da pilha no programa. Veja no exemplo.

  • restartStack() não precisa mas pode e foi aqui escrita em termos de pop() para evitar repetição de código
  • showStack() é uma função de teste. Não existe numa pilha normal e não faz sentido: numa pilha só se vê um elemento por vez. Acrescentei um parâmetro, um const char*, para mostrar um título opcional, porque é uma "mão na roda" nos testes.

O programa de exemplo

O programa cria uma pilha com um certo número de registros, mostra, apaga a metade deles e lista o resto. Depois testa o restart(), o delete() e encerra. Não testei muito mas pode servir.

Eis o código:

int main(void)
{
    const int tamanho = 10;
    Stack* nova = startStack(tamanho);
    showStack(nova,"teste: pilha vazia ainda...");
    printf("Vai inserir 1..10\n");
    for( int i = 1; i<=tamanho; i+=1) push(&i,nova);
    showStack(nova,"teste: pilha agora");
    printf("Tenta remover metade dos elementos\n");
    Key* p = NULL;
    int n = nova->size/2;
    for ( int i = 0; i<n; i+= 1)
    {
        printf("Vai remover '%d'\n", *(p = top(nova)));
        free(p); // nao vai usar mais
        pop(nova);
    };  // for()
    showStack(nova,"teste: pilha agora:");
    printf("Usando restart() na pilha\n");
    restartStack(nova);
    showStack(nova,"teste: depois do restart()");
    printf("Apagando a pilha\n");
    nova = deleteStack(nova);
    printf("Apagando a pilha\n");
    showStack(nova,"vazia?");
    showStack(nova,NULL);
    return 0;
}

A saída do exemplo

toninho@DSK-2009:~/projects/triangle$ ./build/stan
teste: pilha vazia ainda...
Pilha com 0 elementos


Vai inserir 1..10
teste: pilha agora
Pilha com 10 elementos
10 9 8 7 6 5 4 3 2 1 

Tenta remover metade dos elementos
Vai remover '10'
Vai remover '9'
Vai remover '8'
Vai remover '7'
Vai remover '6'
teste: pilha agora:
Pilha com 5 elementos
5 4 3 2 1 

Usando restart() na pilha
teste: depois do restart()
Pilha com 0 elementos


Apagando a pilha
Apagando a pilha
Pilha nao construida!
Pilha nao construida!

push()

int         push (Key* k, Stack* s)
{
    // cria um elemento e coloca na pilha.
    // retorna o tamanho se ok, ou algo negativo
    if ( s == NULL ) return -1;
    if ( k == NULL ) return -2;
    Element* el = (Element*) malloc(sizeof(Element));
    if ( el == NULL ) return -3;
    el->key = *k; // shallow copy here!!
    el->next = s->top; // new at the TOP
    s->top = el;
    s->size += 1;
    return s->size;
}

Apenas note que é criado um elemento e a chave é copiada para dentro. Assim se o usuário da API liberar o ponteiro depois não vai destruir a pilha...

restart()

int         restartStack(Stack* s)
{
    if ( s == NULL ) return -1;
    while ( s->size > 0 ) pop(s);
    return 0;
}

Veja que é mais simples escrever restart() a partir de pop(), além de ser um lugar a menos para testar :)

O programa todo

#include <stdio.h>
#include <malloc.h>

typedef int Key;

typedef struct aux_
{
    Key             key;
    struct aux_*    next;

}   Element;

typedef struct
{
    Element*    top;
    unsigned    size;

}   Stack;
// classic
int         empty (Stack*);
int         pop   (Stack*);
int         push  (Key*,Stack*);
int         size  (Stack*);
Key*        top   (Stack*); 
// support
Stack*      deleteStack  (Stack*);
int         restartStack (Stack*); // empties
int         showStack    (Stack*,const char*); // list all
Stack*      startStack   (unsigned); // return new

int main(void)
{
    const int tamanho = 10;
    Stack* nova = startStack(tamanho);
    showStack(nova,"teste: pilha vazia ainda...");
    printf("Vai inserir 1..10\n");
    for( int i = 1; i<=tamanho; i+=1) push(&i,nova);
    showStack(nova,"teste: pilha agora");
    printf("Tenta remover metade dos elementos\n");
    Key* p = NULL;
    int n = nova->size/2;
    for ( int i = 0; i<n; i+= 1)
    {
        printf("Vai remover '%d'\n", *(p = top(nova)));
        free(p); // nao vai usar mais
        pop(nova);
    };  // for()
    showStack(nova,"teste: pilha agora:");
    printf("Usando restart() na pilha\n");
    restartStack(nova);
    showStack(nova,"teste: depois do restart()");
    printf("Apagando a pilha\n");
    nova = deleteStack(nova);
    printf("Apagando a pilha\n");
    showStack(nova,"vazia?");
    showStack(nova,NULL);
    return 0;
}

int         empty (Stack* S)
{
    return S->size == 0;
}

int         pop (Stack* S)
{
    if ( S == NULL ) return -1;
    if ( empty(S) )  return -2;
    Element* to_delete = S->top;
    S->top = S->top->next;
    S->size -= 1;
    free(to_delete);
    return S->size;
}

int         push (Key* k, Stack* s)
{
    // cria um elemento e coloca na pilha.
    // retorna o tamanho se ok, ou algo negativo
    if ( s == NULL ) return -1;
    if ( k == NULL ) return -2;
    Element* el = (Element*) malloc(sizeof(Element));
    if ( el == NULL ) return -3;
    el->key = *k; // shallow copy here!!
    el->next = s->top; // new at the TOP
    s->top = el;
    s->size += 1;
    return s->size;
}

int         size(Stack* s)
{
    if ( s == NULL ) return -1;
    return s->size;
}

Key*        top(Stack* s)
{
    if ( s == NULL ) return NULL;
    Key* k = (Key*) malloc(sizeof(k));
    *k = s->top->key;
    return k;
}

Stack*      deleteStack(Stack* s)
{
    if ( s == NULL ) return NULL;
    while ( s->size > 0 ) pop(s);
    return NULL;
}

int         restartStack(Stack* s)
{
    if ( s == NULL ) return -1;
    while ( s->size > 0 ) pop(s);
    return 0;
}


int         showStack (Stack* s, const char* msg)
{   
    // prints stack nodes along with optional message
    if ( s == NULL )
    {
        printf("Pilha nao construida!\n");
        return -1;
    };
    if ( msg != NULL )
    {
        printf("%s\n", msg);
    }
    printf("Pilha com %d elementos\n", s->size);
    Element* p = s->top;
    while ( p != NULL )
    {
        printf( "%d ", p->key );
        p = p->next;
    }
    printf("\n\n");
    return s->size;
}

Stack*      startStack (unsigned sz)
{
    const unsigned dflt = 1000;  // default size
    Stack*      stack = (Stack*) malloc(sizeof(Stack));
    if ( stack == NULL ) return NULL;
    stack->top = NULL;
    stack->size = 0;
    return stack;
}
2
  • Muito obrigado, suas dicas valerão ouro! Essa parte do retorno de ponteiros foi ingenuidade da minha parte, isso altera completamente a estrutura. Bom, agora eu sei que não posso fazer isso.
    – Staniack
    Commented 30/03/2021 às 20:54
  • :) Atente para essa distinção sempre entre container e conteúdo. Todas ADT são iguais, e os sistemas em si são assim também. C foi escrita exatamente para escrever esse tipo de solução, essa construção tipo factory como em Stack* pilha = startStack(500). E esse lance de owning pointer de modo que você não aceita nada de fora e só retorna cópias do que tem dentro é outra coisa para manter um olho em cima.
    – arfneto
    Commented 30/03/2021 às 22:13

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .