La asignación dinámica de memoria es una característica de C. Le permite al usuario crear tipos de datos y estructuras de cualquier tamaño de acuerdo a las necesidades que se tengan en el programa.
Se revisarán dos de las aplicaciones más comunes:
La función malloc es empleada comúnmente para intentar ``tomar'' una porción contigua de memoria. Esta definida como:
void *malloc(size_t size);
Lo anterior indica que regresará un apuntador del tipo void *, el cual es el inicio en memoria de la porción reservada de tamaño size. Si no puede reservar esa cantidad de memoria la función regresa un apuntador nulo o NULL
Dado que void * es regresado, C asume que el apuntador puede ser convertido a cualquier tipo. El tipo de argumento size_t esta definido en la cabecera stddef.h y es un tipo entero sin signo.
Por lo tanto:
char *cp; cp = (char *) malloc(100);
intenta obtener 100 bytes y asignarlos a la dirección de inicio a cp.
Es usual usar la función sizeof() para indicar el número de bytes, por ejemplo:
int *ip; ip = (int *) malloc(100 * sizeof(int) );
El compilador de C requiere hacer una conversión del tipo. La forma de lograr la coerción (cast) es usando (char *) y (int *), que permite convertir un apuntador void
a un apuntador tipo char e int respectivamente. Hacer la conversión al
tipo de apuntador correcto asegura que la aritmética con el apuntador
funcionará de forma correcta.
Es una buena práctica usar sizeof() aún si se
conoce el tamaño actual del dato que se requiere, -- ya que de esta
forma el código se hace independiente del dispositivo (portabilidad).
La función sizeof() puede ser usada para
encontrar el tamaño de cualquier tipo de dato, variable o estructura.
Simplemente se debe proporcionar uno de los anteriores como argumento a
la función.
Por lo tanto:
int i;
struct COORD {float x,y,z};
struct COORD *pt;
sizeof(int), sizeof(i), sizeof(struct COORD) y
sizeof(PT) son tambien sentencias correctas.
En el siguiente ejemplo se reserva memoria para la variable ip,
en donde se emplea la relación que existe entre apuntadores y arreglos,
para manejar la memoria reservada como un arreglo. Por ejemplo, se
pueden hacer cosas como:
main()
{
int *ip, i;
ip = (int *) malloc(100 * sizeof(int) );
ip[0] = 1000;
for (i=0; i<100; ++i)
scanf("%d",ip++);
}
Cuando se ha terminado de usar una porción de memoria siempre se deberá liberar usando la función free(). Esta función permite que la memoria liberada este disponible nuevemente quizás para otra llamada de la función malloc()
La función free() toma un apuntador como un argumento y libera la memoria a la cual el apuntador hace referencia.
Existen dos funciones adicionales para reservar memoria, calloc() y realloc(). Los prototipos son dados a continuación:
void *calloc(size_t nmemb, size_t size); void *realloc(void *ptr, size_t size);
Cuando se usa la función malloc() la memoria no es inicializada (a cero) o borrada. Si se quiere inicializar la memoria entonces se puede usar la función calloc. La función calloc es computacionalmente un poco más cara pero, ocasionalmente, más conveniente que malloc. Se debe observar también la diferencia de sintaxis entre calloc y malloc, ya que calloc toma el número de elementos deseados (nmemb) y el tamaño del elemento (size), como dos argumentos individuales.
Por lo tanto para asignar a 100 elementos enteros que estén inicializados a cero se puede hacer:
int *ip; ip = (int *) calloc(100, sizeof(int) );
La función realloc intenta cambiar el tamaño de un
bloque de memoria previamente asignado. El nuevo tamaño puede ser más
grande o más pequeño. Si el bloque se hace más grande, entonces el
contenido anterior permanece sin cambios y la memoria es agregada al
final del bloque. Si el tamaño se hace más pequeño entonces el
contenido sobrante permanece sin cambios.
Si el tamaño del bloque original no puede ser redimensionado, entonces realloc
intentará asignar un nuevo bloque de memoria y copiará el contenido
anterior. Por lo tanto, la función devolverá un nuevo apuntador (o de
valor diferente al anterior), este nuevo valor será el que deberá
usarse. Si no puede ser reasignada nueva memoria la función realloc devuelve NULL.
Si para el ejemplo anterior, se quiere reasignar la memoria a 50 enteros en vez de 100 apuntados por ip, se hará;
ip = (int *) realloc ( ip, 50*sizeof(int) );
Regresando al ejemplo del capítulo anterior se definió la estructura:
typedef struct {
int valor;
struct ELEMENTO *sig;
} ELEMENTO;
La cual puede crecer en forma dinámica.
ELEMENTO *liga; liga = (ELEMENTO *) malloc( sizeof(ELEMENT) ); /* Asigna memoria para liga */ free(liga); /* libera la memoria asignada al apuntador liga usando free() */
La cola es una colección de ordenada de elementos de la que se pueden borrar elementos en un extremo (llamado el frente de la cola) o insertarlos en el otro (llamado el final de la cola.
Se muestra a continuación el código completo para manipular esta estructura:
/* cola.c */
/* Demo de estructuras dinamicas en C */
#include <stdio.h>
#define FALSO 0
typedef struct nodo {
int dato;
struct nodo *liga;
} elemento_lista;
void Menu (int *opcion);
elemento_lista * AgregaDato (elemento_lista * apuntlista, int dato);
elemento_lista * BorrarDato (elemento_lista * apuntlista);
void ImprCola (elemento_lista * apuntlista);
void LimpCola (elemento_lista * apuntlista);
main ()
{
elemento_lista listmember, *apuntlista;
int dato, opcion;
apuntlista = NULL;
do {
Menu (&opcion);
switch (opcion) {
case 1:
printf ("Ingresa un dato que sera agregado ");
scanf ("%d", &dato);
apuntlista = AgregaDato (apuntlista, dato);
break;
case 2:
if (apuntlista == NULL)
printf ("¡Cola vacia!\n");
else
apuntlista = BorrarDato (apuntlista);
break;
case 3:
ImprCola (apuntlista);
break;
case 4:
break;
default:
printf ("Opcion no valida - intentar nuevamente\n");
break;
}
} while (opcion != 4);
LimpCola (apuntlista);
} /* fin de main */
void Menu (int *opcion)
{
char local;
printf("\nEntre\t1 para agregar un dato,\n\t2 para borrar un dato,\n\t3 para mostrar el contenido de la cola\n\t4 para salir\n");
do {
local = getchar ();
if ((isdigit (local) == FALSO) && (local != '\n'))
{
printf ("\nSe debe ingresar un entero.\n");
printf ("Teclee 1 para agregar, 2 para borrar, 3 para imprimir, 4 para salir\n");
}
} while (isdigit ((unsigned char) local) == FALSO);
*opcion = (int) local - '0';
}
elemento_lista *AgregaDato (elemento_lista *apuntlista, int dato)
{
elemento_lista * lp = apuntlista;
if (apuntlista != NULL) {
while (apuntlista -> liga != NULL)
apuntlista = apuntlista -> liga;
apuntlista -> liga = (struct nodo *) malloc (sizeof (elemento_lista));
apuntlista = apuntlista -> liga;
apuntlista -> liga = NULL;
apuntlista -> dato = dato;
return lp;
}
else
{
apuntlista = (struct nodo *) malloc (sizeof (elemento_lista));
apuntlista -> liga = NULL;
apuntlista -> dato = dato;
return apuntlista;
}
}
elemento_lista *BorrarDato (elemento_lista *apuntlista)
{
elemento_lista *tempp;
printf ("El elemento borrado es %d\n", apuntlista -> dato);
tempp = apuntlista -> liga;
free (apuntlista);
return tempp;
}
void ImprCola (elemento_lista *apuntlista)
{
if (apuntlista == NULL)
printf ("La cola esta vacia !!\n");
else
while (apuntlista != NULL) {
printf ("%d\t", apuntlista -> dato);
apuntlista = apuntlista -> liga;
}
printf ("\n");
}
void LimpCola (elemento_lista *apuntlista)
{
while (apuntlista != NULL) {
apuntlista = BorrarDato (apuntlista);
}
}
Por lo tanto, si la lista de entrada es: 14 15 4 9 7 18 3 5 16 4 20 17 0 14 5, se debe generar el árbol de la figura 9.1.
Para obtener una lista ordenada en forma ascendente, recorrer el árbol en preorden (depth-first order), es decir, visitar la raíz, recorrer el subárbol izquierdo en orden y recorrer el subárbol derecho en orden. Por lo que la salida deberá ser:
Los valores ordenados son: 0 3 4 4 5 5 7 9 14 14 15 16 17 18 20
Mostrar 10 valores por línea.
![\includegraphics[width=3in, clip]{figuras/arbol.eps}](img18.png)