INSTITUTO SUPERIOR PRIVADO DE ANGOLA
ESTRUTURAS DE DADOS
DISCIPLINA:
Estrutura de Dados
PROFESSOR: Samuel Kakumba N’gunga
Implementação das listas
(II) – Listas Vinculadas – (Apontadores)
1. Características
e Estrutura:
A implementação das listas vinculadas é baseada no conceito de apontadores e (variaveis dinámicas). A estrutura resultante tem as seguintes características:
· Os elementos da lista estão organizados sequencialmente, e a ordem é definida de formas explicita.
·
Os elementos da
lista são organizados em vínculos ou
nós compostos por dois campos ( um que contém a informação
e o outro que aponta para o próximo elemento.
Exemplos considere a lista composta pelos nomes Luanda, Namibe, Cabinda
2. Declaração:
TYPE
tElemento =…; {Defina
neste espaço o tipo de dados para a lista}
tLista =
^VinculoLista;
VinculoLista = record
info
:
tElemeneto; {tipo de dados da lista}
proximo :
tLista ; {aponta
para o próximo elemento}
end;
3. Operações:
3.1 Criar Lista
procedure criar (var Lista :tLista);
{
operação: Criar uma lista
pós condição: retornar a lista vazia
}
begin
Lista:=Nil;
end;
3.2 Lista
Vazia
function vazia (Lista :tLista): Boolean;
{
operação: verificar
se a lista contém elementos
pós condição: retornar verdadeiro
se a lista não conter nenhum elemento ou falso caso contrário
}
begin
vazia
:= (Lista=Nil);
end;
3.3
Cabeçalho da lista (Head)
procedure Head (var elemento
: tElemento;
Lista :tLista);
{
retornar o ultimo elemento da lista
assume lista não vazia
}
begin
if not vazia(Lista) then
elemento:= Lista^.info;
end;
OBS: Se tElemtnto for de tipo simples ou elementar tal como char, integer, real, boolean ou mesmo apontador, então Head pode ser
uma função
function Head (
Lista :tLista) : tElemento;
{
retornar o ultimo elemento da lista
assume lista não vazia
}
begin
if not vazia(Lista) then
Head:= Lista^.info;
end;
3.4 Parte
restante da lista (Tail)
function Tail (Lista :tLista):tLista;
{
retornar a parte restante da
lista
assume lista não vazia
}
begin
if not vazia(Lista) then
Tail
:= Lista^.proximo
end;
3.5 Inserir
3.5.1 Inserir no início da lista
Para inserir um elemento no início da lista siga os passos:
(1) - criar nova variavel temporária (new)
(2) -inserir o elemento na variavel (campo info)
(3) -apontar a nova variavel para a lista original
(4) -apontar a lista original para a nova variavel.
function Inserir (elemento :tElemento; Lista :tLista): tLista;
var temporaria : tLista;
begin
{Passo 1:criar nova variavel temporária}
New (temporaria);
{Passo 2: inserir o elemento na variavel }
temporaria^.info
:=
elemento
;
{Passo 3: apontar a nova variavel para a lista origina}
temporaria^.proximo := Lista ;
{Passo 4: apontar a lista original para a nova variavel}
Lista :=temporaria ;
Inserir :=Lista;
end;
(Faça clique aqui para ver a Ilustração)
3.5.2
Inserir depois de um elemento expecífico
Para inserir depois de um elemento da lista siga os passos:
(1) - criar nova variavel temporária (new)
(2) -inserir o elemento na variavel (campo info)
(3) -apontar a nova variavel para o proximo elemento da lista original
(4) -apontar a lista original para a nova variavel.
function
InserirDepoisDe (elemento :tElemento; Lista :tLista): tLista;
var temporaria : tLista;
begin
{Passo 1:criar nova variavel temporária}
New (temporaria);
{Passo 2: inserir o elemento na variavel }
temporaria^.info
:=
elemento
;
{Passo 3: apontar a nova variavel para o proximo elemento da lista original }
if vazia(Lista) then
begin{não tem sucessor. inserir como antes}
temporaria^.proximo := Lista;
{Passo 4:
apontar a lista original para a nova variavel}
Lista :=temporaria;
end
else
begin{aponta para sucessor}
temporaria^.proximo := Lista^.proximo;
{Passo 4: apontar a lista original para a nova variavel}
Lista^.proximo := temporaria;
end;
Inserir :=InserirDepoisDe ;
end;
(Faça clique aqui para ver a Ilustração)
3.7 Excluir
3.7.1 Excluir ao (topo da lista)
procedure ExluirTopo (var Lista :tLista);
var p: tLista;
{
se a lista não estiver vazia
eliminar o elemento ao topo da lista.
assume lista não vazia
}
begin
if
not vazia(Lista) then
begin
p := Lista;
dispose(p);
end;
end;
3.7.2 Exluir depois depois do topo
procedure ExluirdepoisDe ( var Lista :tLista);
begin
if
Lista<> Nil then
with
Lista do
begin
{ (1) apontar p para o
sucessor do elemento ao topo}
p := Lista^.proximo;
{ (2) agora
faça
com que o sucessor da lista aponte para o sucessor de p
}
p := Lista^.proximo:=p^.proximo
;
{ (3)
reciclar a variavel
p}
dispose(p)
end;
end;
4. Vantagens e
Desvantagens:
4.1
Vantagens
4.2 Desvantagens