Capítulo 10 - Alocação Dinâmica de Memória

A alocação dinâmica de memórica é uma característica importante das linguagens de alto nível. No C constitui uma fracção muito importante da sua definição (juntamente com os apontadores). A alocação dinâmica permite-nos criar tipos de dados e estruturas de qualquer tamanho e comprimento que satisfaça as nossas necessidades, durante a execução de um programa. Vamos ver duas aplicações comuns da alocação dinâmica:

arrays dinâmicos
estruturas de dados dinâmicas (listas ligadas)

Malloc

A função malloc() é usada para "pedir" ao sistema operativo uma porção de memória. O seu protótipo é:

void *malloc(int number_of_bytes);

A função retorna um apontador genérico (void *) para o ínicio da memória alocada que deverá conter espaço suficiente para armazenar number_of_bytes bytes. Se não for possível alocar essa quantidade de memória a função retorna o apontador NULL.

Então se quisermos alocar espaço para 100 inteiros podemos usar:

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

Notar o uso de um cast na saída da função e também o uso do operador sizeof para determinar, em bytes, o tamanho de um inteiro. O cast para o tipo de apontador correcto é muito importante para assegurar que a aritmética com os apontadores é efectuada de modo correcto. O uso do operador sizeof também é indispensável, mesmo que se saiba o tamanho do tipo de dados, para tornar o código independente da máquina em que for compilado. O seu uso torna o código facilmente portável. O operador sizeof pode ser usado para determinar o tamanho (em bytes) de qualquer tipo ou variável.

As seguintes utilizações são todas correctas:

int i;
struct coord { float x, y, z };
typedef struct coord pt;
sizeof(int); sizeof(i);
sizeof(struct coord); sizeof(pt);

Após a alocação de memória e a atribuição do seu endereço inicial a um apontador, podemos usá-lo como se fosse um array, aproveitando a quase identidade entre arrays e apontadores. Ou seja, podemos fazer coisas como as que se seguem:

ip[0] = 1041;

for (k=0; k<100; k++)
scanf("%d", ip++);

Listas ligadas

Vamos ver como se pode agora construir uma estrutura dinâmica através de uma lista ligada em C.

Para isso necessitamos da definição de um nó:

typedef struct {
int value;
element *next;
} element;

A alocação de novos elementos poderá ser feita utilizando a função malloc(), como se mostra:

link = (element *) malloc(sizeof(element));

Quando o elemento tiver cumprido a sua missão e já não for necessário, é indispensável libertar a memória alocada. A libertação de memória alocada com malloc() (e só essa) faz-se através do endereço da mesma, chamando a função standard free():

free(link);

Um exemplo completo é o programa queue.c.

Exercícios

1. Escreva um programa para armazenar num array um certo número de inteiros. O programa deverá começar por perguntar ao utilizador o número de inteiros a armazenar; deverá de seguida alocar dinamicamente um array de inteiros capaz de armazenar esse número de inteiros; e por fim deverá lê-los do teclado e reescrevê-los no vídeo. Antes de terminar não esquecer de libertar a memória alocada.

2. Escreva uma programa que acrescente funcionalidade ao programa de listas ligadas mostrado atrás.

3. Escreva um programa que ordene uma sequência de valores utilizando uma árvore binária (com apontadores). Uma árvore binária é uma estrutura em que cada nó pode estar ligado, no máximo, a outros dois (o filho à esquerda e o filho à direita). Para ordenar os valores estes deverão ser inseridos na árvore (esta deverá ser uma árvore de pesquisa, i. e., para cada nó, todos os descendentes à esquerda são menores e todos os descendentes à direita são maiores), e de seguida esta deverá ser listada em ordem simétrica.

Os valores deverão ser inteiros e a saída do programa deverá listá-los em ordem crescente com o máximo de 10 valores em cada linha. Exemplo de saída:

Os valores ordenados são:
2 4 8 12 15 18 23 27 29 31
41 52 55 58