Listas Encadeadas 01

Vamos fazer um exemplo de implementação de listas encadeadas ou ligadas utilizando como dado um numero inteiro

Implementaremos as seguintes operações:

1 - Insercao no Inicio da Lista 

2 - Remove elementos no Inicio da Lista

3 - Mostrar a lista 

4 - Mostra o ultimo elemento da Lista

5 - Conta a quantidade de elementos da Lista  

6 - insere um elemento no final da Lista

A estrutura a ser utilizada:

struct no{

 int info;

 struct no *lig;

};

typedef struct no *lista;

ou

 typedef no {

    int info;

    lista lig;

 } *lista ;

Desta forma temos:

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

struct no{

       int info;

       struct no *lig;

       };

typedef struct no *lista;

            

int main()

{ int x,op,cont;

  lista p,L,q;

  L = NULL;

  do{

     printf("\n 1 - Insercao no Inicio da Lista ");

     printf("\n 2 - Remove elementos no Inicio da Lista");

     printf("\n 3 - Mostrar a lista ");

     printf("\n 4 - Mostra o ultimo elemento da Lista ");

     printf("\n 5 - Conta a quantidade de elementos da Lista "); 

     printf("\n 6 - insere um elemento no final da Lista");

     printf("\n 7 - sair ");

     printf("\n Escolha uma opcao ");

     scanf("%d",&op);

     switch (op)

     { case 1: 

         printf(" Entre com um elemento ");

         scanf("%d",&x);

         p = (lista) malloc (sizeof(struct no));

         p->info = x;

         p->lig = L;

         L = p;

         break;

      case 2: 

         if (L!=NULL)         

           { p = L;

             printf("\n elemento removido foi = %d", p->info);

             L= p->lig;

             free(p);

           } else

             printf("\n a lista esta vazia "); 

           break;    

      case 3:  

          p=L;

          while (p!=NULL)

            { printf(" %d ", p->info);

              p=p->lig;

             }

           break;                                   

      case 4: 

          p=L;

          while (p->lig !=NULL)

            p = p->lig;

          printf(" \n Ultimo elemento = %d ",p->info);

            break;

      case 5:

          cont =0;

          p=L;

          while (p!=NULL)

           { cont++;

             p=p->lig;

           }

          printf(" \n A lista possui %d Elementos ",cont);

          break;

      case 6:

          printf(" Entre com um elemento ");

          scanf("%d",&x);

          q = (lista) malloc (sizeof(struct no));

          q->info = x;

          q->lig = NULL;  

          if (L==NULL)

            L = q;                              

            else

            { p =L;

              while (p->lig !=NULL)

                  p=p->lig;

              p->lig = q;

            }

           break;                             

   }// fim do switch

            

}while (op !=7);

return 0;    

}// fim do programa                

Um outro exemplo de pilha é fazer a leitura de uma frase e inverter somente as palavras.

Por exemplo: A casa da titia maria.
Invertendo as palavras temos: A asac ad aitit airam

A ideia aqui é percorrer a frase e obter os caracteres diferentes de espaço em branco e fazer a inserção numa pilha. 

Quando for encontrado outro espaço em branco ou chegou ao final da frase, os elementos da pilha são removidos.

Assim:


int main()
{ int op,i ;
  char x,frase[30];
  pilha *p;
  inicializa(p);      
  printf(" Entre com uma frase ");
  gets(frase);
  for(i=0; i<strlen(frase); i++)// percorre a frase
    { if (frase[i]!=' ') // se for não for branco faça push
        push(p,frase[i]);
        else         // se for branco remove todos os elementos 
        {            // da pilha
          while (!vazia(p))
            printf("%c",pop(p));
          printf("%c",frase[i]);
        }//fim do else 
    }// fim do for    
// depois de percorrido a frase pode ser que a pilha ainda esteja
// não vazia
    while (!vazia(p))
       printf("%c",pop(p));
getch();                       
} 

Outro exemplo de pilha: Transformação de um número inteiro para binário.

Neste caso, vamos realizar a leitura de um numero de dividir por 2 até que o seu quociente seja igual a zero.

Assim:


int main()
{ int n;
  pilha p;
  inicializa(&p);
  printf(" Entre com um numero em decimnal ");
  scanf("%d",&n);

  while (n != 0)
  {
    push(&p,n%2);
    n = n/2;
  }

  printf("\n A expressão em binario = ");

  while (!vazia(&p))
 printf("%d ",pop(&p));
  getch();
}

Olá, boa tarde

Uma aplicação inicial para pilhas é verificar se uma determinada frase é palíndromo.

Assim, uma palavra, ou frase é considerada um palíndromo quando pode ser lida tanto da direita para esquerda, como da esquerda para a direita.

Por exemplo:
SUBINOONIBUS
OVO
ANILINA
MATAM
SALAS

A solução deste problema se baseia no fato de que podemos realizar a leitura da palavra inserindo-a numa pilha.

Depois realizamos a remoção dos elementos comparando com o que foi lido anteriormente.

Assim podemos ter o seguinte código:

Vamos considerar que exista uma biblioteca chamada de pilha onde as funções primitivas estão armazenadas.

Assim:


int main()
{ int op, flag,i;
  char frase[30];
  pilha *p;
  inicializa(p);
  printf(" Entre com a frase a ser analisada\n ");
  gets(frase);
  printf("\n Mostrando a frase lida: %s ",frase);
// inserindo os dados na pilha
  for(i=0;i<strlen(frase);i++)
        push(p,frase[i]);

  i =0;
  flag = 1;
  // variavel logica que verifica qdo o elemento for diferente
  while (flag && i < strlen(frase))
   { // retiro elementos da pilha e comparo com os do vetor
        if (frase[i]!=pop(p))
          flag =0;
     i++;    
    }  
       
  if (flag==0)
     printf(" \n a frase %s não eh palindroma ",frase);
     else
     printf("\n a frase %s eh palindroma ",frase);
     
  fflush(stdin);
  getche();
}      

Olá, Boa tarde

Vamos implementar uma pilha usando alocação estática de memória, ou seja, uma struct contendo um vetor que armazena os seus elementos e um apontador de topo que irá controlar a pilha.

Este apontador topo será utilizado para verificar situação de pilha vazia e cheia, assim como na inserção e remoção dos elementos.

Neste caso temos:


#include <stdio.h>
#include <conio.h>
#define MAX 6
// o tamanho máximo da pilha = 6

typedef struct{
        int info[MAX];
        int topo;
        } pilha;
// definição da struct pilha
        
void inicializa(pilha *p)
{
   p->topo = -1;
}

//*************************************

int vazia(pilha *p)
{
  return (p->topo ==-1);
}
//*************************************
int cheia (pilha *p)
{
 return (p->topo == MAX-1);

}
//*************************************

void push(pilha *p, int x)
{ if (cheia(p))
printf(" ERRO: PILHA CHEIA \n ");
else
{ p->topo++;
  p->info[p->topo]= x;
}
}

int pop(pilha *p)
{int aux;
  if (vazia(p))
      printf(" ERRO: PILHA VAZIA \n");
else
{aux = p->info[p->topo];
 p->topo--;
        }

 return aux;// return p->info[--p->topo];
}

Uma sugestão para o programa Main que pode testar a pilha:


int main()
{ int x,op;
  pilha p;
  inicializa(&p);
  do{
    printf("\n 1 - insercao ");
    printf("\n 2 - remoção ");
    printf("\n 4 - sair ");
    printf("\n Escolha uma opção ");
    scanf("%d",&op);
    switch (op)
{ case 1 : printf("\n Entre com um elemento ");
     scanf("%d",&x);
   push(&p,x);
   break;
  case 2: if (!vazia(&p))
    printf("\nElemento removido foi %d ",pop(&p));
        else 
        printf("Erro: Pilha Vazia");
break;
   }
  }while (op!=4);
  return 0;
}