LABORATORIO 4: ESTRUCTURAS DINÁMICAS DE DATOS
LISTAS SIMPLEMENTE ENLAZADAS
CONTENIDOS
|
1 |
|
|
2 |
|
|
3 |
|
|
3.1 |
|
|
3.2 |
|
|
4 |
|
|
5 |
- Conceptuar una Estructura Dinámica de Datos
- Contrastar una EDD (Estructura Dinámica de Datos) frente a una EED (Estructura Estática de Datos)
- Diseñar e implementar una EDD a partir de nodos autoreferenciables
- Una Estructura de Datos es una colección de elementos (objetos) que poseen cierta relación y ubicación, razón por la cual se encuentran vinculados física y lógicamente.
- Cada uno de los elementos de la Estructura se denomina Nodo.
- Nodos enlazados = Estructura de Datos.
- Una Estructura Estática de Datos vincula sus elementos físicamente por medio de espacios reservados en tiempo de compilación, por lo que conoce de manera previa de cuántos espacios se dispone, ante esta situación el tamaño de la estructura es rígido, lo que puede conllevar a un desperdicio de memoria.
- En una EED las eliminaciones, inserciones y reposicionamiento de nodos es una operación lógica, más no física.
- Generalmente las posiciones de memoria en EED son contiguas.
- Las Estructuras Dinámicas de Datos se crean físicamente en tiempo de ejecución, de modo que tendrá en todo momento la cantidad de elementos necesarios para operar.
- Las EDD emplean necesariamente apuntadores y como tal referencias a posiciones de memoria donde son alojados cada uno de los nodos a vincular.
- Las posiciones de memoria que emplean los elementos pueden encontrarse dispersas dentro del espacio de memoria primaria.
- Las EDD se clasifican en lineales y no lineales.
- Las EDD lineales se conocen como listas y se reconocen como referencias uno a uno entre elementos.
- Las EDD no lineales corresponden a niveles de elementos (jerarquización) con una vinculación múltiple y una distribución amplia, llegando a conformar redes. Caso tal de Árboles y Grafos.
- Una EDD lineal se evidenciará en la siguiente figura:
- 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
o Insertarlo dentro de la estructura reorganizando referencias (vínculos)
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.
Donde lógica y físicamente se alcanza:
Resultado:
Evaluemos dos posibles casos:
- ¿Qué ocurre cuando se desea insertar un nodo antes del inicial?. R/ El nuevo nodo será ahora el Nodo Cabecera.
- ¿Qué ocurre cuando se desea insertar un nodo luego del final?. R/ El nuevo nodo será ahora el Nodo Final.
- La Estructura conformada se denominará Lista, pues justamente se están relacionando (enlistando) los elementos (nodos) de manera consecutiva.
- La Lista constituida se denomina simplemente enlazada, debido a que existe solo un vínculo entre un nodo y otro, resulta importante notar que todo nodo poseerá una referencia, la pregunta sería ¿cuál es la referencia para el último nodo? R/ El último nodo referenciará a NULL y este es un instrumento poderoso para saber que el final de la lista lo denota este nodo.
- Así pues resultan evidentes las operaciones básicas que pueden desarrollarse con una EDD Lineal tipo Lista:
Básicas
para el Nodo:
o Insertar nodo
o Eliminar Nodo
o Modificar Nodo (Cambiar ya sea su información o su referencia)
Básicas
para la Lista:
o Recorrer y contar los nodos de la Lista
o Buscar un nodo
o Ordenar la Lista
- 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 Siguiente es un Atributo más que resulta indispensable 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: LISTAUNIENLACE
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 un apuntador denominado cabeza que referenciará en primera instancia NULL y cuando se posicionen uno o más nodos en la Estructura, siempre estará referenciando al primero de ellos.
Toda creación de un nodo implicará poner en nulo su espacio autoreferencial.
Todo nodo se relacionará a lo sumo con otro nodo a partir de la dirección de memoria donde se encuentra definido. Para todo nodo debe haber claridad en su sucesor y antecesor.
Tan solo puede existir una cabeza en toda la estructura y será siempre el primer nodo.
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, actualizando la
estructura.
Datos de ingreso: Apuntador a Nodo, Apuntador a Cabeza.
Datos de salida: Apuntador a Cabeza.
Precondición: True
Postcondición: Lista poseerá uno o dos elementos. Cabeza apuntará a una dirección física.
InsertaFinal.
Descripción: Inserta un
nodo en la posición subsiguiente al único nodo que posee referencia a NULL y
actualiza a estructura Lista.
Datos de ingreso: Apuntador a Nodo, Apuntador a Cabeza.
Datos de salida: Apuntador a Cabeza.
Precondición: True
Postcondición: Lista poseerá un elemento más. Cabeza seguirá apuntando a la dirección que posee. El ‘nodo recién insertado ahora es el último de la Lista.
InsertaAntes.
Descripción: Inserta un
nodo en la posición previa 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.
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 Cabeza.
Datos de salida: Ninguno.
Precondición: True
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.
Precondición: True
Postcondición:
De encontrarse el nodo con el carácter buscado, Lista poseerá un elemento
menos.
BuscaNodoPrevio.
Descripción: Recorre la
estructura hasta alcanzar el nodo que se encuentra antes de aquel 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.
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 te’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;
public:
~Nodo(){delete sig;}
void setCaracter(char);
char getCaracter();
void setSig(Nodo*);
Nodo* getSig();
Nodo* creaNodo();
};
class Control{
Nodo *cabeza;
Nodo* buscaFinal();
public:
Control(){cabeza=NULL;}
~Control(){delete cabeza;}
void insertaInicio(Nodo *);
void insertaFinal(Nodo *);
void insertaAntes(Nodo *,char);
void insertaDespues(Nodo *,char);
void visualizaLista();
int eliminaNodo(char);
int buscaNodoPrevio(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;
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);
lista.insertaInicio(nuevo);
}
break;
case '5':
lista.visualizaLista();
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 Lineal con doble vinculación.