Difference between revisions of "Pilha (dimensão variável)"

From Wiki**3

 
(No difference)

Latest revision as of 09:46, 12 November 2008

Exemplo de pilha de strings de dimensão arbitrária (variável).

Ficheiro pilha.h

  /* resultado da operação de colocação na pilha */
  enum resultado { FALHA, SUCESSO };
  /* declarações das funções */
  void           inicia  (struct pilha *p);
  unsigned char  vazia   (struct pilha *p);
  size_t         tamanho (struct pilha *p);
  enum resultado push    (struct pilha *p, char *dados);
  char          *pop     (struct pilha *p);

Ficheiro pilha.c

Implementação da pilha.

 /* estrutura que representa a pilha */
 struct pilha {
   struct elemento *topo;
   size_t n;
 };

 /* elemento constituinte da pilha */
 struct elemento {
   char *dados;
   struct elemento *outro;
 };

A função inicia prepara a pilha para ser a utilizada.

 void inicia(struct pilha *p) {
   if (p == NULL) return;           /* argumento inválido? */
   p->topo = NULL;
   p->n    = 0;
 }

A função vazia retorna um valor diferente de zero se a pilha estiver vazia.

 unsigned char vazia(struct pilha *p) {
   return !p || p->topo == NULL;
 }

A função tamanho retorna o número de elementos da pilha.

 size_t tamanho(struct pilha *p) {
   return p ? p->n : 0;
 }

A função push insere novos elementos na pilha. Note-se o processo de reserva de memória: a pilha, além de reservar espaço para novos nós, também reserva espaço para os dados.

 enum resultado push(struct pilha *p, char *dados) {
   struct elemento *e = NULL;
   if (dados == NULL || p == NULL) return FALHA;  /* args inválidos? */
 
   if ((e = (struct elemento*)malloc(sizeof(struct elemento))) == NULL)
     return FALHA;
 
   if ((e->dados = (char*)malloc((1+strlen(dados))*sizeof(char))) == NULL) {
     free(e);
     return FALHA;
   }
 
   strcpy(e->dados, dados);
   e->outro = p->topo;
   p->topo  = e;
   p->n++;
   return SUCESSO;
 }

Note-se que a função pop apenas liberta o espaço correspondente a um nó da pilha, não libertando o espaço dos dados.

 char *pop(struct pilha *p) {
   struct elemento *e = NULL;
   if (vazia(p)) return NULL;     /* pilha vazia? */
   e = p->topo;
   p->topo = p->topo->outro;
   p->n--;
   char *pd = e->dados;           /* ponteiro para os dados  */
   free(e);                       /* liberta nó (malloc em push) */
   return pd;
 }

Ver Também