Estrutura de Dados (DPADF 0056)
Aula 11 – Listas Ordenadas
Universidade Federal de Santa Maria
Colégio Agrícola de Frederico Westphalen
Curso Superior de Tecnologia em Sistemas para Internet
Prof. Bruno B. Boniati – www.cafw.ufsm.br/~bruno
Conjunto de dados mantido sempre ordenado
12
45
?
23
28
33
Listas Ordenadas
• Cada inserção de um novo elemento deverá obedecer ao
critério de ordenação;
• Antes de incluir um novo elemento da lista sua posição
correta precisa ser encontrada:
Novo elemento
12
28
33
23
45
Mantendo a Lista Ordenada
• Manter uma lista ordenada em geral não é eficiente pois
cada vez que a lista aumentar de tamanho, maior será o
custo computacional de realizar a operação de inclusão;
• A única alteração a ser feita é na função de inclusão, que
precisará percorrer a lista procurando o elemento após o
qual a inclusão será feita;
• Se a ordem de armazenamento dos elementos na lista
não for significante/determinante para o problema em
questão, não é recomendado a utilização de listas
ordenadas;
Prós e contras
• Uma lista ordenada é uma boa escolha se ...
▫ Você precisa que os elementos sejam mantidos sempre de
acordo com algum critério de ordenação e a eventual
demora na inclusão de novos elementos não é um fator
importante;
• Uma lista ordenada não é uma boa escolha se ...
▫ Você precisa de rapidez de inclusão e não precisa
necessariamente que os elementos da lista estejam
ordenados;
• Uma opção alternativa seria disponibilizar uma operação para ordenar
a lista (somente quando houvesse necessidade)
Implementação
Elemento* insere_ordenado (Elemento* inicio, int v) {
//procurar a posição a ser inserido o elemento
TO-DO?
// TO-DO
//alocar memória para o novo elemento
// TO-DO
//encadear o novo elemento
// TO-DO
}
Exercícios para fixação
Lista de Nomes em Ordem Alfabética
• Que tal implementar um TAD Lista para ler um
conjunto de caracteres de um arquivo e
apresentá-los de forma ordenada.
▫ Tente variar o tamanho do arquivo e medir o
desempenho do programa.
Estrutura de Dados (DPADF 0056)
Aula 12 – Lista Duplamente Encadeada
Universidade Federal de Santa Maria
Colégio Agrícola de Frederico Westphalen
Curso Superior de Tecnologia em Sistemas para Internet
Prof. Bruno B. Boniati – www.cafw.ufsm.br/~bruno
Lista com encadeamento nos dois sentidos (anterior e próximo)
Lista duplamente encadeada
• Até então o que vimos foram listas com encadeamento
simples (cada elemento indica seu vizinho em um único
sentido: “início fim” da lista);
• Suponhamos a necessidade de percorrer uma lista em
sua ordem inversa. Isso seria possível?
• Outra dificuldade é a retirada de um elemento, pois
mesmo conhecendo seu ponteiro, de nada adianta se não
conhecermos também seu antecessor;
Lista duplamente encadeada
• Uma lista duplamente encadeada é uma lista onde cada
elemento possui dois campos de encadeamento:
▫ Uma indicação para o próximo elemento;
▫ Uma indicação para o elemento anterior;
• Em uma lista duplamente encadeada se obtivermos uma
referência a qualquer elemento da lista podemos avançar
ou retroceder ambos os sentidos.
ɸ
10
40
17
6
40
ɸ
Para exemplificar ...
anterior
10
proximo
struct elemento {
int conteudo;
struct elemento* anterior;
struct elemento* proximo;
};
typedef struct elemento Elemento;
Implementação
• As interfaces das operações são exatamente as
mesmas ... E basicamente duas operações
precisam ser alteradas:
▫ Inclusão
 Tanto o novo elemento como os elementos entre o
qual ocorrerá a inclusão precisam ter suas ligações
atualizadas;
▫ Exclusão
 Os elementos antes e após ao elemento a ser
excluído precisarão ajustar suas ligações;
Vantagens
• Com a referência a qualquer elemento da lista posso
descobrir seu início e seu final;
• Conhecendo a referência a um elemento posso fazer sua
exclusão sem a necessidade de descobrir seu elemento
anterior;
• Estabeleço uma relação bilateral de vizinhança o que
pode possibilitar outras operações, como a ordenação da
lista, por exemplo.
Exercícios para fixação
Qual a distância de um elemento?
(do começo para o fim e do fim para o começo)
• Usando uma LDE (lista duplamente encadeada) e
a referência a um elemento qualquer da lista você
consegue dizer a posição que esse elemento
ocupa?
40
O elemento
ocupa a 4ª posição (em
relação ao início) e a 2ª posição em relação ao fim)
ɸ
10
40
17
6
40
ɸ