Listas Estáticas en Pascal: Implementación de ListaEst2 con Arrays y Punteros

Unidad ListaEst2: Implementación de una Lista Estática en Pascal

La unidad ListaEst2 implementa una lista enlazada estática mediante un array de nodos, sin utilizar punteros dinámicos. Usa el TAD ElemTAD para los elementos almacenados.

Declaraciones

unit ListaEst2;
interface
uses ElemTAD;
const
N = 10;
INICIO = 1;
type
TNodo = record
info: TElemento;
sig: 0..N;
end;
TAlmacen = array [INICIO..N] of TNodo;
TListaEst = record
almacen: TAlmacen;
cabLib, cabOcu: 0..N;
end;

implementation

Procedimiento CrearVacia

Inicializa la lista: enlaza todas las posiciones como lista libre, marca la lista ocupada como vacía (cabOcu = 0) y establece la primera posición libre en cabLib = 1.

PROCEDURE CrearVacia(VAR l: TListaEst);
VAR
i: INICIO..N;
BEGIN
FOR i := INICIO TO N-1 DO
l.almacen[i].sig := i+1;
l.almacen[N].sig := 0;
l.cabOcu := 0;
l.cabLib := 1;
END;

Procedimiento Construir

Inserta un elemento al inicio de la lista ocupada, tomando una posición de la lista libre.

PROCEDURE Construir(VAR l: TListaEst; e: TElemento);
VAR
aux: integer;
BEGIN
aux := l.cabOcu; {guardamos final de lista cabOcu = 0}
Asignar(l.almacen[l.cabLib].info, e);
l.cabOcu := l.cabLib; {la cabLib pasa a ser ocupada}
l.cabLib := l.almacen[l.cabOcu].sig; {la siguiente posición a la ocupada será la nueva libre}
l.almacen[l.cabOcu].sig := aux; {enlazamos la posición ocupada con el antiguo inicio, finalizando en 0}
END;

Procedimiento Primero

Devuelve en e el primer elemento de la lista, si no está vacía.

PROCEDURE Primero(VAR e: TElemento; l: TListaEst);
BEGIN
IF NOT EsVacia(l) THEN
e := l.almacen[l.cabOcu].info;
END;

Procedimiento Resto

Elimina el primer elemento de la lista, devolviendo su posición a la lista libre. Modifica la lista original.

PROCEDURE Resto(VAR l: TListaEst); {Modifica la lista original}
VAR
aux: integer;
BEGIN
IF NOT EsVacia(l) THEN
BEGIN
aux := l.cabLib; {guardamos la posición libre que teníamos}
l.cabLib := l.cabOcu; {la posición que estaba ocupada ahora es libre}
l.cabOcu := l.almacen[l.cabOcu].sig; {nos movemos un elemento hacia delante en la lista}
l.almacen[l.cabLib].sig := aux; {enlazamos lo que era ocupado con la antigua lista libre}
END;
END;

Función EsVacia

Indica si la lista no contiene elementos ocupados (cabOcu = 0).

FUNCTION EsVacia(l: TListaEst): boolean;
BEGIN
EsVacia := (l.cabOcu = 0);
END;

Función Longitud

Devuelve el número de elementos ocupados recorriendo la lista.

FUNCTION Longitud(l: TListaEst): integer;
VAR
aux, i: integer;
BEGIN
i := 0;
IF NOT EsVacia(l) THEN
aux := l.cabOcu;
WHILE aux <> 0 DO
BEGIN
i := i+1;
aux := l.almacen[aux].sig;
END;
Longitud := i;
END;

Procedimiento Ultimo

Devuelve en e el último elemento de la lista.

PROCEDURE Ultimo(VAR e: TElemento; l: TListaEst);
VAR
aux: integer;
BEGIN
IF NOT EsVacia(l) THEN
aux := l.cabOcu;
WHILE l.almacen[aux].sig <> 0 DO
BEGIN
aux := l.almacen[aux].sig;
END;
e := l.almacen[aux].info;
END;

Función Pertenece

Comprueba si el elemento e se encuentra en la lista.

FUNCTION Pertenece(l: TListaEst; e: TElemento): boolean;
VAR
aux: integer;
BEGIN
IF NOT EsVacia(l) THEN
Pertenece := FALSE;
aux := l.cabOcu;
WHILE ((aux <> 0) AND (l.almacen[aux].info <> e)) DO
BEGIN
aux := l.almacen[aux].sig;
END;
IF (l.almacen[aux].info = e) THEN
Pertenece := TRUE;
END;

Procedimiento Concatenar

Añade los elementos de l2 al final de l, mientras haya espacio disponible.

PROCEDURE Concatenar(VAR l: TListaEst; l2: TListaEst);
VAR
aux: integer;
BEGIN
aux := l.cabOcu;
WHILE l.almacen[aux].sig <> 0 DO
aux := l.almacen[aux].sig;
WHILE (NOT EsVacia(l2)) AND (NOT EsLlena(l)) DO
BEGIN
Primero(e, l2);
Resto(l2);
InsertarFinal(l, e);
END;
END;

Procedimiento BorrarElemento

Elimina de la lista la primera aparición del elemento e, devolviendo su posición a la lista libre.

PROCEDURE BorrarElemento(VAR l: TListaEst; e: TElemento);
VAR
aux, aux2: integer;
BEGIN
IF NOT EsVacia(l) THEN
aux := l.cabOcu;
aux2 := l.cabLib;
WHILE (aux <> 0) AND (l.almacen[aux].info <> e) DO
aux := l.almacen[aux].sig;
aux2 := l.almacen[aux2].sig;
IF (l.almacen[aux].info = e) THEN
END;
END.