Estructuras C

Cap´
ıtulo 4

Estructuras de datos: memoria
din´mica
a
La Reina se puso congestionada de furia, y, tras lanzarle una mirada felina, empez´ a
o
gritar: ✭✭¡Que le corten la cabeza! ¡Que le corten. . . !✮✮.
Lewis Carroll, Alicia en el Pa´ de las Maravillas.
ıs
Vimos en el cap´
ıtulo 2 que los vectores de C presentaban un serio inconveniente con respecto a
las listas de Python: su tama˜odeb´ ser fijo y conocido en tiempo de compilaci´n, es decir, no
n
ıa
o
pod´
ıamos alargar o acortar los vectores para que se adaptaran al tama˜o de una serie de datos
n
durante la ejecuci´n del programa. C permite una gesti´n din´mica de la memoria, es decir,
o
o
a
solicitar memoria para albergar el contenido de estructuras de datos cuyo tama˜o exacto no
n
conocemos hasta que se hainiciado la ejecuci´n del programa. Estudiaremos aqu´ dos formas
o
ı
de superar las limitaciones de tama˜o que impone el C:
n
mediante vectores cuyo tama˜o se fija en tiempo de ejecuci´n,
n
o
y mediante registros enlazados, tambi´n conocidos como listas enlazadas (o, simplemente,
e
listas).
Ambas aproximaciones se basan en el uso de punteros y cada una de ellas presenta diferentesventajas e inconvenientes.

4.1.

Vectores din´micos
a

Sabemos definir vectores indicando su tama˜o en tiempo de compilaci´n:
n
o
1

#define TALLA 10

2
3

int a[TALLA];

Pero, ¿y si no sabemos a priori cu´ntos elementos debe albergar el vector?1 Por lo estudiado
a
hasta el momento, podemos definir TALLA como el n´mero m´s grande de elementos posible,
u
a
el n´mero de elementos parael peor de los casos. Pero, ¿y si no podemos determinar un
u
n´mero m´ximo de elementos? Aunque pudi´ramos, ¿y si ´ste fuera tan grande que, en la
u
a
e
e
pr´ctica, supusiera un despilfarro de memoria intolerable para situaciones normales? Imagina
a
una aplicaci´n de agenda telef´nica personal que, por si acaso, reserva 100000 entradas en un
o
o
vector. Lo m´s probable es que unusuario convencional no gaste m´s de un centenar. Estaremos
a
a
desperdiciando, pues, unas 99900 celdas del vector, cada una de las cuales puede consistir en
un centenar de bytes. Si todas las aplicaciones del ordenador se dise˜aran as´ la memoria
n
ı,
disponible se agotar´ rapid´
ıa
ısimamente.
1 En la secci´n 3.5.3 vimos c´mo definir vectores locales cuya talla se decide al ejecutar unafunci´n: lo que
o
o
o
denominamos ✭
✭vectores de longitud variable✮ Nos proponemos dos objetivos: por una parte, poder redimensionar
✮.
vectores globales; y, por otro, vamos a permitir que un vector crezca y decrezca en tama˜o cuantas veces
n
queramos. Los ✭
✭vectores de longitud variable✮ que estudiamos en su momento son inapropiados para cualquiera
✮
de estos dos objetivos.Introducci´n a la Programaci´n con C
o
o

213

4.1 Vectores din´micos
a

4.1.1.

malloc, free y NULL

Afortunadamente, podemos definir, durante la ejecuci´n del programa, vectores cuyo tama˜o
o
n
es exactamente el que el usuario necesita. Utilizaremos para ello dos funciones de la biblioteca
est´ndar (disponibles incluyendo la cabecera stdlib.h):
a
malloc (abreviatura de ✭✭memoryallocate✮✮, que podemos traducir por ✭✭reservar memoria✮✮): solicita un bloque de memoria del tama˜o que se indique (en bytes);
n
free (que en ingl´s significa ✭✭liberar✮✮): libera memoria obtenida con malloc, es decir, la
e
marca como disponible para futuras llamadas a malloc.
Para hacernos una idea de c´mo funciona, estudiemos un ejemplo:
o
vector dinamico.c

vector dinamico.c
1
2

#include#include

3
4
5
6
7

int main(void)
{
int * a;
int talla, i;

8

printf ("N´mero de elementos: "); scanf ("%d", &talla);
u
a = malloc( talla * sizeof (int) );
for (i=0; ip[0].x) * (pol ->p[pol ->puntos-1].x - pol ->p[0].x) +
(pol ->p[pol ->puntos-1].y - pol ->p[0].y) * (pol ->p[pol ->puntos-1].y - pol ->p[0].y) );
return perim;

38
39
40
41
42
43
44
45

}

46...