TAD Lista Ordenada

Implementación mediante arrays

La siguiente unidad representa una posible implementación del TAD lista ordenada cuyas operaciones están definidas en ésta página. El tipo de datos se representa mediante el registro de tipo TListaOrd, el cual almacena un array estático donde se guardan las direcciones de las variables dinámicas que representan los elementos, un campo indicando el número de elementos almacenados, otro que indica el índice del elemento actual y una referencia a la función encargada de realizar la comparación entre elementos a fin de garantizar que la lista se encuentre siempre ordenada.

En un momento dado el estado de la lista se encuentra representado por los valores almacenados en los campos de ese registro. Las direcciones de los elementos se almacenan en las posiciones 1..NumElem del array Vec, y el índice del elemento actual, ElemAct, puede tomar cualquier valor entre 1..NumElem+1. Si toma el valor NumElem+1 significa que no existe elemento actual, y una llamada a ElemActual devolverá el valor nil.

Nota: Si se desea copiar el texto en el editor de Turbo-Pascal, se debe tener cuidado de eliminar los acentos y otros caracteres especiales que aparecen en los comentarios, sino puede dar un error de compilación. Tambien se debe tener en cuenta de que el nombre del fichero debe ser igual al identificador de la unidad, en este caso debería llamarse lista1.pas. Puede descargarse directamente el fichero pulsando aquí.

Nota: Los conceptos de invariante, variante, precondición y postcondición se verán en el tema 5 (verificación).


unit Lista1;

interface

const MaxElem = 1000;

type
  TFuncComp = function(Elem1,Elem2: pointer) : boolean;
  { Las funciones utilizadas en este TAD deben devolver el valor true
    cuando Elem1 sea menor o igual que Elem2. } 

  TListaOrd = record
                Vec : array[1..MaxElem] of pointer;
                NumElem : 0..MaxElem;
                ElemAct : 1..MaxElem+1;
                MenorIgual : TFuncComp
              end;

  procedure Inicializar(var L: TListaOrd; fMenorIgual: TFuncComp);
  procedure Destruir(var L: TListaOrd);
  function  ListaLlena(L: TListaOrd) : boolean;
  function  ElemActual(L: TListaOrd) : pointer;
  procedure IrAInicio(var L: TListaOrd);
  procedure IrASiguiente(var L: TListaOrd);
  procedure Buscar(var L: TListaOrd; Elem: pointer);
  procedure Insertar(var L: TListaOrd; Elem: pointer);
  procedure Borrar(var L: TListaOrd);
  procedure Reordenar(var L: TListaOrd; fMenorIgual: TFuncComp);

implementation

  procedure Inicializar(var L: TListaOrd; fMenorIgual: TFuncComp);
  begin
    L.NumElem := 0;
    L.ElemAct := 1; { Uno más que el número de elementos }
    L.MenorIgual := fMenorIgual
  end;

  procedure Destruir(var L: TListaOrd);
  begin
    { En esta implementación no hay que hacer nada }
  end;

  function ListaLlena(L: TListaOrd) : boolean;
  begin
    ListaLlena := L.NumElem = MaxElem
  end;

  function ElemActual(L: TListaOrd) : pointer;
  begin
    if L.ElemAct > L.NumElem then
      ElemActual := nil
    else
      ElemActual := L.Vec[L.ElemAct]
  end;

  procedure IrAInicio(var L: TListaOrd);
  begin
    L.ElemAct := 1;
  end;

  procedure IrASiguiente(var L: TListaOrd);
  begin
    if L.ElemAct <= L.NumElem then L.ElemAct := L.ElemAct+1
  end;

  procedure Buscar(var L: TListaOrd; Elem: pointer);
  var Ini,Med,Fin : integer;
  begin
    { Algoritmo de búsqueda binaria }
    Ini := 1;
    Fin := L.NumElem;
    while Ini <= Fin do
    begin
      { Invariante: " I : 1 £ I < Ini : Vec[I] < Elem
                    " I : Fin < I £ NumElem : Vec[I] ³ Elem }
      { Variante: Fin-Ini }
      Med := (Ini+Fin) div 2;
      if L.MenorIgual(Elem,L.Vec[Med]) then
        Fin := Med-1
      else { Elem > V[Med] }
        Ini := Med+1
    end;
    L.ElemAct := Fin+1
    { Postcondición: Ini = Fin+1
                     " I : 1 £ I £ Fin : Vec[I] < Elem
                     " I : Fin+1 £ I £ NumElem : Vec[I] ³ Elem }
  end;

  procedure Insertar(var L: TListaOrd; Elem: pointer);
  var I : integer;
  begin
    { 1. Localizar el lugar de inserción (I+1) y desplazar los elementos }
    if L.NumElem = 0 then
      I := 0 { Caso especial de insercion del primer elemento }
    else
    begin
      I := L.NumElem;
      while (I > 1) and not L.MenorIgual(L.Vec[I],Elem) do
      begin
        { Invariante: " J : 1 < I £ J £ NumElem : Vec[J] > Elem }
        { Variante: I }
        L.Vec[I+1] := L.Vec[I];
        I := I-1
      end;
      { Cuando el bucle llega a I = 1 se detiene, aunque es posible que el punto de
        inserción no sea I+1 = 2, sino I+1 = 1, cuando Elem es menor que todos }
      if (I = 1) and not L.MenorIgual(L.Vec[1],Elem) then
      begin
        { Caso especial: Insercion de elemento menor que todos, falta un desplazamiento. }
        L.Vec[2] := L.Vec[1];
        I := 0
      end
      { Postcondición: (Vec[I] = Vec[I+1]) Ù
                       (" J : 1 £ J £ I : Vec[J] £ Elem) Ù
                       (" J : I+1 < J £ NumElem+1 : Vec[J] > Elem) }
    end; { if }
    { 2. Insercion }
    L.Vec[I+1] := Elem;
    { 3. Adaptacion del elemento actual y del número de elementos }
    L.ElemAct := I+1;
    L.NumElem := L.NumElem+1
  end;

  procedure Borrar(var L: TListaOrd);
  var I : integer;
  begin
    I := L.ElemAct;
    { Se desplazan una posición a la izquierda todos los elementos
      posteriores al actual }
    while I < L.NumElem do
    begin
      L.Vec[I] := L.Vec[I+1];
      I := I+1
    end;
    { Se decrementa el número de elementos. El indice al elemento actual no se cambia
      ya que tras haber borrado el elemento actual, ese indice apunta al elemento
      que le seguía, tal como establece la postcondición }
    L.NumElem := L.NumElem-1
  end;

  procedure Reordenar(var L: TListaOrd; fMenorIgual: TFuncComp);

    { Subprogramas usados por Reordenar: Representan la implementación
      clásica de la ordenación rápida (Quicksort) }

    procedure Particion(var L: TListaOrd; Ini,Fin,PosPiv: integer;
                        var UltMen,PriMay : integer);
    var
      Izda,Dcha : integer;
      Pivote,Temp : pointer;
    begin
      Pivote := L.Vec[PosPiv];
      Izda := Ini;
      Dcha := Fin;
      repeat
        { Invariante: " I : Ini £ I < Izda : Vec[I] £ Pivote
                      " I : Dcha < I £ Fin : Vec[I] ³ Pivote }
        { Variante: Dcha-Izda }
        while not L.MenorIgual(Pivote,L.Vec[Izda]) do Izda := Izda+1;
        { while L.Vec[Izda] < Pivote do Izda := Izda+1; }
        while not L.MenorIgual(L.Vec[Dcha],Pivote) do Dcha := Dcha-1;
        { while L.Vec[Dcha] > Pivote do Dcha := Dcha-1; }
        if Izda <= Dcha then
        begin
          { Intercambio de elementos entre Vec[Izda] y Vec[Dcha] }
          Temp := L.Vec[Izda]; L.Vec[Izda] := L.Vec[Dcha]; L.Vec[Dcha] := Temp;
          Izda := Izda+1;
          Dcha := Dcha-1
        end
      until Izda > Dcha;
      UltMen := Dcha;
      PriMay := Izda
    end;

    procedure OrdRapida(var L: TListaOrd; Ini,Fin: integer);
    var
      PriMay,UltMen,PosPivote : integer;
    begin
      if Ini < Fin then
      begin
        PosPivote := (Ini+Fin) div 2;
        Particion(L,Ini,Fin,PosPivote,UltMen,PriMay);
        OrdRapida(L,Ini,UltMen);
        OrdRapida(L,PriMay,Fin)
      end
    end;

  begin { Reordenación }
    { Se cambia la función que compara dos elementos entre sí }
    L.MenorIgual := fMenorIgual;
    { Se reordena el vector, usando el algoritmo de ordenación rápida }
    OrdRapida(L,1,L.NumElem);
    { Tras reordenar, no existe elemento actual }
    L.ElemAct := L.NumElem+1
  end;

end. { Unidad Lista1 }