LABORATORIO 5: ESTRUCTURAS DINÁMICAS DE DATOS
LISTAS DOBLEMENTE ENLAZADAS
CONTENIDOS
|
1 |
|
|
2 |
|
|
3 |
|
|
3.1 |
|
|
3.2 |
|
|
4 |
|
|
5 |
- Diseñar e implementar una EDD doblemente referenciada a partir de nodos autoreferenciables
Ahora que se ha conceptualizado, analizado e implementado Estructuras Dinámicas de Datos Simplemente en las que cada nodo posee un solo enlace, se pretende incrementar el nivel de complejidad fijando un doble enlace.
¿Por qué utilizar una doble referencia (enlace)?
Respuesta:
Siempre que se
requiere alcanzar a algún nodo de la estructura, se hace un recorrido en un único
sentido, para una lista simplemente enlazada, partiendo de una única referencia
siempre vigente durante toda la ejecución del programa: NODO CABEZA. A partir de esto, si se quisiera referenciar
un nodo previo, se tendría que con un nuevo apuntador empezar a recorrer la
lista desde la Cabeza hasta alcanzar la ubicación deseada, situación que hace
del proceso algo muy dispendioso computacionalmente. En tanto, si existe una doble referencia, para
determinar a un nodo previo bastará con emplear el enlace anterior y para uno
siguiente, emplear el enlace siguiente.
Un nodo será visualizado gráficamente así:
Nótese que Anterior y Siguiente son apuntadores que referencian a otro nodo, por lo tanto van a poseer solo direcciones de memoria.
- La creación de un nuevo nodo implica:
o Solicitar el espacio a la memoria principal
o Verificar la validez del espacio (la memoria puede no entregarlo)
o Depositar la información básica del nodo y fijar las referencias inicialmente a NULL
o Insertarlo dentro de la estructura reorganizando referencias (vínculos)
- En una Lista doblemente enlazada se tiene dos Nodos Cabeza.
- Se podría verificar la estructura como dos Listas, donde una cabeza es el último nodo de una lista y de manera complementaria.
- El enlace anterior del Nodo Cabeza 1 apuntará a NULL
- El enlace siguiente del Nodo Cabeza 2 apuntará a NULL
- Los recorridos pueden hacerse por cualquiera de las dos cabezas
Veamos el siguiente caso:
El nodo creado se desea integrar a la Estructura, por lo tanto se debe verificar la posición donde se quiere insertar y reordenar las referencias; en nuestro caso particular, El nodo 5 cambiará su referencia hacia la dirección donde se encuentra el nodo 7
y posteriormente el nodo 4 cambia su referencia hacia el nodo 5.
Ahora Nodo 5 entrega su referencia Anterior a Nodo 4
Y finalmente Nodo 7 actualiza su referencia a nodo 5, quedando la lista dispuesta de la siguiente manera:
Casos de Análisis:
- Inicialización con cero nodos
- Inserción del primer nodo en la lista
- Insertar un nodo en la cabeza. Se requiere conocer en cual cabeza se hará la inserción
- Insertar un nodo al final de una cabeza
- Inserción de un nodo intermedio
- Eliminación de cabeza
- Eliminación de nodo final
- Ordenamiento
En el Modelo OO, ¿cómo se constituye un nodo? R/ Un nodo será la instanciación de una clase (es decir un objeto).
Note que tanto Siguiente como Anterior son dos Atributos más que resulta nindispensables para producir el enlace (liga) entre un nodo y otro, siendo un apuntador del mismo tipo de dato de la clase. Esta justamente es la razón por la cual se denomina EDD autoreferenciada.
TAD LISTA SIMPLEMENTE ENLAZADA
Inicialmente trabajemos una Estructura de Datos que en cada nodo se almacene un objeto que posea como atributos
NOMBRE: LISTADOBLEENLACE
OBJETO ABSTRACTO: LISTA
Note que cada arista (à ) es realmente una dirección de memoria.
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 dos apuntadores: cabeza1, cabeza2 que referenciarán en primera instancia NULL y cuando se posicionen uno o más nodos en la Estructura, siempre cabeza1 referenciará al primero de ellos y cabeza2 el nodo del extremo contrario.
Toda creación de un nodo implicará poner en nulo sus espacios autoreferenciales.
Todo nodo se relacionará a lo sumo con dos nodos 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 las
respectivas referencias.
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 Cabeza1, o Cabeza2,
según sea el caso, actualizando
la estructura.
Datos de ingreso: Apuntador a Nodo, Apuntador a Cabeza (según selección).
Datos de salida: Apuntadores a Cabeza1 y Cabeza2.
Precondición: el usuario
ha determinado la cabeza en la que se hará la inserción.
Postcondición: Lista poseerá uno o dos 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 (Cualquiera por la que se hará la búsqueda), Apuntador a Nodo, Caracter.
Datos de salida: Apuntadores a Cabeza1 y Cabeza2, 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 (Cualquiera por la que se hará la búsqueda), Apuntador a Nodo, Caracter.
Datos de salida: Apuntadores a Cabeza1 y Cabeza2, 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, según el seleccionado por el usuario.
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 (cualquiera según se desee realizar la búsqueda), 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 (cualquiera, según se desee la búsqueda), 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.
/*
INFORMACIàN ADMINISTRATIVA
Descripcion: Aplicaci¢n para el manejo de listas
simplemente enlazadas
Autor: MIGUEL ANGEL MENDOZA MORENO
Fecha: 13 de Septiembre de 2004
Plataforma: Windows
Asignatura: Laboratorio Estructuras de Datos I
*/
#ifndef
NODO_H
#define NODO_H
#include<stdlib.h>
//Se
empleará macro NULL
class Nodo{
char caracter;
Nodo *sig;
Nodo *ant;
public:
~Nodo(){delete sig;
delete ant;}
void setCaracter(char);
char getCaracter();
void setSig(Nodo*);
Nodo* getSig();
void setAnt(Nodo*);
Nodo* getAnt();
Nodo* creaNodo();
};
class Control{
Nodo *cabeza1, *cabeza2;
public:
Control(){cabeza1=cabeza2=NULL;}
~Control(){delete cabeza1;delete cabeza2}
void insertaInicio(Nodo *,Nodo *);
void insertaAntes(Nodo *, Nodo *,char);
void insertaDespues(Nodo *, Nodo *,char);
void visualizaLista(Nodo *);
int eliminaNodo(char);
int buscaNodo(char);
void ordenaLista();
int cuentaNodos();
};
#endif
ARCHIVO DE MANIPULACIÓN DEL CLIENTE: Interfaz
A continuación se presente un segmento de código para tratar la interfaz, bajo la consideración de una carga amplia en el manejo de streams en este archivo, mas no en la implementación.
#include"lista.h"
#include<iostream.h>
#include<conio.h>
int main(){
Control lista;
char opc=' ',dato;
int cab;
while(opc!='0'){
clrscr();
cout<<" MENU PRINCIPAL"<<endl;
cout<<"\t1. INSERTAR Nodo en la CABEZA\n";
cout<<"\t2. INSERTAR Nodo en el FINAL\n";
cout<<"\t3. INSERTAR Nodo antes de otro\n";
cout<<"\t4. INSERTAR Nodo despues
de otro\n";
cout<<"\t5. VISUALIZAR estado de la LISTA\n";
cout<<"\t6. REMOVER Nodo de la LISTA\n";
cout<<"\t7. BUSCAR Nodo en la LISTA\n";
cout<<"\t8. ORDENAR la LISTA\n";
cout<<"\t9. LONGITUD de la LISTA\n";
cout<<"\tO. Salir\n";
cout<<"\tOpci¢n: ";
cin.get(opc);
switch(opc){
case '1':
Nodo *nuevo;
if((nuevo=(*nuevo).creaNodo())==NULL){
cout<<"INSUFICIENTE
MEMORIA: Nodo no
creado!!!"<<endl;
cin.get();
}
else{
cout<<"Digite
Caracter ";
cin.ignore();
cin.get(dato);
(*nuevo).setCaracter(dato);
(*nuevo).setSig(NULL);
(*nuevo).setAnt(NULL);
do{cout<<"Seleccione Cabeza 1/2";
cin>>cab;}while(!(cab ==1
||cab==2));
if(cab==1)
lista.insertaInicio(nuevo,cabeza1);
else
lista.insertaInicio(nuevo,cabeza2);
}
break;
case '5':
do{cout<<"Seleccione
Cabeza 1/2";
cin>>cab;}while(!(cab ==1 ||cab==2));
if(cab==1)
lista.visualizaLista(cabeza1);
else
lista.visualizaLista(cabeza2);
break;
/* ETCÉTERA
*/
}
}
return 0;
}
- Implemente el TAD mencionado preliminarmente, soportándose en los archivos de definición e interfaz presentados previamente. NOTA. Puede usted llegar a considerar nuevas operaciones para soportar las solicitadas.
- 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.
Estructuras Dinámicas de Datos de tipo Circular (Simple y Doble enlace)