TAD Lista Ordenada
Implementación mediante listas enlazadas
La siguiente unidad representa una posible implementación del TAD lista ordenada cuyas operaciones están definidas en ésta página. Los elementos se representan mediante nodos de una lista doblemente enlazada. Aunque se pueden utilizar otras variantes (lista simplemente enlazada con nodo cabecera, por ejemplo), la elegida es la que produce una codificación más sencilla (particularmente en las operaciones borrar y reordenar). Se debe señalar que se ha intentado presentar un código lo más claro posible, por lo que en algunos casos se definen más variables de las estrictamente necesarias.
El tipo de datos se representa mediante el registro de tipo TListaOrd, el cual almacena punteros al nodo inicial de la lista y al nodo que almacena la referencia al elemento actual. Como es habitual, el valor nil se utiliza cuando no existe nodo inicial (lista vacía) o elemento actual.
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 lista2.pas. Puede descargarse directamente el fichero pulsando aquí.
unit Lista2;
interface
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. }
PNodo = ^TNodo;
TNodo = record
Elem: pointer;
Ant,Sig: PNodo
end;
TListaOrd = record
Primero,Actual : PNodo;
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.Primero := nil;
L.Actual := nil;
L.MenorIgual := fMenorIgual
end;
procedure Destruir(var L: TListaOrd);
var P : PNodo;
begin
{ Atención: En este subprograma destruimos los nodos, NO los elementos.
El destruir los elementos es responsabilidad del programa. }
while L.Primero <> nil do
begin
P := L.Primero;
L.Primero := L.Primero^.Sig;
dispose(P)
end;
L.Actual := nil
end;
function ListaLlena(L: TListaOrd) : boolean;
begin
{ Se supone una memoria de capacidad infinita }
ListaLlena := false
end;
function ElemActual(L: TListaOrd) : pointer;
begin
{ Atención: Un error bastante frecuente consiste en confundir nodos con elementos.
Si escribiesemos ElemActual := L.Actual, la unidad compilaría sin dar error, pero
estaríamos devolviendo un puntero al nodo, no al elemento. Este puntero se interpretaría
en el programa como un puntero a elemento, provocando errores muy dificiles de depurar. }
if L.Actual = nil then ElemActual := nil else ElemActual := L.Actual^.Elem
end;
procedure IrAInicio(var L: TListaOrd);
begin
L.Actual := L.Primero
end;
procedure IrASiguiente(var L: TListaOrd);
begin
if L.Actual <> nil then L.Actual := L.Actual^.Sig
end;
procedure Buscar(var L: TListaOrd; Elem: pointer);
var
P : PNodo;
Seguir : boolean;
begin
{ Algoritmo de búsqueda secuencial }
P := L.Primero;
Seguir := true;
while (P <> nil) and Seguir do
if L.MenorIgual(Elem,P^.Elem) then { P^.Elem ³ Elem }
Seguir := false
else
P := P^.Sig;
{ Se cumple que P = nil (en cuyo caso todos los elementos de la lista son menores que Elem),
o bien P^.Elem ³ Elem y todos los elementos de la lista anteriores a P son menores que Elem. }
L.Actual := P
end;
procedure Insertar(var L: TListaOrd; Elem: pointer);
var
P,Q,N : PNodo;
begin
if L.Primero = nil then
begin
{ Caso especial inserción en lista vacía }
new(L.Primero);
L.Primero^.Elem := Elem;
L.Primero^.Ant := nil;
L.Primero^.Sig := nil;
L.Actual := L.Primero
end else begin
{ El objetivo es que P apunte al último nodo menor o igual que Elem y Q
apunte al primer nodo mayor que Elem (P y Q son contiguos). El punto de
inserción será entre P y Q. }
Q := L.Primero;
while L.MenorIgual(Q^.Elem,Elem) and (Q^.Sig <> nil) do
Q := Q^.Sig;
if L.MenorIgual(Q^.Elem,Elem) then
begin
{ Q es el último nodo, Q^.Elem £ Elem => Elem es mayor que todos }
P := Q;
Q := nil
end else
P := Q^.Ant;
{ 2. Creación del nodo e inserción entre P y Q }
new(N);
N^.Elem := Elem;
N^.Ant := P;
N^.Sig := Q;
if P <> nil then P^.Sig := N else L.Primero := N;
if Q <> nil then Q^.Ant := N;
L.Actual := N;
end
end;
procedure Borrar(var L: TListaOrd);
var P,Q : PNodo;
begin
{ Por la precondición sabemos que L.Actual es distinto a nil }
P := L.Actual^.Ant;
Q := L.Actual^.Sig;
{ Actualización de enlaces del elemento anterior (P) y posterior (Q) }
if P <> nil then P^.Sig := Q else L.Primero := Q;
if Q <> nil then Q^.Ant := P;
{ Destrucción del nodo }
dispose(L.Actual);
{ El nuevo elemento actual es el siguiente }
L.Actual := Q;
end;
procedure Reordenar(var L: TListaOrd; fMenorIgual: TFuncComp);
{ Subprogramas usados por Reordenar: Representan la implementación
de la ordenación por fusión adaptada a listas enlazadas }
procedure Fusion(Lis1,Lis2: PNodo; N1,N2: integer; MenorIgual: TFuncComp);
{ Fusiona las dos sublistas contiguas que comienzan por los nodos Lis1 y Lis2
y contienen, respectivamente, N1 y N2 elementos. }
var P,Q,R: PNodo;
begin
while (N1 > 0) and (N2 > 0) do
if MenorIgual(Lis1^.Elem,Lis2^.Elem) then
begin
{ Continua fusionando. La primera lista pierde su primer elemento. }
Lis1 := Lis1^.Sig;
N1 := N1-1
end else begin
{ Se suprime el primer nodo de la segunda lista }
P := Lis2^.Ant;
Q := Lis2;
R := Lis2^.Sig;
P^.Sig := R;
if R <> nil then R^.Ant := P;
{ Se Inserta antes del primer nodo de la primera lista }
P := Lis1^.Ant;
Q^.Ant := P;
Q^.Sig := Lis1;
Lis1^.Ant := Q;
if P <> nil then P^.Sig := Q;
{ Continua fusionando. La segunda lista pierde su primer elemento. }
Lis2 := R;
N2 := N2-1
end
end;
procedure OrdFusion(var Ini: PNodo; N: integer; MenorIgual: TFuncComp);
{ Ordena la sublista doblemente enlazada que comienza por el nodo Ini y contiene N
elementos. Devuelve en Ini el nuevo nodo inicial de la lista ya ordenada. }
var
I : integer;
N1,N2 : integer;
Ini1,Ini2 : PNodo;
begin
if N > 1 then
begin
{ Número de elementos de cada mitad }
N1 := N div 2;
N2 := N-N1;
{ Nodos iniciales de cada mitad }
Ini1 := Ini;
Ini2 := Ini; for I := 1 to N1 do Ini2 := Ini2^.Sig;
{ Ordena la primera mitad }
OrdFusion(Ini1,N1,MenorIgual);
{ Ordena la segunda mitad }
OrdFusion(Ini2,N2,MenorIgual);
{ Ini1 e Ini2 habran cambiado tras la ordenación de cada mitad ya que el
primer elemento de cada sublista no será el mismo que antes. Ahora se
calcula cual va a ser el nuevo nodo inicial de la sublista tras la
fusión de las dos mitades: }
if MenorIgual(Ini1^.Elem,Ini2^.Elem) then
{ El primer elemento de la primera mitad ordenada }
Ini := Ini1
else
{ El primer elemento de la segunda mitad ordenada }
Ini := Ini2;
{ Fusión de las dos mitades }
Fusion(Ini1,Ini2,N1,N2,MenorIgual);
end
end;
var
N : integer;
P : PNodo;
begin { Reordenación }
{ Se cambia la función que compara dos elementos entre sí }
L.MenorIgual := fMenorIgual;
{ Se cuenta el número de elementos de la lista }
N := 0;
P := L.Primero;
while P <> nil do
begin
N := N+1;
P := P^.Sig
end;
{ Se reordena la lista }
OrdFusion(L.Primero,N,L.MenorIgual);
{ Tras reordenar, no existe elemento actual }
L.Actual := nil
end;
end. { Unidad Lista2 }