C / Ordenando la lista

Bienvenidos sean a este post, hoy volveremos a aplicar mucho de lo visto anteriormente.

En el post anterior creamos un proyecto simple donde tomamos una lista de nombres y lo almacenabamos en un archivo, esto podia ser desde un archivo o bien desde stdin para ingresarlo mediante el teclado, hoy vamos a tomar lo que vimos en el post anterior y vamos a mejorarlo agregando varias cosas mas, para ello les dejo el codigo que trabajamos hasta ahora con la estructura:

Este simplemente lo extraen y desde ahi podran trabajar normalmente, para nuestro siguiente paso vamos a crear un nuevo archivo en el directorio libs, a este archivo lo llamaremos funciones.h y le agregaremos el siguiente codigo:

funciones.h

#ifndef _ORDENA_NOMBRES_H_
#define _ORDENA_NOMBRES_H_

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>

typedef char ListaDatos;

typedef struct _Nodo ListaNodo;
typedef struct _Nodo
{
	ListaNodo* aProximo;
	ListaDatos* aDatos;
} ListaNodo;

typedef struct
{
	ListaNodo* aPrimerNodo;
	int cuentaNodos;
} ListaNombres;

ListaNombres* CreaListaNombres();
ListaNodo* CrearListaNodo(char* aNombreAgregar);
void AgregarNombre(ListaNombres* aNombres, char* aNombreAgregar);
void BorrarNombre(ListaNombres* aNombres);
bool EstaVacio(ListaNombres* aNombres);
void MostrarNombres(FILE* salidaDesc, ListaNombres* aNombres);
void MasAllaAlmacenamiento();

#endif

Esta va a ser la libreria que nos permitira implementar algunas funciones, observen que esta encerrado en un #ifndef … #endif donde verificamos si no existe la constante _ORDENA_NOMBRES_H_ para en caso de existir proceda a ignorar todo el contenido de instrucciones en el bloque, este nos evitara que se generen multiples declaraciones conflictivas, especialmente cuando tenemos muchos archivos de encabezado, volviendo al codigo nuestro primer paso sera definir dicha constante, luego incluiremos cuatro librerias, primero definiremos un alias para un char llamado ListaNodo, despues tenemos tres alias para dos struct, el primero sera para _Nodo donde primero lo definiremos sin nada y luego le agregaremos dos variables, el siguiente struct sera para el listado de nombres, si les resulta familiar es porque son listas enlazadas de la cual hablamos en este post, las cuales nos permitiran poder ordenar los nombres alfabeticamente en nuestro archivo de salida pero eso lo veremos en un momento, despues tenemos una serie de prototipos para distintas funciones, las primeras dos seran para trabajar con nuestras listas enlazadas, despues tendremos varias funciones para trabajar con los nombres, una que verifica si esta vacia o no y una para cuando nos vayamos por fuera del almacenamiento.

Nuestro siguiente paso sera definir cada una de estas funciones, para ello crearemos en el mismo directorio un nuevo archivo que llamaremos funciones.c, una vez realizado comenzaremos a agregar los siguientes bloques:

#include "funciones.h"

ListaNombres* CrearListaNombres()
{
	ListaNombres* aLN = (ListaNombres*)calloc(1,sizeof(ListaNombres));
	if (aLN == NULL) MasAllaAlmacenamiento();
	return aLN;
}

Nuestra primera linea sera agregar la libreria que definimos anteriormente, nuestro siguiente paso sera definir la funcion para crear el listado de nombres, observen que lo primero sera definir una variable de tipo ListaNombres, en este caso usamos calloc para crear un espacio de memoria para trabajar con la lista, el primer dato sera para definir el tamaño y luego para la cantidad que debe contar, para mas informacion les recomiendo este post, lo siguiente sera chequear si esta variable es igual a NULL y en caso de ser verdadero procede a llamar a la funcion MasAllaAlmacenamiento, de la cual hablaremos luego, en caso de no ocurrir devolvemos la variable generada, con esto comentado pasemos a agregar el siguiente segmento:

ListaNodo* CrearListaNodo(char* aNombreAgregar)
{
	ListaNodo* aNuevoNodo = (ListaNodo*)calloc(1,sizeof(ListaNodo));
	if(aNuevoNodo == NULL) MasAllaAlmacenamiento();
	aNuevoNodo->aDatos = (char*)calloc(1,strlen(aNombreAgregar)+1);
	if(aNuevoNodo->aDatos == NULL) MasAllaAlmacenamiento();
	strcpy(aNuevoNodo->aDatos, aNombreAgregar);
	return aNuevoNodo;
}

Este se encargara de crear la lista de nodos, como argumento recibiremos el nombre a agregar en el nodo de la lista, observen que volvemos a trabajar de forma similar a la funcion anterior, en caso sera una variable de tipo ListaNodo y volveremos a usar a calloc de forma similar, tambien chequeamos si es igual a NULL y en caso de ser verdadero llamamos a la funcion MasAllaAlmacenamiento, nuestro siguiente paso sera almacenar en aDatos el nombre pasado como argumento y para ello volvemos a usar a calloc para reservar el espacio en memoria correctamente, volvemos a chequear si es igual a NULL, esto lo hacemos para salir del programa en caso de error pero ya veremos como, para ir finalizando si esta todo bien por medio de strcpy copiamos el valor en esta variable del struct, por ultimo para devolver todo lo relacionado a este nodo, pasemos a agregar el siguiente segmento de codigo:

void AgregarNombre(ListaNombres* aNombres, char* aNombreAgregar)
{
	ListaNodo* aNuevoNombre = CrearListaNodo(aNombreAgregar);

	if(EstaVacio(aNombres))
	{
		aNombres->aPrimerNodo=aNuevoNombre;
		(aNombres->cuentaNodos)++;
		return;
	}

	(aNombres->cuentaNodos)++;
	ListaNodo* actual;
	ListaNodo* previo;
	actual=previo=aNombres->aPrimerNodo;
	while(actual)
	{
		if(strcmp(aNuevoNombre->aDatos, actual->aDatos) < 0)
		{
			if(actual==aNombres->aPrimerNodo)
			{
				aNombres->aPrimerNodo = aNuevoNombre;
				aNuevoNombre->aProximo = actual;
			} else {
				previo->aProximo = aNuevoNombre;
				aNuevoNombre->aProximo = actual;
			}
			return;
		}
		previo = actual;
		actual = previo->aProximo;
	}
	previo->aProximo = aNuevoNombre;
}

Esta sera la funcion que se encargara de agregar el nombre en la lista de nombres, para ello pasaremos el listado de nombres y el nombre a agregar, nuestro primer paso sera crear una variable de tipo ListaNodo para el nuevo nombre y para ello usaremos la funcion anterior, primero chequearemos si el listado informado esta vacio (por medio de una funcion que explicaremos luego), en caso de ser verdadero procedemos a asignar el nombre en el primer nodo, incrementamos a cuentaNodos y salimos de la funcion, en caso de no ser asi seguiremos con la funcion, lo primero sera incrementar a cuentaNodos, luego declararemos dos variables de tipo ListaNodo, uno para el nodo actual y otro para el previo, lo siguiente sera asignar el valor del primer nodo a las dos variables anteriores, el while se encargara de chequear en las tres secciones de la memoria (inicio, medio y final) donde una vez que llegue al final de la lista saldra del bucle, pero en el bloque chequearemos por medio de strcmp si los datos del nuevo nombre y los datos de actual es menor a cero, en caso de cumplirse procede a chequear si actual es igual al valor del primer nodo y en caso de ser afirmativo procede a asignarle el nuevo nombre y el del proximo sera el de actual de lo contrario en el nodo proximo de previo le asignaremos el nuevo nombre y al proximo de nuevo nombre le asignamos el actual, y salimos de la funcion.

Si la comparacion no se cumple al valor previo le asigna el actual y en actual asigna el valor del proximo de previo, volviendo a repetir el ciclo, por ultimo en el proximo de previo asignaremos el nuevo nombre, este sera el encargado de hacer la magia de ordenar los nombres, pasemos a agregar el siguiente bloque de codigo:

void MostrarNombres(FILE* salidaDesc, ListaNombres* aNombres)
{
	ListaNodo* actual=aNombres->aPrimerNodo;
	while(actual)
	{
		fputs(actual->aDatos, salidaDesc);
		fputc('\n', salidaDesc);
		actual=actual->aProximo;
	}
}

Con esta mostraremos los nombres almacenados, para ello pasaremos la salida y el listado donde estan los nombres, como argumentos pasarmos la salida y el listado, luego definiremos una variable de tipo ListaNodo y en ello almacenaremos el primer nodo de la lista pasada como argumento, por medio de un bucle while pasaremos por todos los nodos de la lista, en ella imprimiremos el valor del nombre actual en lo que pasemos como salida, ya sea un archivo o el stdout, usaremos el fputc para dar el enter o newline y luego pasaremos al proximo nodo, todo esto lo haremos mientras haya datos cuando no haya mas saldremos de ahi y terminaremos con la funcion, con todo comentado pasemos a agregar el siguiente bloque de codigo:

void BorrarNombre(ListaNombres* aNombres)
{
	while(aNombres->aPrimerNodo)
	{
		ListaNodo* temp=aNombres->aPrimerNodo;
		aNombres->aPrimerNodo=aNombres->aPrimerNodo->aProximo;
		free(temp->aDatos);
		free(temp);
	}
}

Esta la que usaremos para borrar los nombres del listado que pasemos, el bucle lo haremos mientras exista un valor en el primer nodo de la lista informada, en el bloque definiremos una variable con el primer nodo el cual sera de manera temporal, despues en el primer nodo asignaremos el valor del proximo, para despues liberar el valor de datos de la variable temporal y luego a la variable temporal, ya tenemos la funcion encargada de borrar los nombres de nuestra lista en memoria, pasemos a definir la siguiente funcion:

bool EstaVacio(ListaNombres* aNombres)
{
	return aNombres->cuentaNodos==0;
}

Este sera la encaegada de devolver si una lista esta vacia o no mediante un valor booleano, para ello devolvera el valor booleano true si el valor de cuentaNodos es igual a cero, indicando que esta vacia, en caso contrario devolvera un false para indicar que no esta vacia, pasemos a ver la ultima funcion:

void MasAllaAlmacenamiento()
{
	fprintf(stderr, "### FATAL RUNTIME ERROR ### Sin memoria");
	exit(EXIT_FAILURE);
}

Esta sera la encargada de cerrar el programa ante algun error, por esta razon la usamos en algunas funciones si el valor de ellas es igual a NULL, observen que devolvera un mensaje y saldra por medio de exit con el valor de FALLA GENERAL, con todo esto comentado veamos como quedo nuestro codigo final:

funciones.c

#include "funciones.h"

ListaNombres* CrearListaNombres()
{
	ListaNombres* aLN = (ListaNombres*)calloc(1,sizeof(ListaNombres));
	if (aLN == NULL) MasAllaAlmacenamiento();
	return aLN;
}

ListaNodo* CrearListaNodo(char* aNombreAgregar)
{
	ListaNodo* aNuevoNodo = (ListaNodo*)calloc(1,sizeof(ListaNodo));
	if(aNuevoNodo == NULL) MasAllaAlmacenamiento();
	aNuevoNodo->aDatos = (char*)calloc(1,strlen(aNombreAgregar)+1);
	if(aNuevoNodo->aDatos == NULL) MasAllaAlmacenamiento();
	strcpy(aNuevoNodo->aDatos, aNombreAgregar);
	return aNuevoNodo;
}

void AgregarNombre(ListaNombres* aNombres, char* aNombreAgregar)
{
	ListaNodo* aNuevoNombre = CrearListaNodo(aNombreAgregar);

	if(EstaVacio(aNombres))
	{
		aNombres->aPrimerNodo=aNuevoNombre;
		(aNombres->cuentaNodos)++;
		return;
	}

	(aNombres->cuentaNodos)++;
	ListaNodo* actual;
	ListaNodo* previo;
	actual=previo=aNombres->aPrimerNodo;
	while(actual)
	{
		if(strcmp(aNuevoNombre->aDatos, actual->aDatos) < 0)
		{
			if(actual==aNombres->aPrimerNodo)
			{
				aNombres->aPrimerNodo = aNuevoNombre;
				aNuevoNombre->aProximo = actual;
			} else {
				previo->aProximo = aNuevoNombre;
				aNuevoNombre->aProximo = actual;
			}
			return;
		}
		previo = actual;
		actual = previo->aProximo;
	}
	previo->aProximo = aNuevoNombre;
}

void MostrarNombres(FILE* salidaDesc, ListaNombres* aNombres)
{
	ListaNodo* actual=aNombres->aPrimerNodo;
	while(actual)
	{
		fputs(actual->aDatos, salidaDesc);
		fputc('\n', salidaDesc);
		actual=actual->aProximo;
	}
}

void BorrarNombre(ListaNombres* aNombres)
{
	while(aNombres->aPrimerNodo)
	{
		ListaNodo* temp=aNombres->aPrimerNodo;
		aNombres->aPrimerNodo=aNombres->aPrimerNodo->aProximo;
		free(temp->aDatos);
		free(temp);
	}
}

bool EstaVacio(ListaNombres* aNombres)
{
	return aNombres->cuentaNodos==0;
}

void MasAllaAlmacenamiento()
{
	fprintf(stderr, "### FATAL RUNTIME ERROR ### Sin memoria");
	exit(EXIT_FAILURE);
}

Ahora solo nos falta hacer algunas modificaciones en program.c, para ello primero agregaremos estas dos lineas al comienzo junto con las librerias que usaremos en el codigo:

#include <ctype.h>
#include "libs/funciones.h"

Primero agregaremos una libreria para manejar un nuevo tipo de dato y la libreria que completamos anteriormente, nuestro siguiente paso sera agregar el siguiente prototipo:

int trimCdn(char* aCdn);

Esta la usaremos para lo mismo que se usa el trim en otros lenguajes, es decir eliminar los espacios en blanco antes y despues del texto, ya la definiremos mas adelante, lo siguiente sera cambiar esta linea:

if (NULL==(salida=fopen(optarg,"a")))

Por la siguiente:

if (NULL==(salida=fopen(optarg,"w")))

Ahora en lugar de agregar nuevas lineas vaciara el archivo y escribira la nueva lista, nuestro siguiente paso sera cambiar el bloque de la siguiente funcion:

while(getNombre(entrada, buffer_nombres)>1)
{
	putNombre(buffer_nombres, salida);
}

Por el siguiente:

ListaNombres lista_nombres = {0};

while(getNombre(entrada, buffer_nombres) > 1)
{
	AgregarNombre(&lista_nombres, buffer_nombres);
}

MostrarNombres(salida, &lista_nombres);
BorrarNombre(&lista_nombres);

En este caso primero definiremos una nueva lista de nombres vacia, despues tenemos el mismo while que antes pero ahora en lugar de usar a putNombre usamos a AgregarNombre para realizar lo explicado anteriormente, para despues llamar a MostrarNombres, ya sea para escribir en el archivo o mostrarlo en stdout, y por ultimo eliminar todos los nombres de la lista de nombres, nuestro siguiente paso sera en getNombre donde debemos cambiar la siguiente linea:

len = strlen(aCdn);

Con la siguiente:

len = trimCdn(aCdn);

En este caso aplicaremos la funcion nueva para que simplemente tengamos el texto sin espacios en blanco, nuestro ultimo paso sera definir la funcion del nuevo prototipo:

int trimCdn(char* aCadena)
{
	size_t primero, ultimo, ancho_ent, ancho_sal;
	primero = ultimo = ancho_ent = ancho_sal = 0;

	ancho_ent=strlen(aCadena);
	char tmp_cadena[ancho_ent+1];
	strcpy(tmp_cadena, aCadena);
	char* aTmp=tmp_cadena;

	while(isspace(aTmp[primero]))
		primero++;

	aTmp+=primero;

	ancho_sal = strlen(aTmp);

	if (ancho_sal)
	{
		ultimo = ancho_sal-1;
		while(isspace(aTmp[ultimo]))
			ultimo--;

		aTmp[ultimo+1] = '\0';
	}

	ancho_sal=strlen(aTmp);

	if(ancho_ent != ancho_sal)
		strcpy(aCadena, aTmp);

	return ancho_sal;
}

Como dijimos esta funcion se encargara de eliminar los espacios en blanco antes y despues del texto, tal como hace el trim en el resto de los lenguajes, para ello primero definiremos unas variables y luego le asignaremos el valor de cero, nuestro primero paso sera asignar el total de caracteres a ancho_ent que sera el ancho inicial, despues declaramos una variable temporal de tipo char con el ancho anterior pero sumandole uno, despues por medio de strcpy le copiaremos el valor pasado como argumento, y lo siguiente sera definir una nueva variable temporal con la variable temporal anterior, nuestro siguiente paso sera pasar por todas las posiciones mientras sean un espacio en blanco, a este segundo temporal le sumaremos el valor final de primero, despues tomaremos otra de las variables definidas al comienzo y le asignaremos el ancho de la segunda variable temporal, el siguiente condicional se ejecuta si ancho_sal tiene un valor, en caso de ser verdadero le asignaremos a ultimo el valor de este menos uno, volveremos a usar un while donde por medio de un isspace nuevamente verificaremos si la posicion es un espacio en blanco, para ello iremos decrementando el valor de ultimo una vez que salimos del bucle tomaremos la variable aTmp y al valor de ultimo le sumaremos uno y le asignaremos el caracter de final de texto, a ancho_sal le asignamos el nuevo valor de cantidad de caracteres de aTmp, el condicional siguiente verifica si ancho_ent y ancho_sal son distintos, en caso de ser asi copiaremos el valor de aTmp en aCadena y por ultimo devolveremos el valor de ancho_sal, con esto ya tenemos nuestro codigo final, veamos como quedo el codigo final:

program.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/errno.h>
#include <ctype.h>

#include "libs/funciones.h"

const int max_cadena=80;

void usar(char* cmd);
int getNombre(FILE* entradaDesc, char* aCdn);
void putNombre(char* aCdn, FILE* salidaDesc);
int trimCdn(char* aCdn);

int main(int argc, char* argv[])
{
	int c;
	FILE* entrada = NULL;
	FILE* salida = NULL;

	while((c = getopt(argc, argv, "i:o:h")) != -1)
	{
		switch(c)
		{
			case 'i':
				if (NULL==(entrada=fopen(optarg,"r")))
				{
					fprintf(stderr,
						"archivo entrada \"%s\": %s\n",
						optarg, strerror(errno));
					exit(EXIT_FAILURE);
				}
				fprintf(stderr,"usando \"%s\" para entrada\n",
					optarg);
				break;
			case 'o':
				if (NULL==(salida=fopen(optarg,"w")))
				{
					fprintf(stderr,
						"archivo salida \"%s\": %s\n",
						optarg, strerror(errno));
					exit(EXIT_FAILURE);
				}
				fprintf(stderr, "usando \"%s\" para salida\n",
					optarg);
				break;
			case '?':
			case 'h':
			default:
				usar(argv[0]);
				break;
		}
	}

	if (!entrada)
	{
		entrada = stdin;
		fprintf(stderr, "usando stdin para entrada\n");
	}

	if (!salida)
	{
		salida =stdout;
		fprintf(stderr, "usando stdout para salida\n");
	}

	char buffer_nombres[max_cadena];

	ListaNombres lista_nombres = {0};

	while(getNombre(entrada, buffer_nombres) > 1)
	{
		AgregarNombre(&lista_nombres, buffer_nombres);
	}

	MostrarNombres(salida, &lista_nombres);
	BorrarNombre(&lista_nombres);

	fprintf(stderr,"Cerrando archivos\n");
	fclose(entrada);
	fflush(salida);
	fclose(salida);

	return 0;
}

void usar(char* cmd)
{
	fprintf(stderr, "uso: %s [-i entrada] [-o salida]\n", cmd);
	fprintf(stderr, "si no se informa -i, se usa stdin\n");
	fprintf(stderr, "si no se informa -o, se usa stdout\n");
	exit(EXIT_FAILURE);
}

int getNombre(FILE* entradaDesc, char* aCdn)
{
	static int numNombres = 0;
	int len;

	memset(aCdn, 0, max_cadena);

	if(stdin == entradaDesc)
		fprintf(stdout, "Nombre %d: ", numNombres+1);

	fgets(aCdn, max_cadena, entradaDesc);

	len = trimCdn(aCdn);

	if (len) numNombres++;

	return len;
}

void putNombre(char* aCdn, FILE* salidaDesc)
{
	fputs(aCdn, salidaDesc);
	fputc('\n', salidaDesc);
}

int trimCdn(char* aCadena)
{
	size_t primero, ultimo, ancho_ent, ancho_sal;
	primero = ultimo = ancho_ent = ancho_sal = 0;

	ancho_ent=strlen(aCadena);
	char tmp_cadena[ancho_ent+1];
	strcpy(tmp_cadena, aCadena);
	char* aTmp=tmp_cadena;

	while(isspace(aTmp[primero]))
		primero++;

	aTmp+=primero;

	ancho_sal = strlen(aTmp);

	if (ancho_sal)
	{
		ultimo = ancho_sal-1;
		while(isspace(aTmp[ultimo]))
			ultimo--;

		aTmp[ultimo+1] = '\0';
	}

	ancho_sal=strlen(aTmp);

	if(ancho_ent != ancho_sal)
		strcpy(aCadena, aTmp);

	return ancho_sal;
}

Vamos a ver como trabaja ahora mediante el siguiente video

En el video primero vemos como compilar para utilizar nuestra «libreria», despues vemos las distintas formas que podemos trabajar con el programa, asi como en la pantalla asi como vuelve a reescribir el archivo de salida.

En resumen, hoy hemos integrado varias cosas nuevas al procesamiento de archivos, en este caso vmos como a traves de listas enlazadas podemos obtener una salida ordenada con respecto a lo visto en el post anterior, repasamos como trabajar con una libreria externa para poder trabajar con nuestro codigo y como compilarlo, espero les hays gustado 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.