Aplicacion del tema de listas

Ejemplos en la utilización de listas.

En este caso estaremos hablando de una lista general en la que sus elementos no tienen porque estar ordenados por su valor. Por otro lado, es necesario decir que existen muchas formas de definir una lista, y como veremos en apartados posteriores, existen numerosas estructuras relacionadas directamente con la lista y sus distintas variantes de su implementación que ofrecen diferentes propiedades de acceso.

-Implementación estática mediante un vector.
Una posible implementación de esta estructura en Pascal es la siguiente:
CONST
MAX = ... {Tamaño del vector y máximo tamaño posible de la lista}
TYPE
Posicion = 0 .. MAX;
Elemento = RECORD
info: ;
sig: Posicion
END;
TipoLista= RECORD
primero, vacios: Posicion;
mem = ARRAY [1..MAX] OF Elemento
END;
VAR
v:TipoLista;
UNCTION Nuevo(VAR L: TipoLista):Posicion;
BEGIN
IF L.vacios=0 THEN { no quedan componentes en el vector }
{ mensaje de error de lista llena }
ELSE BEGIN
Nuevo := L.vacios;
L.vacios := L.mem[L.vacios].sig
END
END;
PROCEDURE Liberar(VAR L: TipoLista; e: Posicion);
BEGIN
L.mem[e].sig := L.vacios;
L.vacios := e
END;
-Implementación dinámica de una lista con enlace simple.
La implementación directa de esta idea nos lleva a la siguiente estructura de datos en
Pascal
TYPE
Posicion = ^Elemento;
Elemento = RECORD
info:
sig: Posicion
END;
TipoLista = RECORD
longitud: INTEGER;
primero, ultimo: Posicion
END;
-Implementación dinámica como lista doblemente enlazada.
En este apartado queda como ejercicio la justificación de la implementación de las operaciones mostradas.
FUNCTION Anterior (L : TipoLista; p: Posicion ):Posicion;
BEGIN
Anterior := p^.ant
END;
PROCEDURE InsAntes( VAR L: TipoLista; p: Posicion; d: TipoBase );
VAR
aux : Posicion;
BEGIN
new (aux);
aux^.info := d;
IF ListaVacia(L) THEN BEGIN
L.primero := aux;
L.ultimo := aux;
aux^.sig := NIL;
aux^.ant := NIL
END
ELSE
IF p = Primero(L) THEN BEGIN
aux^.sig := Primero(L);
L.primero^.ant := aux;
aux^.ant := NIL;
L.primero := aux
END
ELSE BEGIN { cualquier posición }
aux^.ant := Anterior(L,p);
aux^.sig := p;
p^.ant^.sig := aux;
p^.ant := aux
END;
L.longitud := L.longitud+1
END;
PROCEDURE InsDespues( VAR L : TipoLista; p: Posicion; d: TipoBase );
VAR
aux: Posicion;
BEGIN
new(aux);
aux^.info := d;
IF ListaVacia(L) THEN BEGIN
aux^.sig := NIL;
aux^.ant := NIL;
L.primero := aux;
L.ultimo := aux
END
ELSE
IF p = Ultimo(L) THEN BEGIN
aux^.ant := Ultimo(L);
L.ultimo^.sig := aux;
aux^.sig := NIL;
L.ultimo := aux
END
ELSE BEGIN { cualquier posición }
aux^.ant := p;
aux^.sig := Siguiente (L,p);
p^.sig^.ant := aux;
p^.sig := aux
END;
L.longitud := L.longitud + 1
END;
PROCEDURE Borrar ( VAR L: TipoLista; p: Posicion );
VAR
aux1, aux2 : Posicion;
BEGIN
IF p = Primero(L) THEN BEGIN
L.primero := Siguiente(L,p);
IF Primero(L) = NIL THEN
L.ultimo := NIL
ELSE
L.primero^.ant := NIL
END
ELSE
IF p = Ultimo(L) THEN BEGIN
aux1 := Anterior (L,p);
L.ultimo := aux1;
aux1^.sig := NIL
END
ELSE BEGIN { Cualquier posición }
aux1 := Anterior (L,p);
aux2 := Siguiente (L,p);
aux1^.sig :=aux2;
aux2^.ant :=aux1
END;
dispose(p);
L.longitud := L.longitud - 1
END;
-Lista Ordenada.
El siguiente subprograma contempla todos los casos citados.
PROCEDURE InsOrd (VAR L: TipoLista; d: TipoBase );
VAR
aux1,aux2,ant : Posicion;
BEGIN
new(aux1); aux1^.info := d;
IF ListaOrdVacia(L) THEN BEGIN
L.primero := aux1;
L.ultimo := aux1;
aux1^.sig := NIL
END
ELSE
IF d <= Dato(L, Primero(L)) THEN BEGIN { se inserta el primero}
aux1^.sig := Primero (L);
L.primero:= aux1
END
ELSE BEGIN
aux2 := Primero(L);
WHILE (Dato(L,aux2) <> Ultimo(L)) DO BEGIN
ant := aux2;
aux2 := Siguiente (L,aux2)
END;
IF (Dato (L,aux2) >= d) THEN BEGIN
aux1^.sig := aux2;
ant^.sig := aux1
END
ELSE BEGIN { Se inserta despues del ultimo }
aux1^.sig := NIL;
L.ultimo^.sig := aux1;
L.ultimo := aux1
END
END;
L.longitud := L.longitud + 1
END;
-Multilista.
Al implementar la Multilista hemos elegido una estructura dinámica de enlace simple
para representar cada una de las listas que contiene.
TYPE
Alumno = RECORD
nombre, DNI: String;
nota: REAL
END;
Posicion = ^ElemMultList;
ElemMultList = RECORD
info: Alumno;
signom, sigdni, signot: Posicion
END;
Multilista = RECORD
primernom, primerdni, primernot: Posicion
END;
Referencias:
http://www3.uji.es/~sanchiz/Docencia/F05/tema5.pdf