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.