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 }