08_ListaDuplamenteEncadeada

Prévia do material em texto

LISTAS DUPLAMENTE ENCADEADAS: LISTAS DUPLAMENTE ENCADEADAS: 
ESTÁTICAS E DINÂMICASESTÁTICAS E DINÂMICAS
.: ESTRUTURA DE DADOS :..: ESTRUTURA DE DADOS :.
André Macedo SantanaAndré Macedo SantanaAndré Macedo SantanaAndré Macedo SantanaAndré Macedo SantanaAndré Macedo SantanaAndré Macedo SantanaAndré Macedo Santana
andremacedo@ufpi.edu.br
ListasListas DuplamenteDuplamente EncadeadasEncadeadas EstáticasEstáticas
• As listas simplesmente encadeadas apresentam um limitação pois não permitem
a realização de buscas nos dois sentidos uma vez que a estrutura contém apenas
uma referência para o próximo elemento. Esse fato também dificulta a retirada
de uma elemento da lista, pois não temos a informação de que precede um
determinado nó de forma direta.
• Para solucionar os problemas apresentados, podemos implementar o conceito
de listas duplamente encadeadas incluindo uma nova variável na estrutura Nó
ConceitosConceitos
André M. Santana UFPI - CCN - DIEEstruturas de Dados
de listas duplamente encadeadas incluindo uma nova variável na estrutura Nó
para armazenar o endereço do Nó precedente, permitindo dessa forma, um
caminhamento em ambos os sentidos da lista.
• uma variável de estrutura (info);
• Uma variável ponteiro (prox)
Lista Duplamente Encadeada
Procedimentos básicos:
• inicializar lista;
• alocar um nó;
• inserir um nó;
• excluir um nó;
ListasListas DuplamenteDuplamente EncadeadasEncadeadas EstáticasEstáticas
EstruturaEstrutura e e OperaçõesOperações
André M. Santana UFPI - CCN - DIEEstruturas de Dados
• A inicialização de uma lista duplamente encadeada é semelhante à foram que
inicializamos as listas simplesmente encadeadas. Essa rotina, inicializar_ltd(),
realiza o encadeamento prévio do vetor e armazena o valor -1 no último nó do
vetor para informa que ali é o fim da estrutura;
ListasListas DuplamenteDuplamente EncadeadasEncadeadas EstáticasEstáticas
OperaçõesOperações: : InicializarInicializar
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Inicializar lista
• A função alocaNo_ltd() é responsável pela alocação do nó que será inserido na
lista. Após a obtenção do endereço do novo nó, a variável disp recebe o próximo
disponível da lista para futuras alocações;
ListasListas DuplamenteDuplamente EncadeadasEncadeadas EstáticasEstáticas
OperaçõesOperações: : AlocarAlocar NóNó
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Alocar um Nó
• Uma vez inicializada a lista [ inicializar_ltd() ] bem como a alocação de um nó da
lista [alocaNo_ltd() ], podemos fazer então a inserção de uma elemento;
ListasListas DuplamenteDuplamente EncadeadasEncadeadas EstáticasEstáticas
OperaçõesOperações: : InserirInserir NóNó
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Inserir um Nó 
• Diferentemente da rotina de eliminação das listas encadeadas onde temos que
informar o Nó anterior ao qual será removido, aqui basta informar apenas o
endereço do próprio Nó de remoção;
Desaloca Nó
ListasListas DuplamenteDuplamente EncadeadasEncadeadas EstáticasEstáticas
OperaçõesOperações: Remover : Remover NóNó
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Remover Nó
EXERCÍCIOSEXERCÍCIOS
ListasListas DuplamenteDuplamente EncadeadasEncadeadas EstáticasEstáticas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
ListasListas DuplamenteDuplamente EncadeadasEncadeadas DinâmicasDinâmicas
• Nas listas duplamente encadeadas dinâmicas cada elemento têm um ponteiro
para o próximo elemento e para o elemento anterior. Assim, dado um elemento,
podemos acessar os dois elementos adjacentes: o próximo e o anterior.
ConceitosConceitos e e EstrturaEstrtura
André M. Santana UFPI - CCN - DIEEstruturas de Dados
• Lista Duplamente Encadeada Dinâmica
OperaçõesOperações: : InserirInserir [[ListaLista com com DescritorDescritor]]
Inserir no início
ListasListas DuplamenteDuplamente EncadeadasEncadeadas DinâmicasDinâmicas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Inserir no meio
Inserir no fim
OperaçõesOperações: : InserirInserir [[ListaLista semsem DescritorDescritor] ] 
Inserir no início
ListasListas DuplamenteDuplamente EncadeadasEncadeadas DinâmicasDinâmicas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Inserir no meio
Inserir no fim
OperaçõesOperações: : InserirInserir no no inicioinicio
ListasListas DuplamenteDuplamente EncadeadasEncadeadas DinâmicasDinâmicas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Inserir no inicio [Lista com Descritor]
OperaçõesOperações: : InserirInserir no no inicioinicio
ListasListas DuplamenteDuplamente EncadeadasEncadeadas DinâmicasDinâmicas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Inserir no inicio [Lista sem Descritor]
OperaçõesOperações: : InserirInserir no no meiomeio
ListasListas DuplamenteDuplamente EncadeadasEncadeadas DinâmicasDinâmicas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Inserir no meio [Lista com Descritor]
OperaçõesOperações: : InserirInserir no no meiomeio
ListasListas DuplamenteDuplamente EncadeadasEncadeadas DinâmicasDinâmicas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Inserir no meio [Lista sem Descritor]
OperaçõesOperações: : InserirInserir no no fimfim
ListasListas DuplamenteDuplamente EncadeadasEncadeadas DinâmicasDinâmicas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Inserir no fim [Lista com Descritor]
OperaçõesOperações: : InserirInserir no no fimfim
ListasListas DuplamenteDuplamente EncadeadasEncadeadas DinâmicasDinâmicas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Inserir no fim [Lista sem Descritor]
• O código a seguir mostra uma possível implementação da função que insere
novos elementos no início da Lista. Assim, o elementos inserido tem como
próximo elemento o antigo primeiro elemento e como anterior o valor NULL;
AlgoritmoAlgoritmo: : InserirInserir NóNó
ListasListas DuplamenteDuplamente EncadeadasEncadeadas DinâmicasDinâmicas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Inserir no início
OperaçõesOperações: : ExcluirExcluir [[ListaLista com com DescritorDescritor]]
Excluir no início
ListasListas DuplamenteDuplamente EncadeadasEncadeadas DinâmicasDinâmicas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Excluir no meio
Excluir no fim
OperaçõesOperações: : ExcluirExcluir [[ListaLista semsem DescritorDescritor]]
Excluir no início
ListasListas DuplamenteDuplamente EncadeadasEncadeadas DinâmicasDinâmicas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Excluir no meio
Excluir no fim
OperaçõesOperações: : ExcluirExcluir no no inicioinicio
ListasListas DuplamenteDuplamente EncadeadasEncadeadas DinâmicasDinâmicas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Excluir no inicio [Lista com Descritor]
OperaçõesOperações: : ExcluirExcluir no no inicioinicio
ListasListas DuplamenteDuplamente EncadeadasEncadeadas DinâmicasDinâmicas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Excluir no inicio [Lista sem Descritor]
OperaçõesOperações: : ExcluirExcluir no no meiomeio
ListasListas DuplamenteDuplamente EncadeadasEncadeadas DinâmicasDinâmicas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Excluir no meio [Lista com Descritor]
OperaçõesOperações: : ExcluirExcluir no no meiomeio
ListasListas DuplamenteDuplamente EncadeadasEncadeadas DinâmicasDinâmicas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Excluir no meio [Lista sem Descritor]
OperaçõesOperações: : ExcluirExcluir no no fimfim
ListasListas DuplamenteDuplamente EncadeadasEncadeadas DinâmicasDinâmicas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Excluir no fim [Lista com Descritor]
OperaçõesOperações: :ExcluirExcluir no no fimfim
ListasListas DuplamenteDuplamente EncadeadasEncadeadas DinâmicasDinâmicas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Excluir no fim [Lista sem Descritor]
• A função consultar_ltd2() recebe a informação referente ao elemento que
queremos buscar e tem como valor de retorno o ponteiro do Nó da lista que
representa o elemento. Caso o elemento não seja encontrado, o retorno é NULL;
AlgoritmoAlgoritmo: : ConsultarConsultar
ListasListas DuplamenteDuplamente EncadeadasEncadeadas DinâmicasDinâmicas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Consultar
• A função excluir_ltd2() é um pouco mais complicada, pois temos de acertar o
encadeamento duplo. Em contrapartida, podemos retirar o elemento da lista se
conhecermos apenas o ponteiro para esse elemento;
OperaçõesOperações: : ExcluirExcluir NóNó
ListasListas DuplamenteDuplamente EncadeadasEncadeadas DinâmicasDinâmicas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Excluir Nó
• Lista Circular Duplamente Encadeada:
• O que seria o último elemento da lista passa a ter como próximo o primeiro
elemento, que, por sua vez, passa a ter o último como anterior;
• Lista de Tipos Estruturados:
• São listas onde o campo “info” é uma estrutura.
OutrosOutros
ListasListas DuplamenteDuplamente EncadeadasEncadeadas DinâmicasDinâmicas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
• São listas onde o campo “info” é uma estrutura.
• Independente da informação armazenada e da forma como ela é
representada internamente, o encadeamento dos elementos da lista não é
alterado;
Cuidado: se o elemento “info” for um ponteiro para uma estrutura, devemos
lembrar de alocar a estrutura antes de alocar o nó da lista;
• A representação da informação por um ponteiro permite construir listas
heterogêneas, isto é, listas em que as informações armazenadas diferem de Nó
para Nó.
• Exemplo: Lista de figuras geométricas
Tipo Triangulo: base(b), altura(h);
Tipo Quadrado: lado(l);
ListasListas HeterogêneasHeterogêneas
ListasListas DuplamenteDuplamente EncadeadasEncadeadas DinâmicasDinâmicas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Tipo Circulo: raio(r);
• Logo, o Nó da lista deve então ser composto por três campos:
• Um identificador de qual objeto está armazenado no Nó;
• Um ponteiro para a estrutura que contém a informação (void*);
• Ponteiros de encadeamento;
EXERCÍCIOSEXERCÍCIOS
ListasListas DuplamenteDuplamente EncadeadasEncadeadas DinâmicasDinâmicas
André M. Santana UFPI - CCN - DIEEstruturas de Dados