(Parte 1 de 2)

CursoSuperior de Tecnologia emTelemática Programação e Estruturas de Dados

Listas Lineares Duplamente Encadeadas

Copyright©2010 Prof. CésarRocha cesarocha@ifpb.edu.br

Objetivos

§Explorar conceitos importantes acerca das listas listas duplamente encadeadasduplamente encadeadasutilizando a linguagem C

§Organização e implementação, características, vantagens e desvantagens, regras de utilização, operações básicas e os algoritmos de implementação

§Estas estruturas são um pouco mais complicadas que as listas encadeadas (módulo anterior)

§Contudo, tenta superar algumas limitações encontradas no TAD supracitado

§Este módulo também fará uso das regras de criação das bibliotecasbibliotecasem práticas de laboratório futuras

Motivação

§Você deve lembrar que a estrutura lista encadeada, vista no módulo anterior, caracterizava-se por um encadeamento simples entre os elementos

§Havia a alocação dinâmica de cada elemento

§Cada elemento armazenava um único ponteiropara o próximo elemento da lista

§Lembre-se que esta estrutura resolveu algumas das limitações encontradas nas listas seqüenciais

§Pré-dimensionamento da lista §Sub-utilização de memória

§Porém, você pode ter notado que...

Desvantagens Lista Encadeada

Em uma lista encadeada simples, não temos como percorrer eficientemente os elementos em ordemordem inversainversa, isto é, do final para o início da lista

O encadeamento simples também dificultava a remoçãoremoçãode um elemento da lista. Veja abaixo:

/* Parâmetros: lista = a lis dado = passa posição = pos

Retorno: 1 em caso de suce */ int removerElemento(TListaEnc*

TListaEnc aux; TListaEnc anterior; int contador; // verifica se a lista esta v if(listaVazia(lista)) return

Assim, mesmo quando sabíamos qual elemento íamos retirar, Assim, mesmo quando sabíamos qual elemento íamos retirar, tínhamos que percorrer a lista, elemento por elemento, até tínhamos que percorrer a lista, elemento por elemento, até encontrarmos o elemento anterior.encontrarmos o elemento anterior.

Isso se deve porque, dado um elemento, não tínhamos como Isso se deve porque, dado um elemento, não tínhamos como acessar diretamente o seu elemento anterior (ou antecessor) acessar diretamente o seu elemento anterior (ou antecessor) para redirecionar o ponteiro.para redirecionar o ponteiro.

Note, na função de remoção, que a solução encontrada foi Note, na função de remoção, que a solução encontrada foi declarar uma variável somente para podermos guardar o declarar uma variável somente para podermos guardar o endereço do nó anterior ao elemento a ser removido da lista.endereço do nó anterior ao elemento a ser removido da lista.

§Para solucionar esses problemas, podemos formar o que chamamos de listas duplamente encadeadaslistas duplamente encadeadas

§Semelhante à lista encadeada, mas contém dois ponteiros(oulinks) naestruturado nó

§Cada elemento agora tem um ponteiro para o próximo elemento e um ponteiro para o seu elemento anterior

§ GraficamenteGraficamente

§O primeiro nó não possui elemento anterior (o ponteiro do elemento anterior terá valor NULL)

Conceitos

L João Maria Ana Edu

Vantagens

§Isto trará novas oportunidades ao novo TAD:

Dado um elemento, poderemos acessar ambos elementos adjacentes: o próximo e o anterior

O ponteiro para o elemento anterior, bem como o endereço do próximo elemento serão manipulados diretamente

Inserção à direita e à esquerda de um nó qualquer

Se tivermos um ponteiro para o último elemento da lista, poderemos percorrê-la na ordem inversa

Também utilizará a memória de maneira eficiente com alocação dinâmica como fez o TAD do módulo anterior

§Este novo TAD possui semelhanças com TListaEnc

§§RepresentaçãoRepresentaçãode cada nó: §estrutura contém os campos dado, proximoeanterior

§ Onde:

Estruturação dos Dados

/* estruturação */ typedef struct nolista{ int dado; struct nolista* proximo; struct nolista* anterior;

}no; typedef no* TListaDupEnc;

/* estruturação */ typedef struct nolista{ int dado; struct nolista* proximo; struct nolista* anterior;

}no; typedef no* TListaDupEnc;

/* estruturação */ typedef struct nolista{ int dado; struct nolista* proximo; }no; typedef no* TListaEnc;

/* estruturação */ typedef struct nolista{ int dado; struct nolista* proximo; }no; typedef no* TListaEnc;

TListaDupEnc *p

(Parte 1 de 2)

Comentários