Baixe o app para aproveitar ainda mais
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; }
Compartilhar