Publicidade cabeçário

segunda-feira, 8 de abril de 2013

Estrutura de Dados - Lista Dinâmica Dupla

Fala pessoal mais uma super lista pra animar o começo da semana. Pra quem gosta da frase: " Poderia ser pior" acreditem é verdade! Depois do terror da lista dinâmica, agora vamos trabalhar com a Lista Dinâmica Dupla ou Lista Duplamente Encadeada! 


Morre Diabo!
Morre Diabo!

Existem algumas variações das listas encadeadas:

  • Lista Duplamente Encadeada com sentinelas;
  • Lista Duplamente Encadeada Circular.
Características da Lista Duplamente Encadeada com sentinelas:
  • Ela possui Cabeça e Último, sendo que cada nó tem 2 ponteiros: um que aponta para o antecessor e outro que aponta pro sucessor;
  • A cabeça e o último apontam pra NULL, uma com seu antecessor e a outra com seu sucessor.
Figura 1 : Lista Duplamente Encadeada com sentinelas
Figura 1 : Lista Duplamente Encadeada com sentinelas
fonte da imagem: bdfatec.blogspot.com.br

Características Lista Duplamente Encadeada Circular:
  • A cabeça aponta pro ultimo e vice-versa;
Figura 2: Lista Duplamente Encadeada Circular
Figura 2: Lista Duplamente Encadeada Circular
fonte da imagem: bdfatec.blogspot.com.br

Bom, agora chega de teoria e vamos ao programa. Primeiramente os métodos da lista, que tem como menu 
1 - Criar Lista Vazia
2 - Inserir no início
3 - Inserir no final
4 - Exibir todos os valores da lista
5 - Exibir todos os valores da lista ao contrário
6 - Inserir nó na segunda posição
7 - Eliminar nó da segunda posição

#include<conio.h>
#include<windows.h>
#include<stdio.h>

struct no{
       int info;
       no *prox;
       no *ant;
       }; no *cabeca;
       
void CriarListaVazia(){
     cabeca = NULL;
     printf("\n\t Lista criada com sucesso!");
     getch();
     }//fim CriarListaVazia

void InserirInicio(){
     int valor;
     no *novo;
     
     printf("\n\t Digite o valor do no.:");
     scanf("%d",&valor);
     
     novo = (no*)malloc(sizeof(no));
     novo -> info = valor;
     novo -> ant = NULL;
     novo -> prox = cabeca;
     if(cabeca != NULL){
     cabeca -> ant = novo; 
     }   
     cabeca = novo;
     printf("\n\t Valor inserido com sucesso!!");     
     }//fim  InserirInicio  

void InserirSegundaPosicao(){
     int valor;
     no *segundo;
     
     printf("\n\t Digite o valor do SEGUNDO no.:");
     scanf("%d",&valor);
     
     segundo = (no*)malloc(sizeof(no));
     segundo -> info = valor;
     segundo -> ant = cabeca;
     segundo -> prox = cabeca -> prox;
     cabeca -> prox = segundo;
     printf("\n\t Valor inserido com sucesso!!");                 
     }// fim InserirSegundaPosicao

void EliminarSegundaPosicao(){
     int valor;
     no *segundo, *aux;
     
     segundo= cabeca -> prox;
     aux = segundo -> prox;
     free(segundo);
     
     aux -> ant = cabeca;
     cabeca -> prox = aux;
     
     printf("\n\t Valor apagado com sucesso!!");                 
     }// fim EliminarSegundaPosicao
         
void InserirFinal(){
     int valor;
     no *novo,*aux;
     
     printf("\n\t Digite o valor do no.:");
     scanf("%d",&valor);
     
     novo = (no*)malloc(sizeof(no));
     novo-> info = valor;
     novo->prox = NULL;
     
     if(cabeca == NULL){
cabeca = novo;
}else{
aux = cabeca;
while(aux->prox != NULL){
aux = aux->prox;
}//fim while
aux->prox = novo;
novo->ant = aux;
}//fim if
     printf("\n\t Valor inserido com sucesso!!");
     }//InserirFinal

void Imprime(){
no *pAux;
int nCont=0;
pAux = cabeca;
printf("\n\nPercorrendo a Lista e exibindo os valores \n\n ");
while(pAux != NULL){
nCont++;
printf("\n elemento %d : %d",nCont,pAux->info);
pAux = pAux->prox;
}//fim while
}// fim Imprime

void ImprimeInvertido(){
    no *aux;
int nCont=0;
aux = cabeca;
      while(aux->prox != NULL){
aux = aux->prox;
}//fim while
     
      do{
        nCont++;
        printf("\n elemento %d : %d",nCont,aux->info);
        aux = aux->ant;
   }while(aux!= NULL);
     }//fim ImprimeInvertido

E agora nosso main com o menu.


     main(){
            int nOpc;
            
            do{
                printf("----------------------- Menu --------------------------------");
                printf("\n\n\t1 - Criar Lista");
                printf("\n\t2 - Inserir no Inicio da Lista");
                printf("\n\t3 - Inserir no final da Lista");
                printf("\n\t4 - Exibir todos os valores da lista");
                printf("\n\t5 - Exibir todos os valores da lista ao contrario");
                printf("\n\t6 - Inserir na 2 posicao da lista");
                printf("\n\t7 - Eliminar o NO da 2 posicao da lista");
                printf("\n\t0 - Sair");
                printf("\n\nDigite a opcao desejada: ");
                scanf("%d",&nOpc);
               
                switch(nOpc){
                             case 0:
                             printf("\n\nObrigado por utilizar o programa\n\n Pressione ENTER para sair...");
                             break;  
                             case 1:
                             CriarListaVazia();
                             printf("\n\n Pressione ENTER para continuar...");
                             break;
                             case 2:
                             InserirInicio();
                             printf("\n\n Pressione ENTER para continuar...");
                             break;
                             case 3:
                             InserirFinal();
                             printf("\n\n Pressione ENTER para continuar...");
                             break;
                             case 4:
                             Imprime();
                             printf("\n\n Pressione ENTER para continuar...");
                             break;
                             case 5:
                             ImprimeInvertido();
                             printf("\n\n Pressione ENTER para continuar...");
                             break;
                             case 6:
                             InserirSegundaPosicao();
                             printf("\n\n Pressione ENTER para continuar...");
                             break;
                             case 7:
                             EliminarSegundaPosicao();
                             printf("\n\n Pressione ENTER para continuar...");
                             break;
                             default:
                             printf("\n\n Item invalido!!! \n\nPressione ENTER para continuar...");
                             break;        
                             }//fim switch
                               
                    getch();
       system("cls");
                  }while(nOpc != 0);                      
            }//fim main

Figura 3: Menu com Lista Dinâmica Encadeada com Sentinelas
Figura 3: Menu com Lista Dinâmica Encadeada com Sentinelas
fonte da imagem: bdfatec.blogspot.com.br
Bom é isso pessoal, bons estudos e boa semana a todos!

fonte : < Profº Jean Daniel - Estrutura de Dados >
adaptado: Arroyo, Gabriel

Gostou do blog? Então segue =D 
Gostou da postagem? Então comenta ;DDD 
Fique por dentro das atualizações