Estrutura de Dados - Aula 10

Prévia do material em texto

ESTRUTURA DE DADOS
Aula 10 – Listas Duplamente Encadeadas
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
Atenção aos Temas Principais dessa Aula
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
Conteúdo Programático desta aula
 Compreender o conceito de Lista Duplamente
Encadeada;
 Compreender operaões com LDE sem ou com
descritor;
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
Direto ao Assunto
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
Nas listas duplamente ligadas, cada nó possui dois
ponteiros, sendo que um aponta para o nó anterior e o
outro, para o nó posterior. Sendo assim, a lista pode ser
“percorrida” começando por qualquer extremidade.
Um ponteiro ant aponta para o nó que precede enquanto
que o ponteiro prox, aponta para o nó que o sucede.
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
Os algoritmos de algumas operações com LDE(listas
ligadas) têm um certo grau de complexidade, mas
facilitam na manipulação da LDE.
A LDE é indicada quando precisarmos percorrer a lista
do fim para o início.
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
Quando usamos LDE sem descritor, as funções básicas de
inserção, remoção, busca, conta nós e impressão, quase
não têm diferença para as LE exceto pelo ponteiro anterior.
Não existe a necessidade de dimensionar o número de nós
porque a alocação vai sendo feita de acordo com a
necessidade.
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
Criar lista
Liberar lista
Verificar se a lista está vazia
Inserir na primeira posição
Inserir na última posição
Remover o primeiro elemento da lista
Remover o último elemento da lista
Remover um elemento por busca
Exibir lista do primeiro para o último nó
Exibir lista do último para o primeiro nó
Contar número de nós, etc.
Algumas operações realizadas com uma LDE
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
struct listaDE
{
int info;
struct listaDE* ant;
struct listaDE* prox;
};
Definido a struct
Para entendimento das funções
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
Inicialização
listaDE *lista= NULL;
Definido a struct
Para entendimento das funções
struct listaDE
{
int info;
struct listaDE* ant;
struct listaDE* prox;
};
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereInicio
novo
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereInicio
novo
23
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereInicio
novo
23 LISTA
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereInicio
novo
NULL 23 LISTA
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereInicio
novo
NULL 23 LISTA
LISTA
if
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereInicio
novo
NULL 23 LISTA
LISTAlista = insere(lista, valor);
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereInicio
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereFim
novo
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereFim
novo
23
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereFim
novo
NULL23
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereFim
novo
NULL23LISTA
if
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereFim
novo
NULL23LISTA
LISTA
if
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereFim
novo
NULL23
aux
LISTAelse
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereFim
novo
NULL23
aux
LISTA
novo
else
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereFim
novo
NULL23aux
aux
LISTA
novo
else
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereFim
novo
NULL23aux
aux
LISTA
novo
else
lista = insere(lista, valor);
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereFim
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
exibeIpF
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
exibeIpF
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
exibeFpI
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
exibeFpI
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
contaNós
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
contaNós
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
busca
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
remove
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
remove
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
remove
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
A REMOÇÃO DE UM NÓ - Um ponto crítico nas LDE
p->ant->prox = p->prox;
p->prox->ant = p->ant;
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
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
1) Através de seu ponteiro prox, p apontava para o próximo
nó cuja representação é: p->prox.
2) Esse endereço foi copiado para o ponteiro prox do nó
anterior acessado por p->ant->prox. (linha verde)
3) Sendo assim, após a remoção de p, p->ant->prox
apontará para o nó seguinte ao que foi removido.(seta azul)
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
1) Através de seu ponteiro prox, p apontava para o próximo
nó cuja representação é: p->prox.
2) Esse endereço foi copiado para o ponteiro prox do nó
anterior acessado por p->ant->prox. (linha verde)
3) Sendo assim, após a remoção de p, p->ant->prox
apontará para o nó seguinte ao que foi removido.(seta azul)
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
O nó descritor é criado para fazer referências ao primeiro
e/ou ao ultimo nó. Por essa razão, seu uso facilita o
acesso aos nós da lista. Seja para inserir, no início ou no
fim, remover, do início ou do fim, etc.
Como o nó descritor pode conter, também, outras
informações, optei por ter o total de nós da lista.
A única preocupação fica em ter que atualizá-lo na
inserção e na remoção de um nó na lista, uma vez que o
acesso a um nó da lista será feito através dele.
DESCRITOR
ESTRUTURA DE DADOSListas Duplamente Encadeadas– Aula10
struct listaDE
{
int info;
struct listaDE* ant;
struct listaDE* prox;
};
1) Definindo a struct
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
struct DE
{
int tam;
listaDE* prim;
listaDE* ult;
};
2) Definindo a struct
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
DE *ptrDesc=new DE;
ptrDesc->prim=NULL;
ptrDesc->ult=NULL;
ptrDesc->tam=0;
3) Inicialização
NULL NULL0
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereInicio
ptAux
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereInicio
ptAux
23
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereInicio
ptAux
23
ptrDesc
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereInicio
ptAux
NULL 23
ptrDesc
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereInicio
ptAux
NULL 23
ptrDesc
+=1
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereInicio
ptAux
NULL 23
ptrDesc
+=1NULL ?
if
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereInicio
ptAux
NULL 23
ptrDesc
+=1
if
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereInicio
ptAux
NULL 23
ptrDesc
+=1
else
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereInicio
ptAux
NULL 23
ptrDesc
+=1
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereInicio
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereFim
ptAux
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereFim
ptAux
23
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereFim
ptAux
NULL23
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereFim
ptAux
ptrDesc
NULL23
+=1
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereFim
ptAux
ptrDesc
NULL23
+=1
if
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereFim
ptAux
ptrDesc
NULL23
+=1
if
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereFim
ptAux
ptrDesc
NULL23
+=1
if
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereFim
ptAux
ptrDesc
NULL23
+=1
if
NULL
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereFim
ptUlt
ptrDesc
+=1
else
ptAux
NULL23
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereFim
ptUlt
ptrDesc
+=1
else
ptAux
NULL23
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereFim
ptUlt
ptrDesc
+=1
else
ptAux
NULL23
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereFim
ptUlt
ptrDesc
+=1
else
ptAux
NULL23
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereFim
ptUlt
ptrDesc
+=1
else
ptAux
NULL23
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
insereFim
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
Exibe Inicio - Fim
ptrDesc
ptr
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
Exibe Inicio - Fim
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
Exibe Fim – Inicio
ptrDesc
ptr
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
Exibe Fim – Inicio
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
removeInicio
aux
ptrDesc
if
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
removeInicio
aux
ptrDesc
if
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
removeInicio
aux
ptrDesc
if
NULL
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
removeInicio
aux
ptrDesc
if
NULL NULL
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
removeInicio
aux
ptrDesc
if
NULL-=1NULL
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
removeInicio
aux
ptrDesc
if
NULL0NULL
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
removeInicio
aux
ptrDesc
else
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
removeInicio
aux
ptrDesc
else
NULL
prim
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
removeInicio
aux
ptrDesc
else
NULL
prim
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
removeInicio
aux
ptrDesc
else
NULL
prim
-=1
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
removeInicio
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
removeFim
aux
ptrDesc
if
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
removeFim
aux
ptrDesc
if
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
removeFim
aux
ptrDesc
if
NULL
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
removeFim
aux
ptrDesc
if
NULL NULL
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
removeFim
aux
ptrDesc
if
NULL NULL-=1
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
removeFim
aux
ptrDesc
if
NULL NULL0 
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
removeFim
aux
ptrDesc
else
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
removeFim
aux
ptrDesc
else
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
removeFim
aux
ptrDesc
else
NULL
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
removeFim
aux
ptrDesc
else
NULL
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
removeFim
aux
ptrDesc
else
NULL
-=1
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
removeFim
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
Libera
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
Resumindo
ESTRUTURA DE DADOS
Listas Duplamente Encadeadas– Aula10
Menu LDE sem Descritor
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
Menu LDE com Descritor
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