Asignación dinámica de memoria Malloc. Pilas, colas y listas

Funciones

Como veremos después, la gestión dinámica memoria se realiza mediante estructuras dinámicas de datos. Fíjate que se repite la palabra dinámica. Estas estructuras se diferencian de las estáticas ( arrays y estructuras ), en que no tienen un tamaño fijo, es decir, no tenemos que indicar su tamaño al declararlas, sino que podremos aumentarlo o disminuirlo en tiempo de ejecución, cuando se esté ejecutando la aplicación. Como puedes ver, las estructuras dinámicas son de gran utilidad. A continuación veremos las funciones que se encargan de reservar y liberar memoria durante la ejecución, que se encuentran en la librería alloc.h:

malloc( tamaño );

Esta función reserva en memoria una zona de tamaño bytes, y devuelve un puntero al inicio de esa zona. Si no hubiera suficiente memoria retornaría NULL.

free( puntero );

Esta función libera de la memoria la zona que habíamos reservado anteriormente con la función malloc.

Estructuras dinámicas de datos

En función de la forma en que se relacionan existen varios tipos de estructuras de datos. Este tipo de estructuras son autorreferenciadas, es decir, contienen entre sus campos un puntero de su mismo tipo. Las más utilizadas son:

• Pilas
• Colas
• Listas

Pilas

Este tipo de estructuras se caracteriza porque todas las operaciones se realizan en el mismo lado. Es de tipo LIFO ( Last In First Out ), el último elemento en entrar es el primero en salir.

Ejemplo

	/* Ejemplo de una pila. */

	#include <stdio.h>
	#include <conio.h>
	#include <stdlib.h>
	#include <alloc.h>

	void insertar(void);
	void extraer(void);
	void visualizar(void);

	struct pila
	{
		char nombre[20];
		struct pila *ant;
	}*CAB=NULL,*AUX=NULL;

	main() /* Rellenar, extraer y visualizar */
	{
		char opc;
		do
		{
			clrscr(); /* borramos la pantalla */
			gotoxy(30,8); /* columna 30, fila 8 */
			printf("1.- Insertar");
			gotoxy(30,10);
			printf("2.- Extraer");
			gotoxy(30,12);
			printf("3.- Visualizar la pila");
			gotoxy(30,14);
			printf("4.- Salir");
			opc=getch( );
			switch(opc)
			{
				case '1':
					insertar( );
					break;
				case '2':
					extraer( );
					break;
				case '3':
					visualizar( );
			}
		}while (opc!='4');
	}

	void insertar(void)
	{
		AUX=(struct pila *)malloc(sizeof(struct pila));
		clrscr();
		printf("Nombre: ");
		gets(AUX->nombre);
		if (CAB==NULL)
		{
			CAB=AUX;
			AUX->ant=NULL;
		}
		else
		{
			AUX->ant=CAB;
			CAB=AUX;
		}
	}

	void extraer(void)
	{
		if (CAB==NULL) return;
		AUX=CAB;
		CAB=CAB->ant;
		free(AUX);
	}

	void visualizar(void)
	{
		if (CAB==NULL) return;
		clrscr();
		AUX=CAB;
		while (AUX!=NULL)
		{
			printf("Nombre: %s\n",AUX->nombre);
			AUX=AUX->ant;
		}
		getch( );
	}

La estructura tipo que utilizaremos será ésta:

	struct pila
	{
		tipo variables;
		struct pila *ant;
	} *CAB=NULL,*AUX=NULL;

Donde tipo variables serán las diferentes variables que guardaremos en la estructura, struct pila *ant es un puntero que apunta al elemento de tipo pila introducido anteriormente, *CAB será donde guardaremos el último elemento insertado en la pila y *AUX nos servirá para guardar elementos temporalmente y para recorrer la pila al visualizarla.

Antes de insertar un elemento, deberemos comprobar si la pila está vacía o no. Si lo estuviera deberemos insertar el primer elemento:

CAB=AUX;
CAB->ant=NULL;

Si ya hubiera algún elemento crearemos uno nuevo apuntado por AUX y haremos que AUX->ant apunte a CAB, que en este momento contiene la dirección del elemento insertado anteriormente. Tras esto haremos que CAB apunte al último elemento insertado, que será la nueva cabeza de la pila.

AUX->ant=CAB;
CAB=AUX;

Para extraer un elemento de la pila deberemos hacer que AUX apunte a la misma dirección que CAB, después haremos que CAB apunte a CAB->ant, con lo que el elemento anterior pasará a ser la cabeza de la pila. Tras esto, solo queda liberar la memoria de la zona apuntada por AUX. No olvides controlar si existe algún elemento ( si CAB es igual a NULL la pila está vacía ):

if (CAB==NULL) return;
AUX=CAB;
CAB=CAB->ant;
free(AUX);

Por último, para visualizar los elementos de la pila, haremos que el puntero auxiliar AUX apunte a la cabeza de la pila, o sea, a CAB. Tras esto iremos visualizando el contenido de la pila, haciendo que AUX tome la dirección de AUX->ant, mientras AUX sea distinto de NULL. También es importante controlar que la pila no esté vacía.

if (CAB==NULL) return;
AUX=CAB;
while (AUX!=NULL)
{
printf("%s",AUX->nombre);
AUX=AUX->ant;
};

Estructura gráfica de una pila

Colas

Este tipo de estructuras se caracteriza porque insertamos los elementos por un lado y los extraemos por el otro lado. Es de tipo FIFO ( First In First Out ), el primer elemento en entrar es el primero en salir. Para gestionar la cola utilizaremos 3 punteros ( para la pila solo eran necesarios 2 ).

Ejemplo

	/* Ejemplo de una cola. */

	#include <stdio.h>
	#include <conio.h>
	#include <stdlib.h>
	#include <alloc.h>

	void insertar(void);
	void extraer(void);
	void visualizar(void);

	struct cola
	{
		char nombre[20];
		struct cola *sig;
	}*CAB=NULL,*AUX=NULL,*FIN=NULL;

	main() /* Rellenar, extraer y visualizar */
	{
		char opc;
		do
		{
			clrscr();
			gotoxy(30,8);
			printf("1.- Insertar");
			gotoxy(30,10);
			printf("2.- Extraer");
			gotoxy(30,12);
			printf("3.- Visualizar la cola");
			gotoxy(30,14);
			printf("4.- Salir");
			opc=getch( );
			switch(opc)
			{
				case '1':
					insertar( );
					break;
				case '2':
					extraer( );
					break;
				case '3':
					visualizar( );
			}
		}while (opc!='4');
	}

	void insertar(void)
	{
		AUX=(struct cola *)malloc(sizeof(struct cola));
		clrscr();
		printf("Nombre: ");
		gets(AUX->nombre);
		AUX->sig=NULL;
		if (FIN==NULL)
			FIN=CAB=AUX;
		else
		{
			FIN->sig=AUX;
			FIN=AUX;
		}
	}

	void extraer(void)
	{
		if (CAB==NULL) return;
		AUX=CAB;
		CAB=CAB->sig;
		free(AUX);
	}

	void visualizar(void)
	{
		if (CAB==NULL) return;
		clrscr();
		AUX=CAB;
		while (AUX!=NULL)
		{
			printf("Nombre: %s\n",AUX->nombre);
			AUX=AUX->sig;
		}
		getch();
	}

La estructura que utilizaremos será:

struct cola { tipo variables; struct cola *sig; } *CAB=NULL,*AUX=NULL,*FIN=NULL;

Donde tipo variables serán las diferentes variables que guardaremos en la estructura, struct cola *sig es un puntero que apunta al elemento de tipo cola introducido a continuación, *CAB será donde guardaremos el primer elemento insertado en la cola, *AUX nos servirá para guardar elementos temporalmente y para recorrer la cola al visualizarla y *FIN tomará la dirección del último elemento insertado.

Antes de insertar un elemento, deberemos comprobar si la cola está vacía o no. Si lo está deberemos insertar el primer elemento.

if (FIN==NULL)
CAB=FIN=AUX;

Si ya existiera algún elemento haremos que FIN->sig apunte al elemento de AUX y a continuación haremos que FIN tome la dirección de AUX, con lo que FIN apuntará al último elemento insertado.

FIN->sig=AUX;
FIN=AUX;

Para extraer un elemento de la cola haremos que el puntero auxiliar AUX tome la dirección del primer elemento insertado, que hemos guardado en CAB. Tras esto haremos que CAB apunte a CAB->sig, es decir, que tome la dirección del segundo elemento insertado, que ahora pasará a ser el primero. Luego liberaremos la zona de memoria apuntada por AUX:

AUX=CAB; /* Deberemos controlar que no esté vacía: if (CAB==NULL) return; */
CAB=CAB->sig;
free(AUX);

Para visualizar la cola comprobaremos que existan elementos, esto es, que FIN sea distinto de NULL. Hecho esto asignaremos a AUX la dirección de CAB e iremos recorriendo la cola hasta que AUX sea igual a NULL.

AUX=CAB; /* Deberemos controlar que no esté vacía: if (CAB==NULL) return; */
while(AUX!=NULL)
{
printf("%s",AUX->nombre);
AUX=AUX->sig;
}

Estructura gráfica de una cola:

Listas

Este tipo de estructuras se caracteriza porque los elementos están enlazados entre sí, de manera que además de las acciones habituales de insertar, extraer y visualizar también podremos buscar un elemento. Para gestionar la lista utilizaremos 4 punteros.

Ejemplo

	/* Ejemplo de una lista. */

	#include <stdio.h>
	#include <conio.h>
	#include <stdlib.h>
	#include <alloc.h>

	void insertar(void);
	void extraer(void);
	void visualizar(void);

	struct lista
	{
		int num;
		struct lista *sig;
	}*CAB=NULL,*AUX=NULL,*F=NULL,*P=NULL;

	main() /* Rellenar, extraer y visualizar */
	{
		char opc;
		do
		{
			clrscr( );
			gotoxy(30,8);
			printf("1.- Insertar");
			gotoxy(30,10);
			printf("2.- Extraer");
			gotoxy(30,12);
			printf("3.- Visualizar la lista");
			gotoxy(30,14);
			printf("4.- Salir");
			opc=getch( );
			switch(opc)
			{
				case '1':
					insertar( );
					break;
				case '2':
					extraer( );
					break;
				case '3':
					visualizar( );
			}
		}while (opc!='4');
	}

	/* A continuación insertaremos el elemento que
	vamos a crear en la posición que le corresponda,
	teniendo en cuenta que la lista deberá quedar
	ordenada de menor a mayor. El puntero P comprueba
	si el campo num de un elemento es menor que el
	campo num del elemento introducido. El puntero
	F se quedará apuntando al elemento de la posición
	anterior al elemento que hemos insertado */

	void insertar(void)
	{
		AUX=(struct lista *)malloc(sizeof(struct lista));
		clrscr( );
		printf("Introduce un número: ");
		scanf("%d",&AUX->num);
		AUX->sig=NULL;
		if (CAB==NULL)
			CAB=AUX;
		else if (CAB->num > AUX->num)
		{
			AUX->sig=CAB;
			CAB=AUX;
		}
		else
		{
			P=F=CAB;
			while (P->num < AUX->num && P!=NULL)
			{
				if (P==CAB) P=P->sig;
				else
				{
					P=P->sig;
					F=F->sig;
				}
			}
			AUX->sig=F->sig;
			F->sig=AUX;
		}
	}

	void extraer(void)
	{
		int var;
		if (CAB==NULL) return;
		clrscr( );
		printf("Introduce el número a extraer: ");
		scanf("%d",&var);
		if (CAB->num==var)
		{
			P=CAB;
			CAB=CAB->sig;
			free(P);
		}
		else
		{
			P=F=CAB;
			while (P->num != var && P!=NULL)
			{
				if (P==CAB) P=P->sig;
				else
				{
					P=P->sig;
					F=F->sig;
				}
			}
			if (P==NULL) return;
			F->sig=P->sig;
			free(P);
		}
	}

	void visualizar(void)
	{
		if (CAB==NULL) return;
		clrscr( );
		AUX=CAB;
		while (AUX!=NULL)
		{
			printf("Número: %d\n",AUX->num);
			AUX=AUX->sig;
		}
		getch( );
	}

La estructura que utilizaremos será:

struct lista
{
tipo variables;
struct lista *sig;
}*CAB=NULL,*AUX=NULL,*F=NULL,*P=NULL;

Donde tipo variables serán las variables que guardaremos en la estructura, struct lista *sig es un puntero que apunta al elemento de tipo lista introducido a continuación, *CAB será donde guardaremos el primer elemento de la lista, *AUX nos servirá para guardar elementos temporalmente y para recorrer la lista al visualizarla, *P para comparar los valores introducidos y ordenarlos, y *F, que apuntará al elemento anterior al último introducido.

Antes de insertar un elemento, deberemos comprobar si la lista está vacía o no. Si lo está deberemos insertar el primer elemento.

if (CAB==NULL) CAB=AUX;

Si ya existiera algún elemento haremos que P y F apunten al primero de la lista. Si el elemento introducido fuera menor que el primero de la lista, haríamos que el nuevo elemento pasara a ser el primero, y el que hasta ahora era el primero, pasaría a ser el segundo.

if (AUX->num < CAB->num){
AUX->sig=CAB;
CAB=AUX;
}

Para extraer un elemento de la lista solicitaremos un número, si el número introducido se corresponde con el campo num de uno de los elementos, éste será extraído de la lista. Deberemos controlar que la lista no esté vacía y que el elemento con el número solicitado exista.

Fíjate en el ejemplo, en la función extraer. Si CAB es igual a NULL, será que la lista está vacía, y si P es igual a NULL al salir del while significará que no se ha encontrado ningún elemento que contenga el número introducido.

Para visualizar la lista comprobaremos que existan elementos, es decir, que CAB sea distinto de NULL. Hecho esto asignaremos a AUX la dirección de CAB e iremos recorriendo la lista mientras AUX sea distinto de NULL.

if (CAB==NULL) return; AUX=CAB; while(AUX!=NULL) { printf("%d",AUX->num); AUX=AUX->sig; }

Estructura gráfica de una lista

Aquí finaliza el tema de la gestión dinámica de memoria. Es un tema algo complejo hasta que se asimila el concepto y funcionamiento de las diferentes estructuras, pero tras conseguirlo ya no tiene ningún secreto. Si alguna vez no recuerdas su funcionamiento siempre es una buena solución coger papel y lápiz, dibujar una pila, cola o lista gráficamente y simular la introducción de elementos, escribiendo la situación de los punteros en cada momento.

Existen otras estructuras, como las listas doblemente enlazadas. La única diferencia con la lista que conocemos es que en las primeras cada elemento guarda la dirección del anterior y del posterior. Sería una estructura como esta:

struct lista_doble
{
char nombre[20];
struct lista_doble *ant;
struct lista_doble *sig;
};

Su funcionamiento es muy similar al de una lista normal. Puedes intentar hacerla tu mismo.

Otras estructuras, como los árboles son más complejas y menos utilizadas.