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

botões

botões

A alocação dinâmica de memória é uma característica importante das linguagens de alto nível. No C constitui uma fraçã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 apresentar duas aplicações comuns da alocação dinâmica:

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

Tópicos

• Malloc
• Listas ligadas
• Exercícios

setas

setas

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 início 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 correto é muito importante para assegurar que a aritmética com os apontadores é efetuada de modo correto.

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 operador sizeof pode ser usado para determinar o tamanho (em bytes) de qualquer tipo ou variável.

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

  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.

Exemplos:

  ip[0] = 1041;

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

setas

setas

Listas ligadas

Vamos ver como se pode 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.

setas

setas

Exercícios

• Escreva um programa para armazenar num array um 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 mesmo número de inteiros; por fim deverá lê-los do teclado e reescreve-los no ecrã. Antes de terminar, deverá libertar a memória alocada.
• Escreva um programa que acrescente funcionalidade ao programa de listas ligadas mostrado atrás.
• 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

setas

setas