reemplaza.pas

{ ppc386 -va -vh *.pas }
{ COMIENZO DE DESCRIPCION

 [Tomado el 1er parcial, 16 abril 2002]. Dada una lista L
 con enteros y dos listas S (por secuencia) y R (por
 reemplaza) escribir un
 procedure REEMPLAZA (var L: lista; S, R: lista)
 que busca todas las secuencias de S en L y las
 reemplaza por R. Ejemplo, si
 L = (1 2 3 4 5 1 2 3 4 5 1 2 3 4 5), S = (4 5 1) y
 R = (9 7 3), entonces despues de llamar a REEMPLAZA
 debe quedar L = (1 2 3 9 7 3 2 3 9 7 3 2 3 4 5). Este
 procedimiento tiene un efecto equivalente a la funci\'on
 REEMPLAZAR de los editores de texto.
 keywords: lista

FIN DE DESCRIPCION }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{$Id: reemplaza.pas 2003/04/03 16:00 jdelia  Exp jdelia   $ }
program reemplaza_p;
uses u_listpi, u_colapi;
type
  lista = listpi;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ SOLUCION 1 (con leve correcion para caso especial)
  Se sugiere el siguiente algoritmo. Recorrer la lista L con
  una posicion "p" y la secuencia S con una posicion "q".
  Esto lo haremos mientras "p" o bien sea distinto de fin
  de L o bien "p" es fin de L y "q" es fin de secuencia. En
  todo momento mantenemos una cola C con los ultimos
  elementos de la lista L que coinciden con los de la
  secuencia S. En el siguiente paso, al avanzar q, se
  pueden dar 3 posibilidades: 
  1. Si llegamos al fin de S, entonces toda la secuencia S
     estaba en la lista L y, por lo tanto, insertamos el
     reemplazo R en la posicion "p" de la lista L. Tambien
     vaciamos la cola C; 
  2. Si el elemento en "q" es igual al que esta en "p"
     entonces suprimimos el elemento de la lista L y lo
     ponemos en la cola C. Tambien avanzamos la posicion
     "q" en el reemplazo R;
  3. Si el elemento en "q" NO es igual al que esta en "p",
     entonces insertamos toda la cola C en la lista L en la
     posicion "p" y reseteamos la posicion "q" al
     principio de la secuencia S. }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure REEMPLAZA1 (var L: lista; S, R: lista );
var
  p, q, t  : posicion;
  c	   : colapi;
begin
  C.ANULA;
  p := L.PRIMERO;
  q := S.PRIMERO;
  while (p <> L.FIN) or ((p = L.FIN) and (q = S.FIN)) do begin
    if  (q = S.FIN) then begin
      {todo S esta en L, por lo que vaciamos la cola C}
      C.ANULA;
      t := R.PRIMERO;    {insertamos R en posicion p de L}
       while (t <> R.FIN) do begin
	L.INSERTA (R.RECUPERA (t), p);
        p := L.SIGUIENTE (p);
        t := R.SIGUIENTE (t);
      end; {while}
      q := S.PRIMERO;    {reseteamos posicion q en S}
      end
    else if (L.RECUPERA (p) = S.RECUPERA (q) ) then
      begin  {Hay un elemento mas en L igual al de S}
      C.PONE (L.RECUPERA (p) );    {Lo ponemos en la cola }
      L.SUPRIME (p);               {Lo suprimimos   }
      q := S.SIGUIENTE (q);        {Avanzamos q en S}
      end
    else begin                     {elementos no iguales}
      while (not C.VACIA) do begin {Inserta C en L} 
        L.INSERTA (C.FRENTE, p);
	C.QUITA;
	p := L.SIGUIENTE (p);
      end; {while}
      p := L.SIGUIENTE (p);        {avanzamos p en L}
    end ; {if}
   end ; {while}
end ;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ SOLUCION 2

Se recorre la lista L con una posicion "p". Si la
secuencia en L a partir de la posicion "p" es igual a S,
entonces se eliminan los elementos de L correspondientes
y se insertan en R, sino avanzamos "p". Para esto, hacer:

1. Escribir una function LONGITUD (L:lista): integer; que
   cuenta los elementos de una lista. 

2. Escribir una function COMPARA (S, L: lista;
   p: posicion): boolean; que compara la secuencia de
   elementos de L a partir de la posicion "p" con la
   secuencia S. Devuelve verdadero si S esta
   contenido en L y falso en caso contrario. 

3. Escribir un procedimiento procedure REEMPLAZA_AQUI
   (var L: lista; p: posicion; n: integer; R: lista);
   que elimina n elementos de L a partir de la posicion
   "p" e inserta la secuencia S en esa posicion.

4. Escribir el procedimiento procedure REEMPLAZA2
   (var L: lista; S, R: lista ); de acuerdo a la
   estrategia descripta anteriormente.
}

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function LONGITUD (L: lista): integer;
var
  p : posicion;
begin
  p := L.PRIMERO;
  LONGITUD := 0;
  while (p <> L.FIN) do begin
      LONGITUD := LONGITUD + 1;
      p := L.SIGUIENTE (p);
  end; {while}
end;
   
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function COMPARA (S, L: lista; p: posicion): boolean;
var
  q : posicion;
begin
  q := S.PRIMERO;
  while (q <> S.FIN) do begin
    if (p = L.FIN) or (L.RECUPERA (p) <> S.RECUPERA (q) )
    then begin
       COMPARA := false;
       exit;
    end; {if}
    p := L.SIGUIENTE (p);
    q := S.SIGUIENTE (q);
  end ; {while}
  COMPARA := true;
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure REEMPLAZA_AQUI (var L: lista  ; p: posicion;
                              n: integer; R: lista);
var
  q : posicion;
  j : integer;
begin
  for j := 1 to n do  L.SUPRIME (p);
  q := R.PRIMERO;
  while (q <> R.FIN) do begin
    L.INSERTA (R.RECUPERA (q), p);
    p := L.SIGUIENTE (p);
    q := R.SIGUIENTE (q);
  end; {while}
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure REEMPLAZA2 (var L: lista; S, R: lista);
var
  p: posicion;
begin
  p := L.PRIMERO;
  while (p <> L.FIN) do begin
    if ( COMPARA (S, L, p) = true ) then
      REEMPLAZA_AQUI (L, p, LONGITUD (S), R)
    else begin
      p := L.SIGUIENTE (p);
    end ; {if}
  end; {while}
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ SOLUCION 3: Sin documentar }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure REEMPLAZA3 (var L: lista; S, R: lista);
var
   p, q, t  : posicion;
   coincide : boolean;
begin 
   p := L.PRIMERO;
   while ( p <> L.FIN ) do begin
     q := p ;
     t := S.PRIMERO;
     coincide := true;
     while (t <> S.FIN) do begin
       if (q = L.FIN) or ( L.RECUPERA (q) <> S.RECUPERA (t) )
       then begin
         coincide := false;
         break ;
       end ; {if}
       t := S.SIGUIENTE (t);
       q := L.SIGUIENTE (q);
     end; {while}
     if (coincide = true) then begin
       q := p;
       t := S.PRIMERO;
       while (t <> S.FIN) do begin
	 L.SUPRIME (q);
         t := S.SIGUIENTE (t);
       end; {while}
       t := R.PRIMERO;
       q := p;
       while (t <> R.FIN) do begin
	 L.INSERTA (R.RECUPERA (t), q);
	 q := L.SIGUIENTE (q);
         t := R.SIGUIENTE (t);
       end; {while}
    end; {if}
    p := L.SIGUIENTE (p);
  end; {while}
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
var
   L, S, R : lista;
   j, k	   : integer;
begin
   writeln ;
   writeln ('Ejemplo 1: ');
   L.ANULA;
   S.ANULA;
   R.ANULA;
   { Llena L con la secuecia 11 12 13 }
   for j := 1 to 1 do
      for k := 11 to 13 do
        L.INSERTA (k, L.FIN);
   L.IMPRIME ('lista inicial L:');
   { Define secuencia S e intenta reemplazar R } 
   S.INSERTA (1, S.FIN);
   S.INSERTA (2, S.FIN);
   S.INSERTA (3, S.FIN);
   R.INSERTA (9, R.FIN);
   R.INSERTA (7, R.FIN);
   R.INSERTA (3, R.FIN);
   S.IMPRIME ('secuencia S:');
   R.IMPRIME ('reemplaza R:');
   REEMPLAZA1 (L, S, R);
{  REEMPLAZA2 (L, S, R); }
{  REEMPLAZA3 (L, S, R); }
   L.IMPRIME ('lista final L:');

   writeln ;
   writeln ('Ejemplo 2: ');
   L.ANULA;
   S.ANULA;
   R.ANULA;
   { Llena L con la secuecia 1 2 3 }
   for j := 1 to 1 do
      for k := 1 to 3 do
        L.INSERTA (k, L.FIN);
   L.IMPRIME ('lista inicial L:');
   { Define secuencia S y reemplaza R } 
   S.INSERTA (1, S.FIN);
   S.INSERTA (2, S.FIN);
   S.INSERTA (3, S.FIN);
   R.INSERTA (9, R.FIN);
   R.INSERTA (7, R.FIN);
   R.INSERTA (3, R.FIN);
   S.IMPRIME ('secuencia S:');
   R.IMPRIME ('reemplaza R:');
   REEMPLAZA1 (L, S, R);
{  REEMPLAZA2 (L, S, R); }
{  REEMPLAZA3 (L, S, R); }
   L.IMPRIME ('lista final L:');

   writeln ;
   writeln ('Ejemplo 3: ');
   L.ANULA;
   S.ANULA;
   R.ANULA;
   { Llena L con la secuecia 1 2 3 4 5 1 2 3 4 5 1 2 3...  }
   for j := 1 to 4 do
      for k := 1 to 5 do
        L.INSERTA (k, L.FIN);
   L.IMPRIME ('lista inicial L:');
   { Define secuencia S y reemplaza R } 
   S.INSERTA (4, S.FIN);
   S.INSERTA (5, S.FIN);
   S.INSERTA (1, S.FIN);
   R.INSERTA (9, R.FIN);
   R.INSERTA (7, R.FIN);
   R.INSERTA (3, R.FIN);
   S.IMPRIME ('secuencia S:');
   R.IMPRIME ('reemplaza R:');
   REEMPLAZA1 (L, S, R);
{  REEMPLAZA2 (L, S, R); }
{  REEMPLAZA3 (L, S, R); }
   L.IMPRIME ('lista final L:');

end.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ Ejemplo 1: 
  lista inicial L: 11 12 13 
  secuencia     S:  1  2  3 
  reemplaza     R:  9  7  3 
  lista final   L: 11 12 13 

  Ejemplo 2: 
  lista inicial L:  1  2  3 
  secuencia     S:  1  2  3 
  reemplaza     R:  9  7  3 
  lista final   L:  9  7  3 

  Ejemplo 3: 
  lista inicial L: 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 
  secuencia     S: 4 5 1 
  reemplaza     R: 9 7 3 
  lista final   L: 1 2 3 9 7 3 2 3 9 7 3 2 3 9 7 3 2 3 
}

Generated by GNU enscript 1.6.1.