INSTITUTO SUPERIOR PRIVADO DE ANGOLA

INSTITUTO SUPERIOR PRIVADO DE ANGOLA
ESTRTUTURAS DE DADOS

INFORM�TICA -3� ANO
PROFESSOR: Samuel Kakumba N�gunga

LISTAS- OPERA��ES DERIVADAS

As opera��es derivadas s�o as que podemos construir fazendo uso das opera��es b�sicas. S�o v�rias opera��es derivadas. Apresentamos em seguida a lista de algumas opera��es e o objectivo fundamental � proporcionar ao estudante algoritmos queira iterativos ou recursivos para a manipula��o de listas.

1. Encaminhar ou Navegar(Lista)
Esta opera��o consiste na inspec��o de todos os elementos contidos numa lista .

a)- Vers�o Iterativa:
procedure encaminhar(Lista: tLista);
bigin
   while not Vazia(lista) do
   begin
   processar( Head ( Lista ) );
   Lista := Tail( Lista );
   end;
end;
________________________________

b)- Vers�o Recursiva:
Express�o recursiva da opera��o:
Se a lista n�o for vazia, fa�a o seguinte:
1. processar os dados contidos no cabe�alho da lista
2. visitar de modo recursivo os restantes elementos da lista.

procedure encaminar(Lista: tLista);
bigin
   if not Vazia(lista) then
   begin
   processar( Head ( Lista ) );
encaminhar( Tail( Lista ) );
   end;
end;

OBS: Neste algoritmo, o termo processar representa qualquer opera��o ligada a isnpec��o dos elementos. O Programador dever� na altura da implementa��o susbtituir esta opera��o pela opera��o que tiver em mente.

________________________________
Veja a Ilustra��o desta opera��o:

Assume a lista representada por caracters

Lista =[A, B, C, D,E]

e que processar Head(Lista) � apenas uma instru��o para exibir o caracter dado sob a tela.

Navegar (Lista) = processar( Head(Lista)); Navegar (Tail(Lista))

|
|_____ A; Navegar ( [B, C, D,E])

|
|_____ B; Navegar ( [C, D,E])

|
|_____ C; Navegar ( [D,E])

|
|_____ D; Navegar ( [E])

|
|_____ E; Navegar ( [])

|
|__Fim lista vazia

2. Contar( Lista)
Esta opera��o determina o n�mero de elementos contidos na lista:
a)- Vers�o Iterativa:
function contar(Lista: tLista): integer ;
      var contador: integer;
bigin
      contador :=0;
      while not Vazia(lista) do
                 begin
                        contador := contador +1;
                        Lista := Tail ( Lista ) ;
                  end ;
       contar:=contador;
end;
________________________________

b)- Vers�o Recursiva:
Express�o recursiva da opera��o:
Se a lista n�o for vazia, fa�a o seguinte:
1. Se a lista for vazia ent�o o comprimento :=0
2. Caso contr�rio, o comprimento := 1 + comprimento da parte restante da lista.

function contar(Lista: tLista) : integer;
bigin
     if Vazia(lista) then
             contar := 0
     else
            contar:= 1 + contar( Tail(Lista))
end;
________________________________

Veja a Ilustra��o desta opera��o:
Assume a lista representada por caracters

Ilustra��o do m�todo recursivo para a determina��o do comprimento da lista

Assume a lista representada por caracters

Lista =[A, B, C, D,E]

Comprimento (Lista) = 1 + Comprimento (Tail(Lista))

| 1 + 1+1+ 1+0 <-----|
|_____ 1 + Comprimento ( [B, C, D,E])

| 1 + 1+1 + 0 <---- |
|_____ 1 + Comprimento ( [C, D,E])

| 1+1+0 <-----|
|_____ 1 + Comprimento ( [D,E])

| 1+ 0<------|
|_____ 1 + Comprimento ( [E])

| 0<-------------|
|_____ 1 + Comprimento ( []) |

| |
|__Fim lista vazia = 0

Resposta: = Comprimento ([A, B, C, D, E]) =1 + 1+1+ 1+0 =5

3. Pesquisar( Lista)
Esta opera��o verifica se um elemento pertence a lista. retornando verdadeiro ou Falso:
a)- Vers�o Iterativa:
function localizado(Elemento:tElemento; Lista: tLista): Bolean ;
      var alvoLocalizado: boolean;
bigin
      alvoLocalizado:=False;
      while not Vazia(lista) and Not AlvoLocalizado do
                   if Elemento = Head(Lista) then
                         alvoLocalizado:=true
                 else
                         Lista := Tail ( Lista );
       localizado:=alvoLocalizado;
end;
________________________________

b)- Vers�o Recursiva:
Express�o recursiva da opera��o:
Se a lista n�o for vazia, fa�a o seguinte:
1. Se a lista for vazia ent�o o retornar Falso
2. Caso contr�rio fa�a o seguinte:
       a) Se o elemento a procura for egual ao cabe�alho da lista ent�o retornar verdadeiro
       b) caso contr�rio procure peloo elemento ou dado na parte restante da lista

function Localizado(Elemento: tElemento;Lista: tLista) : Boolean ;
bigin
     if Vazia(lista) then
             Localizado:= false
     else if Elemento = Head(Lista) then
               Localizado:=true
     else
            Localizado := Localizado(Elemento, Tail(Lista))
end;
________________________________

4. igual( Lista1, Lista2)
Esta opera��o compara duas listas por igualdade na mesma ordem l�xical retornando Verdadeiro ou Falso:
a)- Vers�o Iterativa:
________________________________
function igual(Lista1, Lista2: tLista) : Boolean ;
     var ok : boolean ;{ variavel local }

begin
    ok   :=True;  { assume verdadeiro at� ent�o}
     while not Vazia(lista1) And Not Vazia(lista2) And  ok    do
             begin
                    ok   :=ok  And ( Head(Lista1) = Head(Lista2)) ; {liga��o em s�rie da conjun��o And}
                    lista1:= Tail(Lista1);
                    lista2:= Tail(Lista2);
             end;

    {Se todos os elementos comparados s�o iguais e chegou-se ao final das duas listas simult�neamente,
     ent�o ambas listas s�o iguais}
    ok   :=ok  And vazia(Lista1) And Vazia(Lista2) ; {liga��o em s�rie da conjun��o And}

   { finalmente atribuimos este resultado final � fun��o}
      igual:=ok
end;
________________________________

b)- Vers�o Recursiva:
Express�o recursiva da opera��o:

1. Se ambas listas forem vazias,  ent�o retornar Verdadeiro
2. Caso contr�rio, se ambas listas n�o forem vazias fa�a o seguinte:
        2.1. Se os cabe�alhos de ambas listas forem diferentes ent�o retornar Falso
        2.2. Caso contr�rio ( isto � cabe�alhos iguais ent�o proceder a compara��o recursiva das ambas partes restantes
3. Caso contr�rio isto � se uma das listas for vazia ent�o retornar Falso

function igual(Lista1, Lista2: tLista) : Boolean ;
begin
     if Vazia(lista1) And  Vazia(lista2)   then
             igual:=  true
     else if   Not Vazia(lista1) And  Not Vazia(lista2)   then
            if  Head(Lista1) <> Head(Lista2) then
                       igual:=  false
            else {ambos cabe�alhos s�o iguais}
                      igual:= igual( Tail(Lista1),   Tail(Lista2) )
    else {uma das listas � vazia}
             igual:=  false
end;

________________________________

Veja a Ilustra��o desta opera��o:
Assume a lista representada por caracters
Ilustra��o do m�todo recursivo para a compara��o de duas lista

Assume seguintes listas representadas por caracters

Lista1 =[A, B, C]

Lista2 =[A, B, D]

Igual (Lista1, Lista2) = Not Vazia(lista1) And Not Vazia(lista2) � Verdadeiro. Ent�o
( Head (Lista1) = Head (Lista2) ) tamb�m � Verdadeiro. Ent�o Igual( Tail(Lista1 ), Tail( Lista2) )

Temos as pares restantes e repetimos o passo anterior
Lista1 =[B, C]
Lista2 =[B, D]
Igual (Lista1, Lista2) = Not Vazia(lista1) And  Not Vazia(lista2) � Verdadeiro. Ent�o
                                                                     ( Head (Lista1) = Head (Lista2) )  tamb�m � Verdadeiro. Ent�o Igual( Tail(Lista1 ), Tail( Lista2) )

Temos as pares restantes e repetimos o passo anterior
Lista1 =[C]
Lista2 =[D]
Igual (Lista1, Lista2) = Not Vazia(lista1) And  Not Vazia(lista2) � Verdadeiro. Ent�o
                                                                     ( Head (Lista1)  <> Head (Lista2) )  � Verdadeiro ent�o termina e retorna Falso

|____Fim

Resposta: Igual (Lista1, Lista2) = Falso

5. Concatenar( Lista1, Lista2)
Esta opera��o une as duas listas Lista1 e Lista2 e retorna a uni�o de ambas
a)- Vers�o Iterativa:
function concatenar (Lista1, Lista2: tLista): tLista;
    var
       ListaTemporaria,
       ListaResultante : tLista;
begin
   ListaResultante :=Lista2;
   Criar(ListaTemporaria);
   while not vazia(Lista1) do
         begin
            ListaTemporaria := Inserir(head(Lista1), ListaTemporaria );
            Lista1 :=Tail(Lista1);
         end;
    while not vazia(ListaTemporaria ) do
         begin
               ListaResultante := Inserir(Head(ListaTemporaria), ListaResultante);
               ListaTemporaria :=Tail(ListaTemporaria);
         end;
    concatenar :=ListaResultante

end;

________________________________

b)- Vers�o Recursiva:
Express�o recursiva da opera��o:

1. Se a primeira lista for vazia ent�o retornar a segunda lista.
2. Caso contr�rio Inserir o elemento contido no cabe�alho da primeira lista ao resultado da concatena��o do resto da primeira lista com a segunda lista:

function concatenar(Lista1, Lista2: tLista) : tLista ;
begin
     if Vazia(lista1)    then
          concatenar:=  Lista2
     else
         concatenar:= Inserir( Head(Lista1), concatenar( Tail(Lista1),  Lista2))
end;

________________________________

Ilustra��o do m�todo para concatenar duas listas

Assume a lista representada por caracters

Lista1 =[L, M, N]

Lista2 =[A, B, C, D,E]

Concatenar (Lista1, Lista2) = Inserir(Head(Lista1), Concatenar (Tail(Lista1), Lista2))

    |

    |

    |                                    [L, M, N, A, B, C, D, E]<-------- |
    |_____ Inserir(L, Concatenar ([M, N], [A, B, C, D,E])    |

                                         |                                                       |      [N,A, B, C, D,E]<--- |
                                         |_____Inserir(M, Concatenar ([N], [A, B, C, D, E])                |

                                                                             |                                                              |            [A, B, C, D,E]<----|
                                                                             |_____ Inserir(N, Concatenar ([vazia], [A, B, C, D, E])                    |

                                                                                                                 |                                                                        |
                                                                                                                 |_____ Inserir(N, Concatenar ([vazia], [A, B, C, D, E])

                                                                                                                                                     |
                                                                                                                                                     |_____ = [A, B, C, D, E]

                                                                                                                                                                              |
                                                                                                                                                                              |__Fim lista1 vazia

Resposta: = Concatenar ([L, M, N] , [A, B, C, D, E]) = [L, M, N,A, B, C, D,E]

Hosted by www.Geocities.ws