Const N=_____; {número máximo de elementos}
Type endereço= 0..N; { elementos armazenados nas posições de
1 a N do array; o valor 0 indica fim
da lista }
Type Rec = record
info: T
lig: endereço;
End;
Lista = record
A: array[1..N] of Rec;
Prim, Dispo: endereco;
End;
Var L: lista;
1) Qual é o primeiro elemento da lista ?
Function Primeiro (L: lista): T; Begin If L.Prim <> 0 Then Primeiro := L.A[L.Prim].info; End;2) Qual é o último ?
Function Ultimo(L: Lista): T;
Var p: endereco;
Begin
If L.Prim = 0 Then
{Retorna lista vazia }
Else
Begin
p := L.Prim;
While L.A[p].lig <> 0 do
p := L.A[p].lig; {L.A[p].info é o último elemento}
End;
Ultimo := L.A.[p].info;
End;
3) Quantos elementos tem a lista ?
Function No_elementos(L: Lista): integer;
Var Nelem: integer;
p: endereco;
Begin
If L.Prim = 0 Then
Nelem := 0 {lista vazia}
Else
Begin
p := L.Prim;
Nelem := 1;
While L.A[p].lig <> 0 do
Begin
Nelem := Nelem + 1; {Nelem contém o Número de elementos}
p := L.A[p].lig;
End;
End;
No_elementos := Nelem;
End;
Temos ObterNo(j) e DevolverNo(j), as quais permitem obter um registro de índice j da Dispo, ou devolver o registro de indice j, respectivamente.
Na inserção podemos contar com o registro j como sendo disponível, e na eliminação podemos contar com o registro j como a ser deixado disponível.
Para inserir ou eliminar um elemento da lista, temos que saber do endereço do predecessor (lembre que a busca é guiada pelo conteúdo do registro, no caso de listas ordenadas). Este predecessor é quem contém o endereço daquele que será o sucessor do elemento inserido/eliminado.
inserção
eliminação
1) Inserção após o registro de endereço k
Procedure Insere(var L: Lista; k: endereco, valor: T);
Var j: endereco;
Begin
If L.Dispo <> 0 Then {se a Dispo está vazia, nao pode inserir!}
Begin
ObterNo(j);
L.A[j].info := valor;
L.A[j].lig := L.A[k].lig;
L.A[k].lig := j;
End
Else {não pode inserir registro}
...
End;
-> Fazer a inserção de um novo registro na lista APÓS o m-ésimo registro da lista.
Usar o procedimento Insere acima no código.2) Eliminação do registro de endereço j precedido por k
Procedure Remove(var L: Lista; k,j: endereco); Begin L.A[k].lig := L.A[j].lig; DevolverNo(j); End;
-> Fazer a remoção do m-ésimo registro da lista.
Usar o procedimento Remove acima no código, e retornar o conteúdo do registro
sendo removido.3) Casos especiais
Inserção antes do primeiro elemento
Procedure Insere_prim(var L: Lista; valor: T);
Var j: endereco;
Begin
If L.Dispo <> 0 Then
Begin
ObterNo(j);
L.A[j].info:= valor;
L.A[j].lig := L.Prim;
L.Prim := j;
End
Else
{ não pode inserir }
End;
OBS: No caso da lista estar vazia, Prim passar a apontar o único
elemento da lista.
Inserção em lista vazia
Procedure Insere_ListaVazia(var L: Lista; valor: T);
Var j: endereco;
Begin
If L.Dispo <> 0 Then { lista vazia ou prim = 0 }
Begin
Obter_No(j);
L.A[j].info:=valor;
L.A[j].lig:=0; {null}
L.Prim:=j;
End;
End;
Eliminação do primeiro elemento
Procedure Remove_Primeiro(var L: Lista); Var j: endereco; Begin j := L.Prim; L.Prim := L.A[L.Prim].lig; DevolverNo(j); End;4) Acesso ao i-ésimo elemento A[i].info
Function Acessa_iesimo(L: Lista; Var dado: T): boolean;
Var p,j: endereço;
Begin
p := L.Prim; { começa do primeiro elemento }
j := 1;
While (j < i) and (p <> 0) do
Begin
p := L.A[p].lig; { fim := (p=0) }
j := j + 1; { achou := (j=i) }
End;
If p = 0 Then
Begin
Acessa_iesimo:=false;{ lista não possui i elementos }
dado:=0;
End
Else
Begin
Acessa_iesimo:=true;
dado:=L.A[p].info; { A[p] é o elemento procurado}
End;
End;
5) Eliminar o registro de conteúdo dado pela variável
valor
Procedure Remove_elem(var L: lista; valor: T);
Var pa, p, endereco;
acabou: boolean;
Begin
pa := 0; { ponteiro anterior }
p := L.Prim; { busca a partir do primeiro }
acabou := (p=0); { termina quando fim da lista ]
While not (acabou) do
Begin
If L.A[p].info <> valor Then
Begin
pa := p;
p := L.A[p].lig;
acabou := (p=0);
End
Else
acabou := true;
End;
If p=0 Then
{ não existe o conteúdo `valor' na lista }
Else
Begin
If pa = 0 Then
L.Prim := L.A[L.Prim]lig; { eliminar o primeiro elemento }
Else
L.A[pa].lig := L.A[p].lig;
DevolverNo(p);
End;
End;
-> Da forma como foram definidos, os procedimentos ObterNo() e DevolverNo(),
consideram a Lista Encadeada como uma variável global (verifique), o que não é uma
boa idéia. Alterá-los para passar a Lista como parâmetro.
-> A Busca pode (e deve) ser executada por um algoritmo especificamente projetado
para isso. Fazer o algoritmo de busca para lista Estática Encadeada, e substituir
os trechos correspondentes dos algoritmos acima, pela chamada ao algoritmo de busca.
-> Refazer os algortimos acima utilizando uma estrutura parecida com a utilizada em
em Lista Estática Sequencial, isto é, com o registro contendo número de elementos
(Nelem) e com o campo de dado contendo chave e info. Nesse caso, Busca deverá ser
feita pelo valor da chave.
-> Listar as operações adequadas para o TAD Lista Estática Encadeada Ordenada, nos
moldes da TAD lista inicial. Obs: Busca deve ser uma operação realizada
individualmente.
-> desenvolver os algoritmos para todas as suas operações do TAD acima, usando
a estrutura que contém um campo chave. A operação de Busca deve ser utilizada por
todas as demais operações que necessitarem de buscas.
