9

Asignación dinámica

de memoria

Almacenamiento estático y dinámico

La forma convencional de almacenar las variables en memoria se denomina almacenamiento estático: al principio del programa se declaran las variables y se reserva la cantidad de memoria necesaria. Este es el sistema que hemos utilizado hasta el momento en todos los ejercicios y ejemplos. Con este método cuando un programa utiliza una matriz, previamente decidimos el tamaño máximo que necesita y declaramos la matriz de acuerdo a ese tamaño máximo. Por ejemplo, si el programa usa una matriz bidimensional de enteros y suponemos que el máximo de filas y de columnas que precisará es de 100x100, haremos una declaración como

int matriz[100][100];

con lo que estaremos reservando 100 x 100 x 2 = 20000 bytes de memoria al inicio del programa (en el supuesto de que estén disponibles) y permanecerán reservados durante todo el programa, independientemente de que se usen o no para almacenar valores.

Este tipo de almacenamiento presenta algún inconveniente. Fijémonos en el Ejercicio 3 del Capítulo 7 (página 118) en el que se construye un cuadrado mágico. En ese programa se trabaja con una matriz cuya dimensión puede ir desde 3x3 hasta 19x19. Para el cuadrado de dimensión mínima se necesitan 18 bytes de memoria; cuando se usa la máxima dimensión son necesarios 722 bytes. Pero, independientemente del cuadrado mágico que se desee construir, hemos de declarar la matriz del tamaño máximo, y cuando se construya el cuadrado de ordenes inferiores a 19 estaremos malgastando cierta cantidad de memoria. En este programa esto no es demasiado importante, pero sí lo es para otros que usen matrices mayores. Si el ejercicio referido tratase con cuadrados de órdenes muy grandes, la cantidad de memoria malgastada podría ser muy importante. Basta fijarse en que una matriz de enteros de orden 500x500 necesita, aproximadamente, 0.5 Mb de almacenamiento estático.

La alternativa ideal sería que el programa pudiese solicitar al sistema la cantidad de memoria precisa en cada caso. Para el cuadrado mágico se trataría de pedir al sistema 18 bytes para el orden 3x3 y 722 bytes cuando se construya el cuadrado de orden 19x19. Esto se consigue con la asignación dinámica de memoria, mediante la cual el programa va requiriendo al sistema la memoria que necesita y devolviendo la que ya no es necesaria. Para ello se utilizan las funciones malloc() y free(), que estudiaremos en el próximo apartado.

La memoria asignada dinámicamente se toma de una zona denominada montón (heap) y su tamaño es variable, dependiendo del modelo de memoria usado para compilar el programa.

Básicamente, la forma de situar en la memoria datos y código de un programa atiende al siguiente esquema:

El tamaño para las zonas de código y de datos de vida global permanece constante durante todo el programa. La pila crece hacia abajo y en ella se almacenan las variables de ámbito local utilizadas por las funciones. El montón, también denominado zona de almacenamiento libre, crece hacia arriba, a medida que se asigna memoria dinámicamente a petición del programa. En algunos casos la pila puede solapar parte del montón. También puede ocurrir que el montón no pueda satisfacer todas las demandas de memoria del programa. Estos problemas pueden controlarse con las funciones de asignación dinámica de C.

Las funciones malloc() y free()

Son las dos funciones básicas para la asignación dinámica de memoria. Con la función malloc() se solicita memoria del montón. Con la función free() se devuelve memoria al montón.

El prototipo para la función malloc() es

void *malloc (size_t tama);

y está definido en stdlib.h y alloc.h. Esta función asigna un bloque de tama bytes del montón. Si la cantidad de memoria solicitada está disponible, malloc() devuelve un puntero a la zona de memoria asignada. En caso contrario, devuelve un puntero nulo. El tipo void * indicado en el prototipo quiere decir que el puntero devuelto por malloc() puede (y debe) transformarse a cualquier tipo. El siguiente ejemplo solicita memoria para 100 datos enteros:

int *bloque;

...

...

bloque = malloc (200);

if (!bloque) {

puts ("Memoria insuficiente");

Funcion_error ();

}

Si la función malloc() tiene éxito, el puntero bloque tendrá la dirección de una zona de 200 bytes del montón. En caso contrario debemos finalizar el programa o ejecutar una rutina de error. Hay que poner especial cuidado en no trabajar con punteros nulos, puesto que ello provoca, generalmente, la caida del sistema.

Aunque el ejemplo anterior es correcto, se recomienda hacer la llamada a malloc() de la forma siguiente:

int *bloque;

...

...

bloque = (int *) malloc (100 * sizeof (int));

if (!bloque) {

puts ("Memoria insuficiente");

Funcion_error ();

}

pues asegura la transportabilidad del código.

La función free() tiene como prototipo

void free (void *bloque);

y precisa la inclusión del archivo de cabecera alloc.h. Esta función devuelve al montón el bloque de memoria apuntado por bloque, siendo bloque un puntero proporcionado por una llamada previa a malloc(). La memoria devuelta por free() puede volver a ser asignada por otra llamada a malloc().

El programa de la página siguiente ilustra el uso de ambas funciones. En él se solicita memoria para almacenar una cadena de caracteres de longitud variable. Sólo se usará la memoria necesaria dada por la longitud de la cadena.

#include <stdio.h>

#include <conio.h>

#include <alloc.h>

#include <stdlib.h>

#include <process.h>

void main (void)

{

char *cadena;

int N;

clrscr ();

puts ("EJEMPLO DE ASIGNACIÓN DINÁMICA DE MEMORIA");

printf ("Longitud de la cadena: ");

scanf ("%d", &N);

getchar (); //Elimina el Intro de la entrada

cadena = (char *) malloc (N + 1); //N + 1 para incluir el nulo final

if (!cadena) {

puts ("\nMEMORIA INSUFICIENTE");

exit (1); }

else printf ("\nDirección asignada: %p", cadena);

printf ("\nTeclea %d caracteres: ", N);

gets (cadena);

printf ("\nHas tecleado: %s", cadena);

free (cadena);

}

Otras funciones de asignación dinámica de Turbo C son: allocmem(), calloc(), coreleft(), farcalloc(), farmalloc() y realloc().

Matrices asignadas dinámicamente

El programa mencionado anteriormente del cuadrado mágico ilustra bastante bien una de las situaciones en que es conveniente usar programación dinámica: el programa maneja una matriz cuyo tamaño no puede determinarse a priori.

El siguiente programa resuelve el ejercicio del cuadrado mágico utilizando asignación dinámica de memoria. Aunque en este caso no es necesario, se mantiene la limitación del orden máximo a 19x19, por razones de presentación en pantalla. Además se supone que las funciones Intro() y Strdigit() se encuentran en módulos objeto separados que se enlazarán posteriormente.

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include <string.h>

#include <ctype.h>

#include <alloc.h>

#include <process.h>

void main (void)

{

int *magico, *p;

int i, j, ant_i, ant_j, orden, tope;

register int valor;

char N[3];

clrscr ();

puts ("CUADRADO MÁGICO DE ORDEN N IMPAR (3 a 19)");

do {

do {

printf ("\nValor de N: ");

Intro (wherey (), wherex (), 2, N);

} while (!Strdigit (N));

orden = atoi (N);

} while (orden < 3 || orden > 19 || !(orden % 2));

tope = orden * orden;

magico = (int *) malloc (tope * sizeof (int));

if (!magico) {

puts ("\nMemoria insuficiente");

exit (1);

}

for (i = 0; i < orden; i++) {

for (j = 0; j < orden; j++) {

p = magico + i * orden + j; //Dirección de magico[i][j]

*p = 0;

}

}

i = 0;

j = orden / 2;

for (valor = 1; valor <= tope; valor++) {

p = magico + i * orden + j; //Dirección de magico[i][j]

if (*p) {

i = ant_i + 1;

j = ant_j;

if (i > orden - 1) i = 0;

}

p = magico + i * orden + j; //Dirección de magico[i][j]

*p = valor;

ant_i = i--;

ant_j = j++;

if (i < 0) i = orden - 1;

if (j > orden - 1) j = 0;

}

clrscr ();

for (i = 0; i < orden; i++) {

for (j = 0; j < orden; j++) {

p = magico + i * orden + j; //Dirección de magico[i][j]

printf ("%3d ", *p);

}

printf ("\n");

}

free (magico);

}

Colas dinámicas

Una cola es una estructura FIFO (First In, First Out), es decir, el primer elemento que entra en la estructura es el primero en salir. Las colas se ajustan muy bien al tipo de estructuras susceptibles de programarse dinámicamente, pues son estructuras que crecen y se contraen a medida que la información entra y sale de ellas.

Para programar dinámicamente este tipo de estructuras (como las pilas, los árboles binarios, etc.) es necesario recurrir a las estructuras autoreferenciadas. Una estructura autoreferenciada se define, básicamente, de la siguiente forma:

struct nombre_estructura {

campo_de_nformación1;

campo_de_información2;

...

...

campo_de_informaciónN;

struct nombre_estructura enlace1;

struct nombre_estructura enlace2;

...

...

struct nombre_estructura enlaceN;

};

es decir, hay uno o varios campos en los que se almacena la información que se desee, y uno o varios campos de enlace con otros elementos. Para el caso de una cola dinámica de números enteros cada elemento debe enlazar con el siguiente mediante una estructura autoreferenciada como la siguiente:

struct COLA {

int dato;

struct COLA *enlace;

};

siendo dato el número entero que se almacena en la cola, y enlace un puntero a la estructura del siguiente elemento de la cola.

El siguiente programa gestiona una cola dinámica de números enteros positivos. El funcionamiento del programa se basa en un menú de opciones y en dos funciones, Introducir() y Sacar(), que controlan la entrada/salida de los datos en la cola.

La función Introducir()realiza las siguientes operaciones:

• Llama a malloc() para solicitar memoria para el nuevo elemento. En caso de que no haya memoria disponible, la función devuelve un valor 0.

• Almacena el dato en la dirección asignada mediante malloc().

• Recorre toda la cola desde el principio para localizar el último elemento, a partir del cual debe incluirse el nuevo.

• Enlaza el elemento que antes era el último con el nuevo elemento introducido en la cola.

• Devuelve un valor 1.

• La función Sacar() efectúa las siguientes operaciones:

• Comprueba si la cola está vacía, en cuyo caso devuelve un valor -1.

• Obtiene la información del primer elemento de la cola.

• Hace que el segundo elemento de la cola sea el primero, apuntándolo con el puntero del elemento que se saca.

• Devuelve al montón mediante free() la memoria ocupada por el elemento que se saca.

• Devuelve el valor extraído.

El programa completo se muestra a continuación:

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include <alloc.h>

struct COLA {

int dato;

struct COLA *enlace;

};

int Menu (void);

int Introducir (int n);

int Sacar (void);

struct COLA *primero;

void main (void)

{

int valor, opcion, st;

primero = 0;

while ((opcion = Menu ()) != 3) {

switch (opcion) {

case 1: printf ("\nValor a introducir en la cola: ");

scanf ("%d", &valor);

if (!Introducir (valor)) {

puts ("\nMemoria agotada. Pulse una tecla ...");

while (!getch ());

}

break;

case 2: valor = Sacar ();

if (valor < 0) puts ("\nCola vacía");

else printf ("\nValor obtenido: %d", valor);

printf ("\nPulse una tecla ...");

while (!getch ());

}

}

}

int Menu (void)

{

int n;

clrscr ();

puts ("COLA DINÁMICA\n");

puts ("1. Introducir");

puts ("2. Sacar");

puts ("3. Salir\n");

do {

n = getch ();

} while (n < '1' || n > '3');

return n - 48;

}

int Introducir (int n)

{

struct COLA *nuevo, *actual, *anterior;

nuevo = (struct COLA *) malloc (sizeof (struct COLA));

if (!nuevo) return 0;

nuevo -> dato = n;

nuevo -> enlace = 0;

if (!primero) primero = nuevo;

else {

actual = primero;

while (actual) {

anterior = actual;

actual = anterior -> enlace;

}

anterior -> enlace = nuevo;

}

return 1;

}

int Sacar (void)

{

struct COLA *antprimero;

int n;

if (!primero) return -1;

else {

antprimero = primero;

n = primero -> dato;

primero = primero -> enlace;

free (antprimero);

return n;

}

}

Ejercicios

1. Construye un programa que gestione una pila de enteros con asignación dinámica de memoria. El programa presentará un menú con las opciones

Introducir

Sacar

Salir

El programa dispondrá de funciones Introducir() y Sacar() similares a las utilizadas en el apartado "Colas dinámicas" del capítulo.