Programação
MEAer
Bertinho Andrade da Costa
2011/2012
1º Semestre
Instituto Superior Técnico
Noções de listas e anéis duplamente ligados
Programação 2011/2012 DEEC-IST
Noções de listas e anéis duplamente ligados
1
Sumário



Lista dinâmica duplamente ligada
Anel duplamente ligado
Anel duplamente ligado com registo separado para a
base.

Operações:




Inserção (ordenada)
Procura
Remoção
Listar elementos
Programação 2011/2012 DEEC-IST
Noções de listas e anéis duplamente ligados
2
Lista simples com registo separado para a base

Motivação:

No código para a manipulação de uma lista simplesmente ligada, é necessário alterar o
contéudo do apontador base. Como essa alteração tem que ser feita por funções é então
necessário passar a variável da base por referência, ou em alternativa retornar o novo
valor para a base.
Para evitar passar a base por referência (reduzindo a complexidade das funções) podese criar um registo ligado à base mas que não é utilizado para armazenar dados úteis. A
inserção e eliminação de registos ocorre sempre a seguir ao registo que não é utilizado
(separado). Desta forma deixa de ser necessário passar a variável base por referência
ou retornar o novo valor da base.

O registo separado pode ser utilizado para guardar dados quando se efectua uma
operação de procurar ou de insercção.
Alterações ao código:

Na função inicializa base, deve ser alocado o registo e deve ser inicializado.

As restantes funções devem ser adaptadas tendo presente a finalidade do registo
separado para a base, que não é utilizado para armazenar dados de forma
permanente.


base
Programação 2011/2012 DEEC-IST
Registo vazio
W6
M7
endereço
endereço
NULL
Noções de listas e anéis duplamente ligados
3
Lista simples com registo separado para a base

Utilização:

A utilização de uma lista simplesmente ligada com um registo separado para a base
permite que alista seja manipulada, inserção e remoção de registos passando a
base por valor.
Quando se pretende inserir um novo elemento, é necessário efectuar uma procura.
A determinação do local de inserção e a operação de inserção são realizadas
utilizando dois apontadores (o actual e o anterior).
A variável actual é utilizada para determinar o local de inserção de um novo
elemento na lista. Ela é utilizada para aceder a um campo de modo a ser realizada
uma comparação.


anterior
base
actual
Registo vazio
W6
D 11
C 15
endereço
endereço
endereço
NULL
Programação 2011/2012 DEEC-IST
Noções de listas e anéis duplamente ligados
4
Lista simples com registo separado para a base


Procurar:
A comparação determina o fim da procura.
while ((actual != NULL) && (novo->campo > actual->campo)) {
anterior = actual;
actual = actual->prox;
}
novo
Z7
endereço
anterior
base
Registo vazio ...
endereço
Programação 2011/2012 DEEC-IST
actual
W6
D 11
C 15
endereço
endereço
NULL
Noções de listas e anéis duplamente ligados
5
Lista simples com registo separado para a base

Inserir:

A inserção deve ser realizada entre os registos que são apontados pelas
variáveis anterior e actual. A variável anterior é que permite que
se realize a ligação (lógica entre os elementos) com inserção ordenada.


Note-se que a variável actual pode assumir o valor de NULL, quando chega
ao fim da lista.
A inserção é realizada através das acções: novo->prox = actual;
anterior->prox = novo;
novo
Z7
endereço
anterior
base
Registo vazio ...
endereço
Programação 2011/2012 DEEC-IST
actual
W6
D 11
C 15
endereço
endereço
NULL
Noções de listas e anéis duplamente ligados
6
Lista dupla. ligada com reg. sep. para a base

Motivação

Uma lista duplamente ligada é constituida por elementos cuja estrutura de
suporte tem duas variáveis apontadoras que são utilizadas para efectuar
as ligações lógicas entre elementos adjacentes da lista, como se
apresenta na figura seguinte.

Vantagem na utilização de uma lista duplamente ligada:


Permite simplificar o código de inserção e a eliminação de elementos numa lista.
Desvantagem:

base
Uma lista duplamente ligada necessita mais memória do que uma lista simplesmente
ligada.
Registo vazio
NULL
Programação 2011/2012 DEEC-IST
End. prox
End. ant
C6
End. prox
End. ant
Noções de listas e anéis duplamente ligados
R8
End. prox
End. ant
NULL
7
Lista dupla. ligada com reg. sep. para a base

Inserção:

Dependendo do algoritmo de ordenação, a inserção de um elemento pode ser
realizada:


atrás do elemento que está a ser apontador pela variável actual.
à frente do elemento que está a ser apontador pela variável actual.
novo
B5
End. prox
End. ant
actual
base
NULL
Programação 2011/2012 DEEC-IST
Registo vazio
End. prox
End. ant
C6
End. prox
End. ant
Noções de listas e anéis duplamente ligados
R8
End. prox
End. ant
NULL
8
Lista dupla. ligada com reg. sep. para a base

Inserção atrás do elemento que está a ser apontador pela variável actual
novo->prox = actual;
novo->anterior = actual->anterior;
(actual->anterior)->prox = novo;
actual->anterior = novo;
novo
B5
End. prox
End. ant
actual
base
NULL
Programação 2011/2012 DEEC-IST
Registo vazio
End. prox
End. ant
C6
End. prox
End. ant
Noções de listas e anéis duplamente ligados
R8
End. prox
End. ant
NULL
9
Lista dupla. ligada com reg. sep. para a base

Inserção à frente do elemento que está a ser apontador pela variável actual
novo->prox = actual->prox;
novo->anterior = actual;
(actual->prox)->anterior = novo;
actual->prox = novo;
novo
B5
End. prox
End. ant
actual
base
NULL
Programação 2011/2012 DEEC-IST
Registo vazio
End. prox
End. ant
C6
End. prox
End. ant
Noções de listas e anéis duplamente ligados
R8
End. prox
End. ant
NULL
10
Lista dupla. ligada com reg. sep. para a base

Eliminação de um registo que está a ser apontador pela variável eli_actual
(eli_actual->ant)->prox = eli_actual->prox;
(eli_actual->prox)->ant = eli_actual->ant;
eli_actual
base
Registo vazio
NULL
Programação 2011/2012 DEEC-IST
End. prox
End. ant
C6
End. prox
End. ant
Noções de listas e anéis duplamente ligados
R8
End. prox
End. ant
NULL
11
Anel duplamente ligado



Numa lista (simplesmente ou ) duplamente ligada não é possível passar
do último elemento da lista para o primeiro elemento da lista utilizando a
informação que está guarda no apontador (prox) do último elemento, já
que o seu valor é NULL.
É sempre necessário verificar se se chegou ao fim da lista, através do
teste do valor de um apontador com o valor NULL.
Mas nada impede que se efectue as ligações lógicas que estão indicadas
na figura numa lista (simplesmente ou) duplamente ligada. Neste caso
passamos a ter um anel (simplesmente ou) duplamente ligado.
base
Registo vazio
End. prox
End. ant
Programação 2011/2012 DEEC-IST
C6
End. prox
End. ant
Noções de listas e anéis duplamente ligados
R8
End. prox
End. ant
12
Anel duplamente ligado

Vantagens:



Deixa de existir o perigo de sair fora da lista, já que está na forma
de anel.
Deixam de existir casos especiais para a inserção e a remoção de
registos.
O registo separado para a base pode ser utilizado como sendo uma
variável auxiliar para guardar a informação que se pretende
procurar no anel.
base
Registo vazio
End. prox
End. ant
Programação 2011/2012 DEEC-IST
C6
End. prox
End. ant
Noções de listas e anéis duplamente ligados
R8
End. prox
End. ant
13
Anel duplamente ligado

No desenvolvimento de um programa, utilização de um determinado
tipo de lista deve ser ponderando tendo por base a simplicidade do
código e a memória necessária para a implementação da lista.


NOTAS:

Modifique o programa dos acetatos da aula anterior (lista simplesmente ligada)
de modo a incluir um registo separado para a base. Isto perimite simplificar as
funções.
Posteriormente pode abordar o problema utilizando um anel,

Programação 2011/2012 DEEC-IST
Noções de listas e anéis duplamente ligados
14
Programação 2011/2012 DEEC-IST
Noções de listas e anéis duplamente ligados
15