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 }