LABORATORIO 6: ESTRUCTURAS DINÁMICAS DE DATOS
LISTAS CIRCULARES
CONTENIDOS
|
1 |
|
|
2 |
|
|
3 |
|
|
4 |
|
|
5 |
- Diseñar e implementar una EDD simplemente referenciada circular a partir de nodos autoreferenciables
- Diseñar e implementar una EDD doblemente referenciada circular a partir de nodos autoreferenciables
Cada Estructura Dinámica de Datos posee –tal y como se ha visto hasta el momento- un comportamiento específico y como tal una lógica diferente para operarla, tanto así que no es lo mismo eliminar un nodo de una lista simplemente enlazada que uno de una de doble referencia, aunque la operación sea la misma, la lógica cambia.
Una nueva EDD se integrará a nuestro contexto conceptual: Estructura Circular.
¿Por qué utilizar una estructura Circular?
Respuesta:
Imaginemos por un segundo una lista simplemente enlazada, el movimiento siempre fluirá desde la cabeza en dirección hacia el final de la lista, pero ¿qué ocurre cuando desde el último nodo se necesita operar con el primero?, este es el punto diferencial de una estructura abierta (aquella en que algún nodo apunta a null) y una cerrada.
En una lista circular:
- No existe algún elemento que apunte a NULL
- Se integra una estructura tipo anillo
- Solo hay una cabeza
- La cabeza siempre será el siguiente enlace para algún nodo
- Se pueden llegar a crear recorridos en bucles infinitos
Si en una estructura tipo Circular no existe algún elemento que apunte a NULL, ¿Cómo se valida entonces el último elemento?
Respuesta:
El considerado como último nodo será aquel que en su parte siguiente apunta a la cabeza y precisamente en un método de búsqueda la comparación con el nodo cabeza será la que indique que no existen más elementos en la lista.
Pueden existir Listas Circulares Simplemente Enlazadas y Doblemente Enlazadas.
Gráficamente se tendría:
|
Simplemente
enzalada
|
Doblemente
enzalada
|
- Nótese que con simple o doble referencia, siempre se tendrá solo una cabeza
Veamos el siguiente caso, ¿qué ocurre cuando la lista está vacía y se va a insertar el primer nodo?
|
Antes
de insertar nodo a la lista
|
Después
de insertar nodo a la lista
|
Observamos que el primer nodo insertado en su parte siguiente apuntará a él mismo y simultáneamente será cabeza, lo que permitiría que se leyera como que ese nodo es primero y último simultáneamente.
Ahora bien, al insertar un segundo nodo los apuntadores tomarán la configuración gráfica descrita a continuación.
|
Antes
de insertar nodo a la lista
|
Insertando nodo a la lista
|
Insertando nodo a la lista
|
Casos de Análisis:
- Insertar un nodo como primero de la lista
- Insertar un nodo al final de la lista
- Inserción de un nodo intermedio
- Eliminación de cabeza
- Eliminación de nodo final
- Eliminación de un nodo intermedio
- Ordenamiento
- Búsqueda de un elemento
En el Modelo OO un nodo seguirá teniendo la misma connotación de una lista de simple o doble referencia, según sea el caso.
TAD LISTA CIRCULAR SIMPLEMENTE ENLAZADA
Inicialmente trabajemos una Estructura de Datos que en cada nodo se almacene un objeto que posea como atributos tan solo caracteres.
NOMBRE: LISTA_CIRCULAR_SIMPLE
OBJETO ABSTRACTO: LISTA
Una lista es la sucesión de espacios de memoria vinculados de tal manera que el último encadenamiento debe apuntar al primero.
Lista es una ED Lineal que puede crecer de manera ilimitada (realmente su límite es la memoria ram) según las pretensiones del cliente en tiempo de ejecución.
INVARIANTE:
Lista será controlada por un solo apuntador: cabeza que referenciará en primera instancia NULL y cuando se posicionen uno o más nodos en la Estructura, siempre cabeza referenciará al primero de ellos a menos que el usuario pretenda actualizarlo.
Toda creación de un nodo implicará poner en nulo su espacio autoreferenciable.
Todo nodo se relacionará hacia delante a lo sumo con un nodo a partir de la dirección de memoria donde se encuentra definido. Para todo nodo debe haber claridad en su sucesor y antecesor.
DOMINIO DE LA ESTRUCTURA:
Lista poseerá tantos nodos como el usuario en tiempo de ejecución desee.
Cada nodo poseerá un carácter y
la respectiva referencia.
OPERACIONES:
CreaNodo.
Descripción: Realiza la
solicitud del espacio de almacenamiento para almacenar un nodo.
Datos de ingreso: Apuntador a Nodo.
Datos de salida: Espacio de almacenamiento referenciado por el apuntador a Nodo.
Precondición: Apuntador a
Nodo se encuentra inicializado a NULL.
Postcondición: Apuntador a Nodo poseerá una dirección de memoria, si es nula se interpretará como la imposibilidad de obtener espacio de almacenamiento, por lo que el objeto no se creará.
InsertaInicio.
Descripción: Inserta un
nodo en la posición referenciada por el apuntador Cabeza.
Datos de ingreso: Apuntador a Nodo.
Datos de salida: Apuntador a Cabeza.
Precondición: True.
Postcondición: Lista poseerá uno o más elementos. Cabeza apuntará a una dirección física.
InsertaAntes.
Descripción: Inserta un
nodo en la posición previa a la que posee el carácter de ingreso. Actualiza la estructura Lista.
Datos de ingreso: Apuntador Cabeza, Apuntador a Nodo, Caracter.
Datos de salida: Apuntador a Cabeza, o mensaje de imposibilidad de ingresar el nodo, dada la ausencia en la estructura de aquel nodo que posea como elemento al Carácter buscado.
Precondición: True
Postcondición: Lista podrá poseer un elemento más.
InsertaDespues.
Descripción: Inserta un
nodo en la posición posterior a la que posee el carácter de ingreso. Actualiza a estructura Lista.
Datos de ingreso: Apuntador Cabeza, Apuntador a Nodo, Caracter.
Datos de salida: Apuntador a Cabeza, o mensaje de imposibilidad de ingresar el nodo, dada la ausencia en la estructura de aquel nodo que posea como elemento al Carácter buscado.
Precondición: True
Postcondición: Lista podrá poseer un elemento más.
VisualizaLista.
Descripción: Permite
verificar los elementos de la Lista, partiendo de la Cabeza
Datos de ingreso: Apuntador a Cabeza.
Datos de salida: Ninguno.
Precondición: El usuario
ha seleccionado la cabeza desde la cual hará la visualización.
Postcondición: De ninguna manera la estructura será actualizada.
EliminaNodo.
Descripción: Permite
prescindir del nodo que posee el Carácter de ingreso (si existe), actualizando
la estructura.
Datos de ingreso: Apuntador Cabeza, Carácter.
Datos de salida: Cabeza con estructura modificada, entero 1: fue eliminado, 0: no eliminado.
Precondición: True
Postcondición:
De encontrarse el nodo con el carácter buscado, Lista poseerá un elemento menos,
de manera contraria se retornará valor para emitir mensaje de nodo no
encontrado.
BuscaNodo.
Descripción: Recorre la
estructura hasta alcanzar el nodo que contiene el carácter buscado.
Datos de ingreso: Apuntador Cabeza, Carácter.
Datos de salida: 1 si el nodo ha sido encontrado, 0 de manera contraria.
Precondición: True
Postcondición: De ninguna manera la estructura será actualizada.
OrdenaLista.
Descripción: Actualiza la
lista, teniendo en cuenta un orden ascendente según los nodos que se tienen.
Datos de ingreso: Apuntador Cabeza.
Datos de salida: Apuntador a Cabeza y estructura modificada.
Precondición: True
Postcondición: Se contará al término de la operación con todos los nodos que se tenían a su inicio.
CuentaNodos.
Descripción: determina la
longitud de la estructura a partir del número de nodos que posee Lista.
Datos de ingreso: Apuntador Cabeza.
Datos de salida: Número entero igual o superior a cero.
Precondición: True
Postcondición: La estructura no será modificada.
- Implemente el TAD mencionado preliminarmente, nótese que estructuralmente el archivo de Definición y la Interfaz seguirán siendo iguales a los definidos en La Lista Simplemente Enlazada. NOTA. Puede usted llegar a considerar nuevas operaciones para soportar las solicitadas.
- Defina e implemente un TAD Lista circular doblemente Enlazada.
- Construya otro ejercicio –derivado-, en el que cada nodo conserve la información básica de un empleado (nombre, fechas de nacimiento y vinculación, identificación, salario básico, total deducciones). Explote enormemente el uso de memoria dinámica. Emplee una Lista circular Doblemente Enlazada.
- Listas tipo Pila
- Listas tipo Cola