Ejemplo de TAD - Lista ordenada

Ejemplo de Tipo Abstracto de Datos

Lista ordenada con acceso basado en cursor

1. Objetivos

En ésta página se presenta un ejemplo de definición de un tipo abstracto de datos (TAD) en Pascal, que representa una lista ordenada de elementos a los que se accede mediante cursor: De todos los elementos de la lista, en un momento dado sólo uno de ellos es accesible, al que se le llama cursor o elemento actual. Existen operaciones para hacer que el elemento actual sea el primero de la lista o para hacer que pase a ser el elemento que sigue al que era el actual. Mediante esas dos operaciones es posible acceder a todos los elementos de la lista.

Existen situaciones en las que el elemento actual no está definido: Cuando la lista estáa vacía, cuando se pasa al siguiente del último elemento, cuando se reordena la lista, cuando se busca un elemento de valor mayor que todos los existentes y cuando se borra el último elemento. En esos casos, al requerir el elemento actual se obtiene el valor nil.

Las operaciones de acceso y borrado se realizan sobre el elemento actual. La operación de inserción garantiza que el nuevo elemento se inserte en la posición adecuada de forma que la lista se mantenga siempre ordenada.

El definir el orden de los elementos es responsabilidad de quien utilize este TAD, el cual debe definir una función que se encargue de comparar dos elementos, y proporcionar al TAD una referencia a esa función para que pueda utilizarla cuando lo necesite. Este esquema permite, además, reordenar los elementos de la lista de acuerdo a un criterio distinto cuando sea necesario.

2. Definición del TAD Lista Ordenada

El siguiente listado muestra las operaciones que se pueden realizar sobre una lista ordenada, y los parámetros de entrada y salida de cada una. Se puede observar que todas reciben como entrada la lista sobre la que se realiza la operación. Exceptuando ElemActual y ListaLlena, todas las operaciones realizan cambios en el estado interno de la lista, y por lo tanto devuelven la lista modificada, por eso utilizan un paso por variable.

    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);

A continuación se muestra una tabla con las precondiciones y postcondiciones de cada operación. En principio, se puede asumir que las precondiciones representan los requisitos que se deben cumplir antes de llamar a esa operación, y por lo tanto son condiciones que debe garantizar el programa que desee utilizar esa operación. Las postcondiciones representan, en cierto modo, el propósito u objetivo de la operación, y son condiciones que la unidad que implementa el TAD garantiza que se van a cumplir tras la ejecución de la operación (siempre que se hallan cumplido las precondiciones).

En el tema 5 (Verificación) se verá una descripción más formal de las precondiciones y las postcondiciones, y de cómo se derivan de la técnica de programación bajo contrato.

Operaciones	Precondiciones	Postcondiciones
Inicializar	Ninguna	Inicializa la lista asignando la función de comparación proporcionada y estableciendo el número de elementos a cero y el elemento actual a ninguno.
Destruir	Lista inicializada	Se libera la memoria interna utilizada para representar la lista. Se establece el número de elementos a cero y el elemento actual a ninguno.
Lista llena	Lista inicializada	Comprueba si queda espacio en la lista para insertar un nuevo elemento.
Elemento actual	Lista inicializada	Se devuelve la dirección de memoria correspondiente al elemento actual de la lista, o el valor nil si no existe elemento actual o la lista está vacía.
Ir a inicio	Lista inicializada	El elemento actual pasa a ser el primero de la lista. Si la lista está vacía el elemento actual pasa a ser nil.
Ir a siguiente	Lista inicializada	El nuevo elemento actual pasa a ser el elemento que sigue en la lista al anterior elemento actual. Si el anterior elemento actual no existía o era el último el elemento actual pasa a ser nil.
Buscar	Lista inicializada	El elemento actual pasa a ser el primer elemento de la lista igual o mayor que el valor proporcionado. Las comparaciones entre elementos se realizan utilizando la función de comparación proporcionada en última llamada a Reordenar, o bien, si no se ha realizado ninguna, en la llamada a Inicializar. Si la lista está vacía o el valor proprocionado es mayor que todos los que existen en la lista, el elemento actual pasa a ser nil.
Insertar	Lista inicializada y no llena.	Se inserta el elemento dentro de la lista de forma que su elemento siguiente (si existe) sea estrictamente mayor y su elemento anterior (si existe) sea menor o igual. Las comparaciones entre elementos se realizan de la manera descrita en la operación Buscar. El elemento actual pasa a ser el elemento insertado.
Borrar	Lista inicializada y elemento actual distinto de nil	Se elimina el elemento actual de la lista. El nuevo elemento actual pasa a ser el siguiente al elemento eliminado. Si se elimina el último elemento de la lista el elemento actual pasa a ser nil.
Reordenar	Lista inicializada	Se asigna la función de comparación proporcionada a la lista y se reordenan los elementos de acuerdo a la nueva función de comparación. El elemento actual pasa a ser nil.

3. Implementaciones del TAD

Se proporcionan dos implementaciones distintas de este TAD: Una basada en arrays y otra basada en listas simplemente enlazadas. Aunque ambas se diferencian en la manera en que se almacenan los elementos y se realizan las operaciones, es importante darse cuenta que un programa que utilize este TAD no necesita tener esos cambios en cuenta: Dentro del programa, basta cambiar la linea uses Lista1 por uses Lista2 para que funcione con una u otra implementación y los resultados (excepto por el orden asintótico de las operaciones) serán exactamente los mismos.

Implementación basada en arrays (también se denomina listas contiguas). El orden de las operaciones y los algoritmos utilizados se muestran en la siguiente tabla:

Operaciones	Orden asintótico	Algoritmo
Inicializar	O(1)	Trivial
Destruir	O(1)	Trivial
Lista llena	O(1)	Trivial
Elemento actual	O(1)	Trivial
Ir a inicio	O(1)	Trivial
Ir a siguiente	O(1)	Trivial
Buscar	O(lg n)	Búsqueda binaria
Insertar	O(n)	Búsqueda secuencial con desplazamiento
Borrar	O(n)	Desplazamiento
Reordenar	O(n lg n) caso promedio O(n²) peor caso	Ordenación rápida (Quicksort)

Implementación basada en lista simplemente enlazada. El orden de las operaciones y los algoritmos utilizados se muestran en la siguiente tabla:

Operaciones	Orden asintótico	Algoritmo
Inicializar	O(1)	Trivial
Destruir	O(n)	Borrado de nodos
Lista llena	O(1)	Trivial
Elemento actual	O(1)	Trivial
Ir a inicio	O(1)	Trivial
Ir a siguiente	O(1)	Trivial
Buscar	O(n)	Búsqueda secuencial
Insertar	O(n)	Búsqueda secuencial e inserción
Borrar	O(1)	Trivial
Reordenar	O(n lg n)	Ordenación por fusión recursiva adaptada a listas

En las tablas anteriores, el valor n representa el número de elementos almacenados en ese momento en la lista.

4. Programas de ejemplo que usan el TAD

Programa que mantiene una lista ordenada de enteros y permite al usuario realizar operaciones de inserción, borrado, desplazamiento y reordenación.

Programa que muestra la estructura de un directorio y sus subdirectorios y permite ordenar los ficheros segun distintos criterios.