intercambi.pas

{ ppc386 -va -vh *.pas }
{ COMIENZO DE DESCRIPCION
  Escribir un procedure INTERCAMBIA (var L:lista); que
  intercambia los elementos de L de tal forma que aquellos
  que est\'an en una posici\'on impar son intercambiados con
  el elemento en la posici\'on par inmediatamente siguiente.
  Es decir, el primero es intercambiado con el segundo, el
  tercero con el cuarto y asi siguiendo. Si el n\'umero de
  elementos es impar, entonces el ultimo elemento queda
  inalterado. Asi por ejemplo, si la listas es
  L=(10 1 15 7 2 19 15 16 11 15 9 13 3 7 6 12 1)
  entonces despu\'es de intercambiar debemos tener
  L=(1 10 7 15 19 2 16 15 15 11 13 9 7 3 12 6 1).
  (Ejercicio tomado en el examen final de 9/5/2002).
  keywords:lista

FIN DE DESCRIPCION }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{$ Id: interca.pas  2003/03/12 16:30 mstorti Exp jdelia    $}

{ Supongamos que los elementos son (a,b,c,d,e,....) y en un
  cierto momento tenemos una posicion `p' correspondiente
  a una posicion par, por ejemplo, la que contiene al
  elemento `e'.

* Tomamos la posicion siguiente `q':

  a)    posicion:   p  q
                    |  |
                    v  v
  L = ( a  b  c  d  e  f  g    ........   )   <- elementos

* Guardamos el elemento en la posicion `q' en la variable
  `x' y suprimimos esa posicion `q'. 

b)   posicion:      p     x : = RECUPERA (q)
                    |        
                    v        
  L = ( a  b  c  d  e  g      ........   )   <- elementos

* Insertamos `x' en la posicion `p'. Notar que el
  elemento `f' queda en la posicion `p' 

c)  posicion:      p
                   |        
                   v        
 L = ( a  b  c  d  f  e  g    ........   )   <- elementos

* Avanzamos `p' dos posiciones hasta la siguiente posicion
  par. Como sabemos que seguro hay al menos un elemento,
  entonces al menos no hay que verificar si el primer
  `siguiente' da `fin de lista' o no. 

d) posicion:             p         
                         |
                         v
 L = ( a  b  c  d  f  e  g  ........   )   <- elementos }

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
program intercambia_p;

uses u_listpi;

type
  lista = listpi;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ atencion que hay que hacer el recupera *despues* de haber
  verificado que `q' no esta en el fin de la lista          }
procedure INTERCAMBIA (var L : lista);
var
  p, q : posicion;
  x    : tipo_elemento;
begin
  p := L.PRIMERO;
  while ( p <> L.FIN ) do begin
    q := L.SIGUIENTE (p) ;    { ver figura a) arriba }
    if (q = L.FIN) then exit;
    x := L.RECUPERA (q);
    L.SUPRIME (q);            { ver figura b) arriba }
    L.INSERTA (x,p);          { ver figura c) arriba }
    p := L.SIGUIENTE (p);
    p := L.SIGUIENTE (p);     { ver figura d) arriba }
  end;
end;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
var
  L : lista;
  k : integer;
begin
  randomize ;
  L.ANULA;
{ Insertamos un cierto numero aleatorio de elmentos }
  for k := 1 to (10 + random (10) ) do
      L.INSERTA ( random (20), L.FIN );
  L.IMPRIME ('Antes de intercambia: ');
  INTERCAMBIA (L);
  L.IMPRIME ('Despues de intercambia: ');
end.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}