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;
}
struct aux
? Porque não deixou uma versão demain()
com um teste?