INSTITUTO SUPERIOR PRIVADO DE ANGOLA
ESTRUTURAS DE DADOS
DISCIPLINA:
Estrutura de Dados
PROFESSOR: Samuel Kakumba N’gunga
Implementação das listas
(I) – Espaço Sequencial – Arrays e Records
1. Características
e Estrutura:
A implementação das listas pela representação sequencial é baseada em arrays e records. A estrutura resultante tem as seguintes características:
·
Os elementos da lista
estão organizados sequencialmente, sendo o primeiro na posição 1, o segundo
na posição 2 e assim por diante.
·
Os elementos da
lista são referenciados via índice
(número que representa sua
posição na lista). Exemplos Lista.tArray[5]
2. Declaração:
CONST
ListaLimite = …; {Número máximo de elementos
da lista}
TYPE
tElemento =…; {Defina
neste espaço o tipo de dados para a lista}
ListaArray = array [1..ListaLimite] of
tElemento;
tLista = record
tamanho
: 0..ListaLimite; {número
actual de elementos}
tArray : ListaArray
; {array ou tabela contendo
os elementos}
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.tamanho
:=0;
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.tamanho =0);
end;
3.3 Lista
Cheia
function Cheia (Lista :tLista): Boolean;
{
operação: verificar
se a lista está cheia de
elementos
pós condição: retornar verdadeiro
se a lista estiver cheia ou falso caso contrário
}
begin
Cheia:= (Lista.tamanho =ListaLimite);
end;
OBS: esta operação só é válida para a implementação de lista usando arrays.
3.4
Cabeçalho da lista (Head)
procedure Head (var elemento : tElemento; Lista :tLista);
{
retornar o ultimo elemento da lista
assume lista não vazia
}
begin
elemento:= (Lista.tArray[Lista.tamanho]);
end;
3.5 Parte
restante da lista (Tail)
procedure Tail (var Lista :tLista);
{
retornar a parte restante da
lista
assume lista não vazia
}
begin
Lista.tamanho
:= Lista.tamanho - 1
end;
3.6 Inserir
3.6.1
Inserir após o ultimo elemento (topo da lista)
procedure Inserir (elemento :tElemento; var Lista :tLista);
{
se a lista não estiver cheia
inserir mais um elemento ao topo.
assume lista não cheia
}
begin
if
not cheia(Lista) then
begin
Lista.tamanho := Lista.tamanho + 1;
Lista.tArray[Lista.tamanho] :=
elemento;
end;
end;
3.6.2
Inserir na posição pos da lista
procedure InserirPos (elemento :tElemento; pos: integer; var Lista :tLista);
{
se a lista não estiver cheia
inserir mais um elemento na posição indicada pelo número pos
assume lista não cheia.
Passos:
(a)
criar
um espaço na posição pos. Isto é mover todos os
elementos a direita de pos uma casa adiante
(b)
inserir
o elemento na posição pos
(c)
incrementar
o tamanho da lista uma unidade.
}
var i : integer;
begin
if
not cheia(Lista) then
with Lista do
begin
{ (a) criar
um espaço na posição pos}
for i := tamanho downto pos do
tArray[i+1] := tArray[i];
{ (b) inserir o elemento no local pos}
tArray[pos] := elemento;
{ (c) incrementar o tamanho da lista uma unidade }
tamanho := tamanho + 1;
end;
end;
3.7 Eliminar
3.7.1 Eliminar
o ultimo elemento (topo da lista)
procedure EliminarTopo (var Lista :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
Lista.tamanho
:= Lista.tamanho - 1;
end;
end;
3.7.2 Eliminar
o elemento na posição pos da lista
procedure EliminarPos (pos: integer; var Lista :tLista);
{
se a lista não estiver vazia,
eliminar o elemento na posição indicada por pos
assume lista não vazia.
Passos:
(1)
mover
todos os elementos sucessores de pos uma unidade para
traz
(2)
diminuir
o tamanho da lista uma unidade
}
var i : integer;
begin
if
not vazia(Lista) then
with Lista do
begin
{ (1) mover todos os elementos sucessores de
pos uma unidade para traz}
for i := pos to tamanho do
tArray[i] := tArray[i+1];
{ (2) diminuir o tamanho da lista uma
unidade}
tamanho := tamanho -1;
end;
end;
4. Vantagens e Desvantagens:
3.1 Vantagens
3.2 Desvantagens