Estructuras de Datos (1):
LISTAS ENLAZADAS...
Empezaré por dar una breve introducción de lo que son las estructuras de datos, como bien sabemos podemos ordenar, guardar y/o manipular datos (números, caracteres, etc...) en arreglos unidimensionales, bidimensionales, o tantas dimensiones queramos darles, pero en muchas ocasiones la forma en que necesitamos usarlos no es la óptima para algún tipo de problema que se nos presenta.
Para eso existen la Estructuras de Datos, nos dan más formas de poder manipular los datos conforme a lo que necesitemos. Hoy vamos a tocar un poco el tema de las Listas (enlazadas), las cuales tienen la estructura LIFO por sus siglas en inglés "Last In, First Out" que quiere decir que el ÚLTIMO elemento en ENTRAR es el PRIMERO en SALIR. Expliquemos un poco esto con una imagen que me encontré por ahí...
Por defecto una lista que es vacía es también una lista, solo para aclarar.
Bien, expliquemos la imagen. Claramente se ve que tenemos una lista con 4 nodos. ¿Qué es un nodo? En las Listas es aquella parte de la estructura de datos, que se conforma de dos elementos:
1° Aquella que guarda el dato o elemento el cuál estamos manipulando y 2° El direccionador hacia el siguiente nodo en la Lista, también podemos llamarle APUNTADOR pero eso es más en cuestiones de programación y no de el concepto. Ahora metiéndonos más a la cuestión de programación analizaremos y les mostraré como se arma una Lista en C o C++.
typedef char* Elem;
typedef struct Nodo{
Elem dato;
struct Nodo *sig;
}*Lista;
El siguiente código es la construcción de la Lista como tal, me refiero a su forma inicial siendo vacía y un apuntador apuntando a nulo (NULL) válgase la redundancia. Primero vemos nuestro "Elem" previamente yo lo definí como un typedef de tipo caracter que tengo en otra librería, pero aquí solo lo creo como un apuntador a caracter para poder manipularlo en mi Lista. Después creo un tipo de dato Nodo (typedef struct Nodo) que en realidad va a ser un apuntador a Lista (*Lista). Dentro de todo mi tipo de dato Nodo tengo dos elementos:
1° Elem dato: este será un apuntador a caracter, la parte de la Lista donde se almacenará mi DATO.
2° struct Nodo *sig: parecería que es complicado hasta entenderlo, pero es simple , tenemos un apuntador llamado sig (*sig) que de forma recurrente apuntará a mi tipo de dato Nodo (struct Nodo) y así de forma sucesiva en cada nodo que se cree.
O sea que cada nodo tendrá un dato guardado y un apuntador al siguiente nodo como lo vemos aquí:
struct Nodo{
Elem dato;
*sig;----------------------->struct Nodo{
Elem dato;
*sig;------------->struct Nodo{
} Elem dato;
*sig;------>NULL;
}
Apuntará a NULL hasta que dejemos de meterle elementos a nuestra Lista.
Cabe decir que las Listas se crean de forma Dinámica es decir se crean tantos espacios para datos como los necesitemos.
La Estructura de Datos, Lista es desde mi punto de vista la más fácil de implementar, aunque también de las más difíciles en entender pues fue la primera con que me tope yo, pero después en las demás estructura ya tienes mas dominado el concepto.
Ahora, en C++ ya esta definido el tipo de dato Lista para usarlo así como sus funciones, la podemos usar declarando la librería:
#include<list>
y la creamos así...
list<tipo_de_dato> nom_Lista;
Para más información se puede checar el reference en: http://www.cplusplus.com/reference/list/list/
ahí se encuentran todas las funciones, además si tienen dudas de como implementarlas pueden escribirme a mi correo: adrian.ipod25@gmail.com.
Con esto concluimos el tema de Listas Enlazadas y pueden escribirme sus dudas y en cuanto tenga tipo les responderé, el siguiente tema veremos la ED Pila...
Aquí la librería de la Lista con mis funciones:
También incluí las funciones para usarse con archivos :).
