Bienvenidos sean a este post, hoy veremos una estructura de datos dinamica.
La estructura de datos dinamica mas basica es la llamada listas enlazadas (linked list), dado que este tipo es la base para otras estructuras dinamicas, tales como los stacks o los queues.
El stack se maneja mediante una regla donde cada nuevo elemento debe agregarse al principio de la lista y que cada elemento solo puede eliminarse del principio de la lista, en cambio queue posee como regla que todo nuevo elemento debe ser agregado al final de la lista y se removeran los que esten al inicio de la lista.
Vamos a resumirlo de una forma simple, una lista enlazada consiste de una estructura de cabecera (header structure) que contiene informacion sobre la lista, asi como un enlace al primer elemento, o nodo de lista (list node), siendo que cualquier enlace que es NULL implica que es el ultimo nodo de la lista, y si el primer elemento de la lista es un enlace NULL significa que esta vacia, nuestro principal objetivo sera evitar que los nodos tengan un apuntador que no sea NULL porque de lo contrario la lista no sera valida, para evitar esto debemos apuntar desde una simple variable hasta una estructura compleja, pero para entenderlo bien vamos a analizar un ejemplo simple, para ello crearemos un nuevo archivo que llamaremos ejemplo28.c, al cual le agregaremos el siguiente codigo:
ejemplo28.c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int main()
{
return 0;
}Esta sera la estructura basica de nuestro codigo ahora comenzaremos agregando los siguientes enum despues de las librerias y antes del main:
typedef enum
{
eFrente = 0,
eAtras
} eDonde;
typedef enum
{
eLook = 0,
eInsert,
eDelete
} eAccion;Estos enum los usaremos un poco mas adelante para cuando testeamos a nuestra lista, observen que el primero sera para la ubicacion y el segundo para la accion, nuestro siguiente paso sera agregar el siguiente bloque de informacion:
typedef int DatosLista;
typedef struct _Node NodoLista;
typedef struct _Node
{
NodoLista* aProximo;
DatosLista* aDatos;
} NodoLista;
typedef struct
{
NodoLista* aPrimerNodo;
int cuentaNodos;
} ListaEnlazada;Primero declararemos una variable llamada DatosLista que usaremos dentro de uno de nuestros struct, la siguiente linea es una etiqueta arbitraria que usaremos para una estructura NodoLista, este es un mecannismo de nombramiento que nos permite utilizar ese nombre, lo siguiente sera definir la estructura _Node donde tendremos un apuntador al nombre anterior y despues a la variable que definimos al comienzo, los cuales de ahora en mas seran conocidos como tipos simples personalizados de NodoLista, con esto no volveremos a utilizar a struct _Node haciendo que nuestra lista conste de cero o mas NodoLista, la siguiente estructura sera la encargada de definir el encabezado de nuestra lista enlazada, este constara de dos elementos, el primero es un apuntador a la estructura anterior y luego tenemos una variable donde llevaremos un contador de los nodos de la lista, a continuacion procedemos a agregar el siguiente segemento de lineas:
ListaEnlazada* crearListaEnlazada();
bool estaVacio(ListaEnlazada* aLista);
int tamano(ListaEnlazada* aLista);
void insertarNodoAlFrente(ListaEnlazada* aLista, NodoLista* aNodo);
void insertarNodoAtras(ListaEnlazada* aLista, NodoLista* aNodo);
NodoLista* removerNodoFrontal(ListaEnlazada* aLista);
NodoLista* removerNodoTrasero(ListaEnlazada* aLista);
NodoLista* getNodo(ListaEnlazada* aLista, int pos);
NodoLista* crearNodo(DatosLista* aDatos);
void borrarNodo(NodoLista* aNodo);
void mostrarLista(ListaEnlazada* aLista,void(*printData)(DatosLista* aDatos));
void mostrarNodo(NodoLista* aNodo, void(*printData)(DatosLista* aDatos));
void fueraDeAlmac();Estos son los prototipos de las funciones que iremos agregando en nuestro codigo, esto les recomiendo hacerlo despues de las definiciones anteriores pero antes del main, con esto hecho nuestro siguiente paso sera comenzar a definir estas funciones para ello despues del main agregaremos la siguiente definicion de funcion:
ListaEnlazada* crearListaEnlazada()
{
ListaEnlazada* aLE = (ListaEnlazada*) calloc(1, sizeof(ListaEnlazada));
if (aLE == NULL) FueraDeAlmac();
return aLE;
}Esta funcion nos permitira crear las listas enlazadas, sera del tipo ListaEnlazada, observen que generamos un apuntador de este tipo y utilizamos un calloc para generar el espacio dinamico para la lista, luego tenemos un condicional donde verifica si es igual a NULL y en caso de ser verdadero llamaremos a esa funcion pero de ella hablaremos mas adelante, por ultimo devolvemos el apuntador generado, nuestro siguiente paso sera agregar la siguiente funcion:
bool estaVacio(ListaEnlazada* aLista)
{
return (aLista->cuentaNodos==0);
}Esta funcion la usaremos para chequear si nuestra lista vacia, en este caso devolveremos un valor de tipo bool, le pasaremos una lista y a la hora de devolver el dato verificaremos si el valor cuentaNodos es igual a 0, en caso de ser verdadero envia un true y por lo tanto esta vacia si no se cumple devolvera un false indicando que la lista no estara vacia, pasemos a agregar la siguiente funcion:
int tamano(ListaEnlazada* aLista)
{
return aLista->cuentaNodos;
}Esta funcion nos devolvera el «tamaño» de nuestra liista, para ello pasamos una como argumento, lo siguiente sera devolver el valor de cuentaNodos de la lista informada, continuemos agregando la siguiente funcion:
void insertarNodoAlFrente(ListaEnlazada* aLista, NodoLista* aNodo)
{
NodoLista* aProximo = aLista->aPrimerNodo;
aLista->aPrimerNodo = aNodo;
aNodo->aProximo = aProximo;
aLista->cuentaNodos++;
}Este sera el metodo encargado de agregar un nodo al frente de la lista, en este caso recibiremos los elementos a trabajar, la lista y el nodo, despues definiremos un apuntador de NodoLista y en ella almacenaremos la direccion de aPrimerNodo, nuestro siguiente paso sera asignar el valor recibido de nodo en este primer nodo de la lista y luego al proximo nodo de aNodo le almacenaremos el primer valor que definimos, para que quede despues del ingresado y por ultimo incrementamos a cuentaNodos, nuestro siguiente paso sera agregar la siguiente funcion:
void insertarNodoAtras(ListaEnlazada* aLista, NodoLista* aNodo)
{
if(estaVacio(aLista))
{
aLista->aPrimerNodo = aNodo;
} else {
NodoLista* aActual = aLista->aPrimerNodo;
while(aActual->aProximo != NULL)
{
aActual = aActual->aProximo;
}
aActual->aProximo = aNodo;
}
aLista->cuentaNodos++;
}Esta insertara un nodo pero al final de la lista, como la otra funcion recibira dos datos, la lista y el nodo, primero chequearemos por medio de la funcion estaVacio si la lista pasada esta vacia, en caso de ser verdadero agregaremos el nodo pasado como primer nodo, en caso contrario procedemos a crear un apuntador para el primer nodo de la lista pasada, despues por medio de while pasaremos por todos los proximos nodos mientras sean distintos de NULL.a su vez pasaremos la direccion de memoria de este nodo a aActual, una vez finalizado al valor de aProximo de aActual le asignaremos el nodo que pasamos a la funcion, por ultimo incrementaremos a cuentaNodos, a continuacion agregaremos la siguiente funcion:
NodoLista* removerNodoFrontal(ListaEnlazada* aLista)
{
if (estaVacio(aLista)) return NULL;
NodoLista* aActual = aLista->aPrimerNodo;
aLista->aPrimerNodo = aLista->aPrimerNodo->aProximo;
aLista->cuentaNodos--;
return aActual;
}Esta funcion nos removera el nodo que se encuentre en el frente o primer nodo, primero chequearemos si la lista informada esta vacia en caso de ser verdadero devolveremos un NULL, en caso contrario definiremos un apuntador donde almacenaremos el primer nodo de la lista, despues al primer nodo de la lista le asignaremos el proximo, para luego restar cuentaNodos y dejar evidencia que borramos el nodo, por ultimo devolvemos el nodo que almacenamos al comienzo, agreguemos la siguiente funcion:
NodoLista* removerNodoTrasero(ListaEnlazada* aLista)
{
if(estaVacio(aLista))
{
return NULL;
} else {
NodoLista* aActual = aLista->aPrimerNodo;
NodoLista* aPrev = NULL;
while(aActual->aProximo != NULL)
{
aPrev = aActual;
aActual = aActual->aProximo;
}
aPrev->aProximo=NULL;
aLista->cuentaNodos--;
return aActual;
}
}Este remueve el ultimo nodo, es un poco mas complicado pero no tanto, en este caso volvemos a revisar si la lista inforamada esta vacia, en caso de ser verdardero devolvemos NULL, de lo contrario vamos a definir dos apuntadores de tipo NodoLista, el primero sera para almacenar el primer nodo de la lista, el segundo sera para almacenar el anterior, en este caso como es el primero el anterior debe ser nulo, despues tenemos un bucle que trabajara mientras aProximo sea distinto de NULL, en el bloque asignaremos el valor de aActual a aPrev (el apuntaador que almacena el valor previo), y en el otro apuntador almacenaremos el valor proximo, una vez realizado nuestro siguiente paso sera establecer el valor de aProximo como NULL para eliminarlo, restamos cuentaNodos y por ultimo devolvemos el ultimo valor asignado a aActual, con esto comentado pasemos a agregar el siguiente bloque:
NodoLista* getNodo(ListaEnlazada* aLista, int pos)
{
NodoLista* aActual = aLista->aPrimerNodo;
if (aActual == NULL)
{
return aLista->aPrimerNodo;
}
else if(pos == 0)
{
return aLista->aPrimerNodo;
} else {
int i = 0;
while(aActual->aProximo != NULL)
{
if(i == pos) return aActual;
i++;
aActual = aActual->aProximo;
}
return aActual;
}
}Esta sera la funcion que nos permitira obtener un nodo determinado, para ello le pasaremos dos datos, la lista y la posicion del nodo, despues en el bloque definiremos un apuntador y en ella almacenaremos el prmer nodo de la lista informada, lo siguiente seran una serie de condiciones para verificar el estado de la lista, la pimera es si el valor almacenado en la variable anterior es igual a NULL procede a devolver el valor del primer nodo, lo mismo haremos si la posicion informada es la primera, el siguiente condicional, y por ultimo siino se cumplen ninguna de las dos anteriores primero definiremos una variable, luego tenemos un bucle donde lo haremos mientras aProximo sea distinto a NULL, primero tenemos una condicion donde verificamos si el valor de la variable que definimos anteriormente es igual al informado procede a devolver a aActual, sino ocurre incrementa a esta variable y cambia el valor de aActial con el del proximo nodo, en caso de cumplirse el bucle devolvemos el ultimo valor asignado a aActual, esto es asi para que siempre devolvamos un valor, pasemos a agregar la siguiente funcion:
NodoLista* crearNodo(DatosLista* aDatos)
{
NodoLista* aNuevoNodo = (NodoLista*) calloc(1, sizeof(NodoLista));
if(aNuevoNodo == NULL) FueraDeAlmac();
aNuevoNodo->aDatos = aDatos;
return aNuevoNodo;
}Esta sera la funcion encargada de crear el nodo, primero definiremos un apuntador de tipo NodoLissta donde aplicaremos a calloc, despues chequeamos si aNuevoNodo es igual a NULL en caso de ser verdadero llama a esta funcion que definiremos en un momento, en cambio si no se cumple asignaremos los datos que pasamos al apuntador de datos del nuevo nodo y por ultimo lo devolveremos, continuemos agregando esta nueva funcion:
void borrarNodo(NodoLista* aNodo)
{
free(aNodo->aDatos);
free(aNodo);
}Esta funcion nos borrara el nodo que le pasemos, esto lo hara por medio de free y como cuando lo vimos primero elimina los datos almacenados y luego el nodo en si, desde adentro hacia afuera para no dejar nada que pueda ser llamado, a continuacion agregaremos el siguiente bloque:
void mostrarLista(ListaEnlazada* aLista,void(*printData)(DatosLista* aDatos))
{
NodoLista* aActual = aLista->aPrimerNodo;
printf("Lista tiene %2d entradas: [", tamano(aLista));
while(aActual != NULL)
{
MostrarNodo(aActual, printData);
aActual = aActual->aProximo;
}
printf("]\n");
}Este sera la funcion encargada de mostrar el contenido de la lista, primero pasaremos la lista y luego una curiosidad, en este caso es un apuntador a una funcion, esto es asi porque para esta funcion necesitamos mas que el valor de un apuntador, para entenderlo vamos a dividirlo en tres partes:
- La primera parte es el tipo que devolveremos, parar este caso usaremos a void
- El segundo sera el nombre del apuntador de la funcion, el cual nos permite usar este apuntador como una funcion, para este ejemplo printData pasara a ser una funcion
- El tercero sera los parametros para la «funcion», en este caso los datos de la lista
Continuando con la funcion primero definiremos un apuntador de tipo NodoLista al cual le pasaremos el primer nodo, luego mostraremos un mensaje donde indicaremos la cantidad de entrada en esta lista, observen que usamos la funcion tamano para enseñarla, despues por medio de un bucle pasaremos por todos los elementos de la lista mientras aActual sea distinto de NULL, en ella usaremos una funcion que definiremos a continuacion donde mostraremos cada nodo, para ello le pasaremos dos datos, la posicion actual y el apuntador que definimos anteriormente, por ultimo cambiamos el valor de la variable por el proximo nodo y ser enviado en la proxma pasada, por ultimo cerraremos el mensaje que abrimos anteriormente, con esto comentado pasemos a agregar la siguiente funcion:
void mostrarNodo(NodoLista* aNodo, void(*printData)(DatosLista* aDatos))
{
printData(aNodo->aDatos);
}Esta es la funcion encargada de mostrar cada uno de los nodos, aqui pasaremos dos valores, el primero sera uno para el nodo y en el siguiente volvemos a implementar lo explicado anteriormente, recuerden que debemos repetirlo porque lo pasamos como parametro, pero como curiosidad observen que aqui usamos a printData como funcion y le pasaremos los paramentros ccorrectos para devolver la informacion, en realidad esto es un apuntador a una funcion que veremos en breve, por ultimo debemos agregar esta funcion:
void FueraDeAlmac(void)
{
fprintf(stderr, "### ERROR FATAL DE EJECUCION ### sin memoria");
exit( EXIT_FAILURE );
}Si recuerdan en algunas funciones anteriores hemos citado a esta funcion, especialmente cuando el elemento a analizar es de valor NULL, en realidad esta funcion no es necesaria dado que solo la usaremos para cuando no podamos asignar un espacio en memoria, pero es una buena practica hacerlo porque de esta forma no solo notificaremos el error sino que a su vez saldremos con una falla del programa para establecer que no todo funciono correctamente, esto seria la parte del programa para trabajar con las listas enlazadas, solo nos falta dos partes mas, la encargada de simular todo la creacion de la listas y el main, para comenzar debemos definir las funciones que usaremos de prueba, estas deben estar entre los prototipos y el main, con esto explicado comencemos agregando la primera funcion:
void mostrarInt(int* i)
{
printf("%2d ", *i);
}Esta funcion la usaremos para mostrar valores de tipo int con el tipo DatosLista, si necesitaramos de otro tipo deberemos definir otra funcion para hacerlo, en este caso simplemente por medio de printf mostraremos el valor recibido, nuestro siguiente paso sera agregar la siguiente funcion:
DatosLista* crearDatos(DatosLista d)
{
DatosLista* aD = (DatosLista*)calloc(1, sizeof(DatosLista));
if (aD == NULL) fueraDeAlmac();
*aD = d;
return aD;
}Esta funcion sera para crear los datos de nuestra lista, primero definiremos un apuntador por medio de calloc, en caso de fallar procede a llamar a fueraDeAlmac, sino asignara al apuntador que definimos el valor que le enviamos y despues lo devolveremos, con estas dos funciones definidas vamos a continuar con el proyecto y agregaremos la siguiente funcion:
void testCrearEingreso(ListaEnlazada* aLE, DatosLista datos, eDonde donde)
{
DatosLista* aDatos = crearDatos(datos);
NodoLista* aNodo = crearNodo(aDatos);
switch(donde)
{
case eFrente:
insertarNodoAlFrente(aLE, aNodo);
break;
case eAtras:
insertarNodoAtras(aLE, aNodo);
break;
}
}Esta funcion sera la que usaremos para crear datos y nodos, y tambien lo usaremos para ingresar un nodo al frente y otro atras, primero crearemos dos apuntadores para el tipo de datos y de nodo, en ambos casos usamos a crearDatos, para el primer apuntador pasaremos a los datos que recibimos y en el segundo apuntador para los datos pasamos los datos antes definidos, despues en un switch chequearemos al enum donde, para el caso de eFrente insertaremos el nodo al frente y en caso de ser eAtras llama a la funcion para insertar el nodo atras, con esto comentado vamos a agregar la siguiente funcion:
DatosLista testExaminarNodo(ListaEnlazada* aLE, eDonde donde)
{
NodoLista* aNodo;
switch(donde)
{
case eFrente:
aNodo = getNodo(aLE, 0);
break;
case eAtras:
aNoddo = getNodo(aLE, aLE->cuentaNodos);
break;
}
DatosLista datos = *(aNodo->aDatos);
return datos;
}Esta funcion es para examinar los nodos, de nuevo pasaremos dos datos que seran la lista y en donde trabajaremos, nuestro primer paso sera crear un apuntador a un nodo, para despues por medio de un switch chequearemos donde trabajaremos, para el caso del primer nodo o frente, usaremos a getNodo y pasaremos la lista enlazada y la posicion 0, para el caso de atras usaremos nuevametne a getNodo pasaremos la lista pero en la posicion pasaremos el valor de cuentaNodos para que vaya a la ultima posicion, en cualquiera de los dos casos almacenaremos el resultado en el apuntador declarado anteriormente, nuestro siguiente paso sera definir un nuevo apuntador al cual le asignaremos los datos obtenidos anteriormente, por ultimo devolveremos estos datos, nuestro siguiente paso sera agregar la siguiente funcion:
DatosLista testRemoverNodo(ListaEnlazada* aLE, eDonde donde)
{
NodoLista* aNodo;
switch(donde)
{
case eFrente:
aNodo = removerNodoFrontal(aLE);
break;
case eAtras:
aNodo = removerNodoTrasero(aLE);
break;
}
DatosLista datos = *(aNodo->aDatos);
borrarNodo(aNodo);
return datos;
}Esta funcion sera la encargada de remover un nodo y liberarlo, al igual que en casos anteriores pasamos una lista y donde actuaremos, de forma similar al caso anterior declaramos un apuntador para el nodo, por medio de un switch chequeamos si es en el frente o el de atras donde llamaremos a la funcion correspondiente para remover el nodo correspondiente y sera almacenado en el apuntador anterior, despues definiremos otro variable donde almacenaremos los datos del nodo, despues lo liberaremos por medio de borrarNodo y por ultimo devolvemos los datos almacenados, pasemos a agregar la ultima funcion para simular el trabajo sobre una lista:
void testMostrarOperacion(ListaEnlazada* aLE, eAccion accion,
DatosLista datos, eDonde donde)
{
switch(accion)
{
case eLook:
datos = testExaminarNodo(aLE, donde);
printf("Obtuve nodo %s, veo [%2d].\t",
donde == eFrente ? "frontal" : "trasero",
datos);
break;
case eInsert:
printf("Insertar [%2d] en nodo %s.\t", datos,
donde == eFrente ? "frontal" : "trasero");
testCrearEingreso(aLE, datos, donde);
break;
case eDelete:
datos = testRemoverNodo(aLE, donde);
printf("Remueve [%2d] en nodo %s.\t", datos,
donde == eFrente ? "frontal" : "trasero");
break;
default:
printf("::Error:: accion desconocida\n");
break;
}
mostrarLista(aLE, mostrarInt);
}Esta funcion la usaremos para probar algunas de las acciones sobre nuestras listas, para ello le enviaremos cuatro argumentos, que seran la lista, la accion, los datos y la ubicacion respectivamente, por medio de un switch verificaremos la accion, la primera accion que verificamos es eLook, en este caso primero llamaremos a la funcion para testear y examinar el nodo, despues mostraremos cual nodo es y el valor, el siguiente case es para eInsert y en este caso mostraremos el dato a ingresar y en que nodo, y despues por medio de la funcion de test para crearla e ingresarla, el siguiente case sera para eDelete y aqui llamaremos a la funcion de test para remover nodos y lo almacenaremos en datos, despues mostraremos el dato que removimos y de que nodo, por ultimo default lo usaremos por si pasamos una accion no declarada, con esto tenemos todas las funciones para simular un test, y al final llamaremos a mostrarLista para ver como esta la lista despues de las acciones, nuestro siguiente paso sera modificar el main de la siguiente manera:
int main()
{
ListaEnlazada* aLE = crearListaEnlazada();
printf("\nUsando entrada{1 2 3 4}");
int dato1[] = {1, 2, 3, 4};
int dato1tam = 4;
mostrarLista(aLE, mostrarInt);
for(int i=0; i < dato1tam; i++)
testMostrarOperacion(aLE, eInsert, dato1[i], eFrente);
testMostrarOperacion(aLE, eLook, 0, eFrente);
testMostrarOperacion(aLE, eDelete, 0, eAtras);
printf("\nUsando entrada{31 32 33}");
mostrarLista(aLE, mostrarInt);
int dato2[] = {31,32,33};
int dato2tam = 3;
for(int i=0; i < dato2tam; i++)
testMostrarOperacion(aLE, eInsert, dato2[i], eFrente);
testMostrarOperacion(aLE, eLook, 0, eAtras);
int contar=aLE->cuentaNodos;
for(int i=0; i < contar; i++)
testMostrarOperacion(aLE, eDelete, 0, eFrente);
}En este caso vamos a crear un apuntador para una lista y la crearemos por medio de la funcion crearListaEnlazada, despues mostraremos los primeros cuatro valores que le asignaremos, despues definimos un array con estos valores, lo siguiente sera definir una variable que representara la cantidad de elementos del array, despues mostraremos como esta actualmente nuestra lista, despues por medio de un bucle for agregaremos cada uno de los elementos del array en la lista, en este caso usamos a la funcion de mostrar operacion de test y para ello le pasaremos la accion de eInsert y cada una de las posiciones del array, y siempre indicando el nodo frontal, despues llamaremos dos veces a esta misma funcion, en la primera mostraremos el resultado de la accion eLook y luego de la eDelete para eliminar el nodo trasero, nuestro siguiente paso sera mostrar una nueva entrada con nuevos valores, pero repasamos como quedo la lista, lo siguiente es definir un nuevo array con los nuevos valores, volvemos a definir una nueva variable para tener el tamaño del nuevo array, volvemos a hacer el mismo bucle que el anterior para insertar los nuevos valores, luego mostraremos el valor del nodo trasero.
Para ir finalizando en una variable almacenaremos el valor de cuentaNodos para ser utilizado en un bucle donde pasaremos por todos los nodos y los iremos eliminando por medio de la accion eDelete, no es por medio de la posicion sino que repetimos la cantidad de veces q pasaremos por la primera posicion del nodo frontal, con todo esto podemos ver como quedo nuestro codigo final:
ejemplo28.c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef enum
{
eFrente = 0,
eAtras
} eDonde;
typedef enum
{
eLook = 0,
eInsert,
eDelete
} eAccion;
typedef int DatosLista;
typedef struct _Node NodoLista;
typedef struct _Node
{
NodoLista* aProximo;
DatosLista* aDatos;
} NodoLista;
typedef struct
{
NodoLista* aPrimerNodo;
int cuentaNodos;
} ListaEnlazada;
ListaEnlazada* crearListaEnlazada();
bool estaVacio(ListaEnlazada* aLista);
int tamano(ListaEnlazada* aLista);
void insertarNodoAlFrente(ListaEnlazada* aLista, NodoLista* aNodo);
void insertarNodoAtras(ListaEnlazada* aLista, NodoLista* aNodo);
NodoLista* removerNodoFrontal(ListaEnlazada* aLista);
NodoLista* removerNodoTrasero(ListaEnlazada* aLista);
NodoLista* getNodo(ListaEnlazada* aLista, int pos);
NodoLista* crearNodo(DatosLista* aDatos);
void borrarNodo(NodoLista* aNodo);
void mostrarLista(ListaEnlazada* aLista,void(*printData)(DatosLista* aDatos));
void mostrarNodo(NodoLista* aNodo, void(*printData)(DatosLista* aDatos));
void fueraDeAlmac();
// Rutinas de Testeo
void mostrarInt(int* i)
{
printf("%2d ", *i);
}
DatosLista* crearDatos(DatosLista d)
{
DatosLista* aD = (DatosLista*)calloc(1, sizeof(DatosLista));
if (aD == NULL) fueraDeAlmac();
*aD = d;
return aD;
}
void testCrearEingreso(ListaEnlazada* aLE, DatosLista datos, eDonde donde)
{
DatosLista* aDatos = crearDatos(datos);
NodoLista* aNodo = crearNodo(aDatos);
switch(donde)
{
case eFrente:
insertarNodoAlFrente(aLE, aNodo);
break;
case eAtras:
insertarNodoAtras(aLE, aNodo);
break;
}
}
DatosLista testExaminarNodo(ListaEnlazada* aLE, eDonde donde)
{
NodoLista* aNodo;
switch(donde)
{
case eFrente:
aNodo = getNodo(aLE, 0);
break;
case eAtras:
aNodo = getNodo(aLE, aLE->cuentaNodos);
break;
}
DatosLista datos = *(aNodo->aDatos);
return datos;
}
DatosLista testRemoverNodo(ListaEnlazada* aLE, eDonde donde)
{
NodoLista* aNodo;
switch(donde)
{
case eFrente:
aNodo = removerNodoFrontal(aLE);
break;
case eAtras:
aNodo = removerNodoTrasero(aLE);
break;
}
DatosLista datos = *(aNodo->aDatos);
borrarNodo(aNodo);
return datos;
}
void testMostrarOperacion(ListaEnlazada* aLE, eAccion accion,
DatosLista datos, eDonde donde)
{
switch(accion)
{
case eLook:
datos = testExaminarNodo(aLE, donde);
printf("Obtuve nodo %s, veo [%2d].\t",
donde == eFrente ? "frontal" : "trasero",
datos);
break;
case eInsert:
printf("Insertar [%2d] en nodo %s.\t", datos,
donde == eFrente ? "frontal" : "trasero");
testCrearEingreso(aLE, datos, donde);
break;
case eDelete:
datos = testRemoverNodo(aLE, donde);
printf("Remueve [%2d] en nodo %s.\t", datos,
donde == eFrente ? "frontal" : "trasero");
break;
default:
printf("::Error:: accion desconocida\n");
break;
}
mostrarLista(aLE, mostrarInt);
}
// es el main
int main()
{
ListaEnlazada* aLE = crearListaEnlazada();
printf("\nUsando entrada{1 2 3 4}");
int dato1[] = {1, 2, 3, 4};
int dato1tam = 4;
mostrarLista(aLE, mostrarInt);
for(int i=0; i < dato1tam; i++)
testMostrarOperacion(aLE, eInsert, dato1[i], eFrente);
testMostrarOperacion(aLE, eLook, 0, eFrente);
testMostrarOperacion(aLE, eDelete, 0, eAtras);
printf("\nUsando entrada{31 32 33}");
mostrarLista(aLE, mostrarInt);
int dato2[] = {31,32,33};
int dato2tam = 3;
for(int i=0; i < dato2tam; i++)
testMostrarOperacion(aLE, eInsert, dato2[i], eAtras);
testMostrarOperacion(aLE, eLook, 0, eAtras);
int contar=aLE->cuentaNodos;
for(int i=0; i < contar; i++)
testMostrarOperacion(aLE, eDelete, 0, eFrente);
}
// Definiciones de los prototipos
ListaEnlazada* crearListaEnlazada()
{
ListaEnlazada* aLE = (ListaEnlazada*) calloc(1, sizeof(ListaEnlazada));
if (aLE == NULL) fueraDeAlmac();
return aLE;
}
bool estaVacio(ListaEnlazada* aLista)
{
return (aLista->cuentaNodos==0);
}
int tamano(ListaEnlazada* aLista)
{
return aLista->cuentaNodos;
}
void insertarNodoAlFrente(ListaEnlazada* aLista, NodoLista* aNodo)
{
NodoLista* aProximo = aLista->aPrimerNodo;
aLista->aPrimerNodo = aNodo;
aNodo->aProximo = aProximo;
aLista->cuentaNodos++;
}
void insertarNodoAtras(ListaEnlazada* aLista, NodoLista* aNodo)
{
if(estaVacio(aLista))
{
aLista->aPrimerNodo = aNodo;
} else {
NodoLista* aActual = aLista->aPrimerNodo;
while(aActual->aProximo != NULL)
{
aActual = aActual->aProximo;
}
aActual->aProximo = aNodo;
}
aLista->cuentaNodos++;
}
NodoLista* removerNodoFrontal(ListaEnlazada* aLista)
{
if (estaVacio(aLista)) return NULL;
NodoLista* aActual = aLista->aPrimerNodo;
aLista->aPrimerNodo = aLista->aPrimerNodo->aProximo;
aLista->cuentaNodos--;
return aActual;
}
NodoLista* removerNodoTrasero(ListaEnlazada* aLista)
{
if(estaVacio(aLista))
{
return NULL;
} else {
NodoLista* aActual = aLista->aPrimerNodo;
NodoLista* aPrev = NULL;
while(aActual->aProximo != NULL)
{
aPrev = aActual;
aActual = aActual->aProximo;
}
aPrev->aProximo=NULL;
aLista->cuentaNodos--;
return aActual;
}
}
NodoLista* getNodo(ListaEnlazada* aLista, int pos)
{
NodoLista* aActual = aLista->aPrimerNodo;
if (aActual == NULL)
{
return aLista->aPrimerNodo;
}
else if(pos == 0)
{
return aLista->aPrimerNodo;
} else {
int i = 0;
while(aActual->aProximo != NULL)
{
if(i == pos) return aActual;
i++;
aActual = aActual->aProximo;
}
return aActual;
}
}
NodoLista* crearNodo(DatosLista* aDatos)
{
NodoLista* aNuevoNodo = (NodoLista*) calloc(1, sizeof(NodoLista));
if(aNuevoNodo == NULL) fueraDeAlmac();
aNuevoNodo->aDatos = aDatos;
return aNuevoNodo;
}
void borrarNodo(NodoLista* aNodo)
{
free(aNodo->aDatos);
free(aNodo);
}
void mostrarLista(ListaEnlazada* aLista,void(*printData)(DatosLista* aDatos))
{
NodoLista* aActual = aLista->aPrimerNodo;
printf("Lista tiene %2d entradas: [", tamano(aLista));
while(aActual != NULL)
{
mostrarNodo(aActual, printData);
aActual = aActual->aProximo;
}
printf("]\n");
}
void mostrarNodo(NodoLista* aNodo, void(*printData)(DatosLista* aDatos))
{
printData(aNodo->aDatos);
}
void fueraDeAlmac()
{
fprintf(stderr, "### ERROR FATAL DE EJECUCION ### sin memoria");
exit( EXIT_FAILURE );
}Observen que puse unos comentarios para poder indicar cuales son las funciones de «testeo», las definiciones de los prototipos y el main, con todo esto pasemos a compilar y veamos como es su salida:
tinchicus@dbn001vrt:~/lenguajes/C$ ./prog/ejemplo28
Usando entrada{1 2 3 4}Lista tiene 0 entradas: []
Insertar [ 1] en nodo frontal. Lista tiene 1 entradas: [ 1 ]
Insertar [ 2] en nodo frontal. Lista tiene 2 entradas: [ 2 1 ]
Insertar [ 3] en nodo frontal. Lista tiene 3 entradas: [ 3 2 1 ]
Insertar [ 4] en nodo frontal. Lista tiene 4 entradas: [ 4 3 2 1 ]
Obtuve nodo frontal, veo [ 4]. Lista tiene 4 entradas: [ 4 3 2 1 ]
Remueve [ 1] en nodo trasero. Lista tiene 3 entradas: [ 4 3 2 ]
Usando entrada{31 32 33}Lista tiene 3 entradas: [ 4 3 2 ]
Insertar [31] en nodo trasero. Lista tiene 4 entradas: [ 4 3 2 31 ]
Insertar [32] en nodo trasero. Lista tiene 5 entradas: [ 4 3 2 31 32 ]
Insertar [33] en nodo trasero. Lista tiene 6 entradas: [ 4 3 2 31 32 33 ]
Obtuve nodo trasero, veo [33]. Lista tiene 6 entradas: [ 4 3 2 31 32 33 ]
Remueve [ 4] en nodo frontal. Lista tiene 5 entradas: [ 3 2 31 32 33 ]
Remueve [ 3] en nodo frontal. Lista tiene 4 entradas: [ 2 31 32 33 ]
Remueve [ 2] en nodo frontal. Lista tiene 3 entradas: [31 32 33 ]
Remueve [31] en nodo frontal. Lista tiene 2 entradas: [32 33 ]
Remueve [32] en nodo frontal. Lista tiene 1 entradas: [33 ]
Remueve [33] en nodo frontal. Lista tiene 0 entradas: []
tinchicus@dbn001vrt:~/lenguajes/C$Observen como primero completamos la lista con los primeros cuatro valores para luego removerlo, nos quedo una lista de tres y despues la incrementamos a seis conn los nuevos tres valores, estos se acomodan dependiendo donde queremos agregarlo y por ultimo como pudimos eliminar todos y cada uno de ellos, les recomiendo jugar un poco mas variando algunos datos, agregando y eliminando valores.
Obviamente es algo muy similar a un array pero con la capacidad de poder variar su tamaño de manera dinamica permitiendo que se ajuste mejor a nuestras necesidades, dado que los array solo pueden tener un tamaño y siempre nos manejaremos dentro de este, no se preocupen por este tema porque es harto complejo de manejar y podran hacer muchas cosas antes de poder manejar este tema, pero un poco mas adelante lo utilizaremos para nuestro juego de cartas que vimos en posts anteriores pero ese sera un tema para otro post.
En resumen, hoy hemos visto como es una lista enlazada, un tipo de estructura de datos dinamicos, como es, como trabaja, despues desarrollamos un ejemplo para entender mejor el concepto, si bien es muy complejo, les recomiendo hacer algunas sutiles modificaciones en el main para ir viendo las distintas conductas del codigo y las funciones que utilizamos, espero les sea de utilidad sigueme en tumblr, Twitter o Facebook para recibir una notificacion cada vez que subo un nuevo post en este blog, nos vemos en el proximo post.
Donación
Es para mantenimento del sitio, gracias!
$1.50
El blog de Tinchicus 