12. Listas Encadeadas

Prévia do material em texto

Ju
d
so
n
 S
an
to
s 
S
an
ti
ag
o
LISTAS ENCADEADAS
Alocação Encadeada
Introdução
 O desempenho dos algoritmos de inserção e 
remoção não são bons para listas ordenadas 
em alocação seqüencial
64 75 77 8615 34 42 51 ×
Remoção implica em movimentar elementos
64 75 77 8615 34 42 51 52
Inserção implica em movimentar elementos
L
is
ta
s 
O
rd
en
ad
as
Introdução
 Os dados precisam ser movidos a cada 
inserção/remoção porque a estrutura de lista 
é formada pela posição dos elementos
38
12
54
88
26
90
15
69
Endereços 
de memória
Dados
38 12 54 88 26 90 15 69
Dados organizados
logicamente como uma 
seqüencia
0x27FCF8
0x27FCFC
0x27FD04
0x27FD00
0x27FD08
0x27FD0C
0x27FD10
0x27FD14
Introdução
 Se a estrutura de lista fosse independente da 
posição dos elementos, não haveria 
necessidade de movimentação na memória
38 54 88 90 93
Dados organizados
logicamente como uma 
lista
85
×
38
85
54
88
90
93
Endereços 
De
Memória
Dados
×
0x27FCF8
0x27FCFC
0x27FD04
0x27FD00
0x27FD08
0x27FD0C
0x27FD10
0x27FD14
Lista Encadeada
 Na lista encadeada os elementos de uma lista 
encontram-se dispostos na memória de 
forma aleatória
 A lista encadeada utiliza ponteiros para 
manter a organização lógica de lista
38
90
69
88
54
Endereços 
de Memória
38 54 88 90 69
Dados organizados
logicamente como uma 
lista
0x27FCF8
0x27FCFC
0x27FD04
0x27FD00
0x27FD08
0x27FD0C
0x27FD10
0x27FD14
Lista Encadeada
 A lista encadeada utiliza alocação dinâmica
 A memória é alocada à medida que novos 
elementos são inseridos e desalocada quando 
elementos são removidos
38
90
69
88
54
Endereços 
de Memória
Memória do Sistema
Memória Alocada ao
Programa
0x27FCF8
0x27FCFC
0x27FD04
0x27FD00
0x27FD08
0x27FD0C
0x27FD10
0x27FD14
0x27FD18
0x27FD1C
NULL
Lista Encadeada
 Os elementos da lista encadeada são 
formados por registros da mesma forma que 
a lista sequencial
struct aluno 
{ 
int matricula;
char nome[40];
float nota;
aluno * prox;
};
654 890 125 411658
matricula
nome
nota
prox
8.8
joão
890
Lista Encadeada
 É preciso guardar um ponteiro com o 
endereço do primeiro elemento da lista
 É necessário apontar o campo "próximo" do 
último elemento para uma marcação de fim 
de lista (NULL)
Início
Fim
38 54 88 90 69
Lista Encadeada
 Vantagens:
 A inserção e remoção de elementos é mais 
eficiente, especialmente com listas ordenadas
 Operações de fusão e separação de listas são 
executadas em tempo constante O(1)
 Desvantagens
 Gasto maior de memória
 Acesso ao k-ésimo elemento não é direto, é 
preciso percorrer a lista até o elemento desejado
Lista Encadeada
 Existem diversas opções de encadeamento 
para as listas:
Início
Fim
38 54 88 90 69
Início
38 54 88 90 69
Início 38 54 88 90 69
Simplesmente
Encadeadas
Listas 
Circulares
Duplamente
Encadeadas
Lista Encadeada
 Para cada opção de encadeamento é preciso 
construir algoritmos para:
 Percurso
 Busca
 Inserção
 Remoção
 O percurso para listas em alocação seqüencial 
é trivial, mas para listas encadeadas ele 
precisa de um tratamento específico
Simplesmente Encadeada
 O algoritmo abaixo faz o percurso para 
impressão do campo info de uma lista 
simplesmente encadeada
Algoritmo: Percurso da lista
função percurso(pont)
enquanto pont ≠ λ faça
| imprimir (pont.info)
| pont = pont.prox
ptlista
λ
38 54 88 90 69
Simplesmente Encadeada
 A implementação da função percurso em 
C/C++ considerando uma lista de alunos:
void percurso(aluno * pont)
{
while (pont != NULL)
{
cout << pont->matricula << endl;
cout << pont->nome << endl;
cout << pont->nota << endl;
pont = pont->prox;
}
}
ptlista
38 54 88 90
λ
Simplesmente Encadeada
 O algoritmo de busca também é utilizado nas 
inserções e remoções
 Portanto a busca deve ser muito eficiente
 A existência de um ponteiro para o primeiro 
elemento da lista obriga os algoritmos de inserção 
e remoção a fazerem testes adicionais
ptlista
38 54 88 90
λ
Simplesmente Encadeada
 Isso pode ser resolvido pela criação de um 
elemento cabeça da lista
Lista inicialmente 
vazia
ptlista
λ
38 54 88
ptlista
λ
Lista após algumas 
inserções
Simplesmente Encadeada
 O algoritmo abaixo faz a busca em uma lista 
ordenada simplesmente encadeada
Algoritmo: Busca em uma lista ordenada
função busca-enc(x,ant,pont)
ant = ptlista; pont = λ
ptr = ptlista.prox
enquanto ptr ≠ λ faça
| se ptr.chave < x então
| | ant = ptr
| | ptr = ptr.prox
| senão
| | se ptr.chave == x então
| | | pont = ptr
| | ptr = λ
Simplesmente Encadeada
 O parâmetro pont retorna apontando para o 
elemento buscado ou para nulo se o 
elemento não estiver na lista
 O parâmetro ant retorna apontando para o 
elemento anterior ao buscado (será 
importante na inserção e remoção)
 O parâmetro x é a chave buscada
 Como o algoritmo estabelece um percurso na 
lista sua complexidade é O(n)
Simplesmente Encadeada
 Numa implementação em linguagem C/C++ 
os parâmetros pont e ant devem ser passados 
por referência para servir como retorno da 
função
void BuscaEnc(int x, aluno * lista, aluno* & an, aluno* & po)
{
}
int main()
{
...
aluno * ant = NULL;
aluno * pont = NULL;
BuscaEnc(543, ptlista, ant, pont);
if (pont == NULL) 
...
}
Simplesmente Encadeada
 Uma implementação em C/C++ da função de 
busca em lista simplesmente encadeada:
void BuscaEnc(int x, aluno * lista, aluno* & ant, aluno* & pont)
{
ant = lista; 
pont = NULL;
ptr = lista->prox;
while (ptr != NULL)
{
if (ptr->matricula < x)
{
ant = ptr;
ptr = ptr->prox;
} else {
if (ptr->matricula == x)
pont = ptr;
ptr = NULL;
}
}
}
Simplesmente Encadeada
 O algoritmo abaixo mostra a inserção de um 
elemento com a chave x
Algoritmo: Inserção de um elemento
função insere(x)
busca-enc(x,ant,pont)
se pont == λ então
| ocupar(pt)
| pt.info = novo-valor
| pt.chave = x
| pt.prox = ant.prox 
| ant.prox = pt
senão
| “Elemento já está na lista”
Simplesmente Encadeada
 Implementação em C/C++ da função de 
inserção em lista simplesmente encadeada:
void Insere(aluno & novo, aluno * lista)
{
aluno * ant = NULL;
aluno * pont = NULL;
BuscaEnc(novo->matricula, lista, ant, pont);
if (pont == NULL)
{
aluno * pt = new aluno;
*pt = novo;
pt->prox = ant->prox;
ant->prox = pt; 
}
else
cout << "Elemento existente!" << endl;
}
Simplesmente Encadeada
 A remoção do elemento apontado por pont é 
mostrada no algoritmo abaixo
Algoritmo: Remoção de um elemento
função remove(x)
busca-enc(x,ant,pont)
se pont ≠ λ então
| ant.prox = pont.prox
| valor-recuperado = pont.info 
| desocupar(pont)
senão
| “Elemento não está na lista”
Simplesmente Encadeada
 Implementação em C/C++ da função de 
remoção em lista simplesmente encadeada:
void Remove(int x, aluno * lista, aluno & removido)
{
aluno * ant = NULL;
aluno * pont = NULL;
BuscaEnc(x, lista, ant, pont);
if (pont != NULL)
{
ant->prox = pont->prox;
removido = *pont;
delete pont; 
}
else
cout << "Elemento não está na lista!" << endl;
}
Exercício
 Construir os algoritmos de manipulação de 
uma lista simplesmente encadeada não 
ordenada:
 Percurso
 Busca
 Inserção
 Remoção