EstruturaDados Aula 10

Prévia do material em texto

ESTRUTURA DE DADOS
Aula 10 – Listas Duplamente Encadeadas 
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
if
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
if
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
1) Através de seu ponteiro ant, p apontava para o nó anterior cuja representação é: p->ant.
 
2) Esse endereço foi copiado para o ponteiro ant do próximo nó acessado por p->prox->ant. (linha verde)
 
3) Sendo assim, após a remoção de p, p->prox ->ant apontará para o nó anterior ao que foi removido.(seta azul)
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
int main()
{ int op, valor;
 struct listaDE *lista= NULL; //inicializa a lista duplamente encadeada 
 do
 { 
 system("cls");
 system("color 2f");
 cout<<"\n\n( () ) Alocacao Dinamica ( () )"; 
 cout<<"\n( )";
 cout<<"\n( 1- Insere no Inicio )"; 
 cout<<"\n( 2- Insere no Fim )"; 
 cout<<"\n( 3- Remove da Lista DE )"; 
 cout<<"\n( 4- Exibe a Lista DE IpF )";
 cout<<"\n( 5- Exibe a Lista DE TpF )"; 
 cout<<"\n( 6- Conta Nos da Lista DE )";cout<<"\n( 7- Libera a Lista DE )"; 
 cout<<"\n( 8- Sai )";
 cout<<"\n( Opcao: )";
 cout<<"\n( )"; 
 cout<<"\n( ( ) ) ( ( ) ) ( ( ) ) ( ( ) )\n";
 cin>>op; 
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
system("cls");system("color f2");
switch(op)
 { 
 case 1:cout<<"\nDigite valor a ser inserido: ";
 cin>>valor;
 lista = insere(lista, valor);
 break;
 case 2:cout<<"\nDigite valor a ser inserido: ";
 cin>>valor;
 lista = insereFim(lista, valor);
 break; 
 
 case 3:if(!lista)
 cout << "\n\nNada a remover. Lista vazia\n";
 else 
 {
 cout<<"\nDigite valor a ser removido: "; cin>>valor; 
 lista=remove(lista, valor); 
 }
 break; 
 
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
 case 4: if(!lista)
 cout << "\n\nLista vazia\n";
 else 
 exibeIpF(lista);
 break; 
 
 case 5: if(!lista)
 cout << "\n\nLista vazia\n";
 else 
 exibeFpI(lista);
 break; 
case 6:if(!lista)
 cout << "\n\nLista vazia\n";
 else 
 cout<<"\nTotal de nos: "<< contaNos(lista);
 break; 
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
case 7: if(lista)
 cout<<"\nTem elementos na Lista\n";
 else
 { 
 libera(lista);
 cout<<"\nLiberando Memoria";
 } 
 break; 
 
 case 8: cout<<"Fechando Lista Duplamente Encadedada\n"; 
 break; 
 
 default:cout<<"\nOpcao Invalida\n";
 }
 cout<<"\n\n"; 
 system("pause");
 } while(op !=8);
 return 0;
} 
 
 
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
// insere no início 
listaDE *insere(listaDE *LISTA, int valor)
{
 listaDE* novo = new listaDE;
 novo->info = valor;
 novo->prox = LISTA;
 novo->ant = NULL;
 
 if (LISTA) 
 { 
 LISTA->ant = novo;
 } 
 return novo;
}
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
//insere no fim
listaDE *insereFim(listaDE *LISTA, int valor)
{
 listaDE *novo, *aux;
 novo = new listaDE;
 novo->info = valor;
 novo->prox = NULL;
 if (LISTA == NULL)
 {
 novo->ant = LISTA; LISTA = novo;
 }
 else
 {
 aux = LISTA;
 while (aux->prox != NULL)
 aux = aux->prox;
 aux->prox = novo;
 novo->ant = aux;
 }
 return LISTA;
}
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
// exibe lista IpF
void exibeIpF(listaDE *LISTA)
{
 listaDE* ptr;
 cout<<"\nExibe a lista do primeiro para o ultimo\n"; 
 for (ptr=LISTA; ptr != NULL; ptr=ptr->prox) 
 cout<<"\n"<<ptr->info;
}
 
// exibe lista TpF
void exibeFpI(listaDE *LISTA)
{
 listaDE* ptr=LISTA;
 cout<<"\nExibe a lista do ultimo para o primeiro \n"; 
 while(ptr->prox) { ptr=ptr->prox; }
 while(ptr!=LISTA)
 { 
 cout<<"\n"<<ptr->info;
 ptr=ptr->ant;
 } 
 cout<<"\n"<<ptr->info;
}
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
// remove um elemento da lista 
listaDE *remove(listaDE* LISTA, int valor)
{
 listaDE *p = busca(LISTA,valor);
 if (!p)
 { 
 cout<< "\nValor nao achado\n"; 
 return LISTA;
 } // nao achou o elemento
 // retira elemento do encadeamento 
 if (LISTA == p)
 LISTA = p->prox; 
 else
 p->ant->prox = p->prox;
 if (p->prox )
 p->prox->ant = p->ant;
 cout<<"\nValor removido\n";
 delete p;
 return LISTA;
}
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
// busca valor na lista
listaDE *busca (listaDE *LISTA, int valor)
{
 listaDE *ptr;
 for (ptr=LISTA; ptr != NULL; ptr=ptr->prox)
 if (ptr->info == valor)
 return ptr;
 return NULL; // nao achou o elemento 
}
//conta nós da Lista
int contaNos(listaDE *LISTA)
{
 int conta = 0;
 while (LISTA != NULL) 
 {
 conta++;
 LISTA = LISTA->prox;
 }
 return conta;
}
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
//libera
void libera(listaDE *LISTA)
{
 delete LISTA; LISTA=0;
} 
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
#include <iostream>
#include <cstdlib>
using namespace std;
struct listaDE 
{
 int info;
 listaDE* ant;
 listaDE* prox;
};
struct DE
{
 int tam;
 listaDE* prim;
 listaDE* ult;
};
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
//Protótipos
DE *insereFim(DE *ptrDesc, int valor);
DE *insereInicio(DE *ptrDesc, int valor);
void exibeIpF(DE *ptrDesc);
void exibeTpF(DE *ptrDesc);
void libera(DE *ptrDesc);
void removerFim(DE *ptrDesc);
void removerInicio(DE *ptrDesc);
int main()
{ 
 int op, valor;
 //inicializa a lista duplamente encadeada 
 DE *ptrDesc=new DE;
 ptrDesc->prim=NULL;
 ptrDesc->ult=NULL;
 ptrDesc->tam=0; 
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
 do
 { 
 system("cls"); system("color 2f");
 cout<<"\n\n( () ) Alocacao Dinamica ( () )"; 
 cout<<"\n( )";
 cout<<"\n( 1- Insere no Inicio )"; 
 cout<<"\n( 2- Insere no Fim )"; 
 cout<<"\n( 3- Remove no Inicio )"; 
 cout<<"\n( 4- Remove no Fim )"; 
 cout<<"\n( 5- Exibe a Lista DE IpF )";
 cout<<"\n( 6- Exibe a Lista DE TpF )"; 
 cout<<"\n( 7- Libera a Lista DE )"; 
 cout<<"\n( 8- Sai )";
 cout<<"\n( Opcao: )";
 cout<<"\n( )"; 
 cout<<"\n( ( ) ) ( ( ) ) ( ( ) ) ( ( ) )\n";
 cin>>op;
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
system("cls"); system("color f2");
switch(op)
{ 
 case 1:cout<<"\nDigite valor a ser inserido no Inicio: "; cin>>valor;
 ptrDesc=insereInicio(ptrDesc, valor);
 break; 
 
 case 2:cout<<"\nDigite valor a ser inserido no Fim: "; cin>>valor;
 ptrDesc=insereFim(ptrDesc, valor);
 break; 
 
 case 3: if(ptrDesc->tam == 0)
 cout << "\n\nLista vazia\n";
 else 
 removerInicio(ptrDesc); 
 break; 
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
 case 4: if(ptrDesc->tam == 0)
 cout << "\n\nLista vazia\n";
 else 
 removerFim(ptrDesc); 
 break; 
 
 case 5: if(ptrDesc->tam == 0)
 cout << "\n\nLista vazia\n";
 else 
 exibeIpF(ptrDesc);
 break; 
 case 6: if(ptrDesc->tam == 0)
 cout << "\n\nLista vazia\n";
 else 
 exibeTpF(ptrDesc); 
 break; 
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
 case 7: if(ptrDesc->tam != 0)
 cout<<"\nTem elementos na Lista\n";
 else
 { 
 libera(ptrDesc); cout<<"\nLiberando Memoria";
 } 
 break;
 
 case 8: cout<<"Fechando Lista Duplamente Encadedada\n"; 
 break; 
 
 default: cout<<"\nOpcao Invalida\n";
 }
 cout<<"\n\n"; system("pause");
 } while(op !=8);
 return 0;
} 
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
//insere no inicio
DE *insereInicio(DE *ptrDesc, int valor)
{ listaDE *ptAux=new listaDE;if (ptAux != NULL)
 { //verifica se existe memória disponível
 ptAux->info = valor;
 ptAux->prox = ptrDesc->prim;
 ptAux->ant = NULL;
 ptrDesc->tam=ptrDesc->tam+1;
 if (ptrDesc->prim != NULL)
 { ptrDesc->prim->ant = ptAux; } 
 else
 { ptrDesc->ult = ptAux; } //ajusta ponteiro para fim 
 ptrDesc->prim=ptAux;//ajusta ponteiro início
 return ptrDesc; 
 }
 else{ cout<<"\nSem memoria\n"; exit(-1);}
 }
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
//insere no fim
DE *insereFim(DE *ptrDesc, int valor)
{ listaDE *ptAux=new listaDE;
 listaDE *ptUlt;
 ptAux->info = valor;
 ptAux->prox = NULL;
 ptrDesc->tam=ptrDesc->tam+1; 
 if (ptrDesc->ult == NULL)
 {
 ptrDesc->ult=ptAux;
 ptrDesc->prim=ptrDesc->ult;
 ptAux->ant=NULL;
 }
 else
 {
 ptUlt=ptrDesc->ult;
 ptUlt->prox=ptAux;
 ptAux->ant=ptUlt;
 ptrDesc->ult=ptAux;
 }
 return ptrDesc;
}
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
//remove do inicio
void removerInicio(DE *ptrDesc)
{
 listaDE *aux=new listaDE;
 
 if (ptrDesc->prim == ptrDesc->ult)
 { //lista com um elemento
 aux->info=ptrDesc->prim->info;
 ptrDesc->prim = NULL;
 ptrDesc->ult = NULL;
 ptrDesc->tam=ptrDesc->tam - 1; 
 } 
 else 
 { //lista com mais de um elemento
 aux->info=ptrDesc->prim->info;
 ptrDesc->prim->prox->ant = NULL;
 ptrDesc->prim = ptrDesc->prim->prox;
 ptrDesc->tam=ptrDesc->tam - 1; 
 }
 cout<<"\nRemovido: "<<aux->info;
}
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
//remove do fim
void removerFim(DE *ptrDesc)
{
 listaDE *aux=new listaDE;
 
 if (ptrDesc->prim == ptrDesc->ult)
 { //lista com um elemento
 aux->info=ptrDesc->prim->info;
 ptrDesc->prim = NULL;
 ptrDesc->ult = NULL;
 ptrDesc->tam=ptrDesc->tam - 1; 
 } 
 else 
 { //lista com mais de um elemento
 aux->info=ptrDesc->ult->info;
 ptrDesc->ult->ant->prox = NULL; 
 ptrDesc->ult = ptrDesc->ult->ant;
 ptrDesc->tam=ptrDesc->tam - 1;
 }
 cout<<"\nRemovido: "<<aux->info;
}
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
// exibe lista IpF
void exibeIpF(DE *ptrDesc)
{
 listaDE* ptr=ptrDesc->prim;
 cout<<"\nExibe a lista do primeiro para o ultimo\n"; 
 for (int i=1; i<=ptrDesc->tam; i++) 
 { 
 cout<<"\n"<<ptr->info;
 ptr=ptr->prox;
 }
}
// exibe lista TpF
void exibeTpF(DE *ptrDesc)
{
 listaDE* ptr=ptrDesc->ult;
 cout<<"\nExibe a lista do ultimo para o primeiro \n"; 
 for (int i=ptrDesc->tam; i>=1; i--) 
 { 
 cout<<"\n"<<ptr->info;
 ptr=ptr->ant;
 }
}
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
//libera
void libera(DE *ptrDesc)
{
 delete ptrDesc; ptrDesc=0;
}