O trecho do algoritmo abaixo é o de busca e inserção
em lista encadeada ordenada.
Quando consideramos uma lista circular encadeada, podemos utilizar
um registro auxiliar, como indicado no algoritmo de busca abaixo:
Observação: Este, assim como os demais algoritmos de busca apresentados até o momento, supõe que o campo de informação do nó (tipo T) é 'ordenável', isto é, pode ser comparado com um outro componente do mesmo tipo por expresões (<,<,=,<=,>=); ou então, que existe um campo de chave que pode ser comparado. Isso não é de fato implementado assim.
-> De acodo com a dicussão sobre esse assunto em sala de aula, responda: Qual é alternativa para campos "não ordenáveis". Implemente a alternativa como exercício.
{ Busca em uma lista circular encadeada ordenada com sentinela.
O sentinela é o primeiro elemento da lista circular apontado por ptlista }
Procedure busc_circ (ptlista: Lista; x: T ; Var p,pa:Lista);
Var ant, pont: Lista;
Begin
ant:=ptlista; {sentinela}
ptlista^.info = x;
pont:=ptlista^.lig; {primeiro elemento}
While pont^.info < x do
Begin
ant:=pont;
pont:=pont^.lig;
End;
If pont^.info = x and (pont<>ptlista) then
{elemento já existe,
devolver os ponteiros necessários para eliminação}<- Completar como exercício
Else
{elemento não existe,
devolver os ponteiro necessários para inserção} <- Completar como exercício End;
-> Desenvolver o TAD Lista Ordenada e implementar os demais algoritmos de lista
para ele, supondo organização circular simplesmente encadeada e duplamente encadeada.
