Capitulo2-Gestão de Memória Dinâmica

Prévia do material em texto

Estrutura de Dados e Algoritmos em C 
Para uso exclusivo dos alunos da Faculdade de Engenharia de Universidade Católica de Angola Prof. Manuel Menezes 14 
 
 
 
Capítulo 2 
Gestão de Memória Dinâmica 
 
 
“ Qualquer pessoa pode escrever um programa que um computador entende, mas os bons programa-
dores escrevem programas que os humanos entende” 
 
 - Martin Fowler - 
 
Sumário: 
 
2.1 - Introdução 
2.2 - Gestão de Memória Dinâmica 
2.3 - Alocação de Memória Dinâmica 
2.4 - Operações de Leitura e Atribuição 
2.5 - Libertação de Memória 
2.6- Realocação de Memória 
2.7 - Alocação Dinâmica de Vectores 
2.8 - Alocação Dinâmica de Matrizes 
2.9 -Alocação Dinâmica de Estruturas 
 
2.1 - Introdução 
 
Os programas que foram desenvolvidos para uma primeira disciplina de 
programação de computadores, normalmente utilizam a gestão de memória 
estática. Esses programas caracterizam-se por determinar a quantidade de 
memória para sua execução em tempo de compilação. Como consequência, o 
espaço necessário para o programa ser executado não pode ser alterado e fica 
ao dispor do programa de forma exclusiva durante a sua execução. 
 
Neste capítulo, estudaremos os métodos para desenvolver programas que 
utilizam a gestão da memória de dinâmica, ou seja, a quantidade de memória 
para executar um programa, poderá ser aumentada ou diminuída em cada 
instante. Para dominar esses métodos o leitor terá a necessidade de conhecer 
às técnicas de manipulação de ponteiros. 
 
Estrutura de Dados e Algoritmos em C 
Para uso exclusivo dos alunos da Faculdade de Engenharia de Universidade Católica de Angola Prof. Manuel Menezes 15 
 
 
2.2- Gestão de Memória Dinâmica 
 
Para desenvolver programas que utilizam a gestão de memória dinâmica, 
necessitamos de funções especiais para solicitar blocos consecutivos de 
memória. Uma vez obtidos esses blocos, o programa vai armazenar dados, e 
quando essa quantidade de memória não for mais necessária, esses blocos 
serão devolvidos à memória principal. 
 
Se o programa solicitar blocos de memória e não os libertar, e se essa práctica 
for repetida, o programa poderá apropriar-se de forma exclusiva de uma grande 
quantidade de memória e bloquear o funcionamento do sistema operativo. 
 
A gestão de memória dinâmica exige algumas precauções no desenvolvimento 
do software. Por este motivo, muitas linguagens de programação de alto-nível 
mais recentes (Lisp, Java, Scheme, Python, Perl, Mathematica, e outras), 
efectuam a gestão de memória dinâmica de forma automática, permitindo que o 
programador se concentre na implementação do algoritmo e nos modelos de 
dados associados, sem ter a necessidade de preocupar-se com os problemas 
de dimensionamento de variáveis ou a quantidade de memória necessário para 
o armazenamento de dados. 
 
Neste contexto, é necessário perguntar quais as vantagens de programar em C 
e porque o C contínua a ser utilizado em muitas áreas de aplicação. Existem 
algumas respostas para estas questões, que daremos a seguir: 
 
A gestão de memória dinâmica permite a construção de programas mais 
eficientes e com a utilização de menores recursos de hardware. 
 
A linguagem C é a linguagem de alto-nível que possui mais recursos para emular 
a linguagem máquina. Dada essa aproximação, a maioria dos sistemas 
operativos modernos são escritos em C; 
 
A maioria dos compiladores de linguagens de alto nível, incluindo o próprio C, 
são actualmente escritos e desenvolvidos em C. Ou seja, nesta perspectiva, o C 
é hoje uma linguagem indispensável `a geração da maior parte das linguagens 
de programação e por esse motivo é denominado por “linguagem das 
linguagens”. 
 
2.3 - Alocação de Memória Dinâmica 
 
Para solicitar um bloco de memória durante a execução do programa, é 
necessário invocar a função malloc (memory allocation), que possui a seguinte 
sintaxe: 
 
void *malloc (size_t numero_de_bytes); 
 
esta função recebe como parâmetro o tamanho do espaço solicitado em bytes e 
devolve um ponteiro que faz referência ao primeiro byte do bloco disponibilizado, 
ou um ponteiro nulo se o pedido não for satisfeito. 
 
Estrutura de Dados e Algoritmos em C 
Para uso exclusivo dos alunos da Faculdade de Engenharia de Universidade Católica de Angola Prof. Manuel Menezes 16 
 
 
Por exemplo, para solicitar 1000 bytes de memória, e apontar para o endereço 
desse bloco o ponteiro ptr, devemos utilizar as seguintes linhas de código: 
 
void *ptr; 
ptr = malloc(1000); 
 
O ponteiro retornado pela função malloc() é um ponteiro genérico e não possui um 
tipo de dados específico. Por este facto, ele é declarado como void *. 
 
2.4 - Operações de Leitura e Atribuição 
 
Com ponteiros genéricos ou ponteiros do tipo void *, não podemos efectuar 
operações de atribuição e de leitura, porque o programa não consegue 
armazenar dados nos blocos de memória que foram alocadas. 
 
Para tornar essas operações possíveis é necessário converter de forma explicita, 
utilizando o operador cast, o endereço obtido pela função malloc(), para um 
ponteiro com o tipo de dados que iremos manipular. 
 
Por exemplo, para armazenar um número inteiro na memória dinâmica, devemos 
converter o ponteiro genérico para um ponteiro do tipo inteiro. 
 
void *ptr; 
int *pnumero; 
ptr = malloc(1000); 
pnumero = (int *)ptr; 
 
Agora, o ponteiro pnumero e o ponteiro ptr apontam para o início de um bloco de 
memória dinâmica obtido pela função malloc(). Através do ponteiro pnumero, o 
programa poderá manipular esse bloco de memória como se trata-se de um 
vector de números inteiros. 
 
Por exemplo, podemos armazenar no endereço apontado por pnumero um valor 
qualquer como fazemos com as variáveis elementares: 
 
*pnumero = 10; 
 
Mas, muitas vezes temos a necessidade de armazenar o endereço retornado 
pela função malloc() num ponteiro específico. Para isso efectuamos a seguinte 
conversão: 
 
int *pnumero; 
pnumero = (int *)malloc(1000); 
*pnumero = 10; 
 
 
 
 
 
Estrutura de Dados e Algoritmos em C 
Para uso exclusivo dos alunos da Faculdade de Engenharia de Universidade Católica de Angola Prof. Manuel Menezes 17 
 
O ponteiro retornado pela função malloc() é a única forma de aceder à um bloco 
de memória dinâmica disponibilizada. Através desse ponteiro o programa pode 
escrever e ler dados nesse espaço. Mas se durante a execução do programa 
este ponteiro for pedido, esse espaço permanecerá alocado até o fim do 
programa e a sua localização será impossível de detectar. 
 
2.5 - Libertação de Memória Dinâmica 
 
Na primeira disciplina de fundamentos de programação, o leitor certamente viu 
que o espaço de memória para as variáveis locais é reservado em memória 
quando uma função é chamada, e automaticamente libertado quando a função 
termina. 
 
Ao contrário das variáveis locais, os blocos de memória solicitados pela função 
malloc() permanece sob propriedade do programa por tempo indeterminado. 
Quando esse programa não precisar mais dessa porção de memória, é neces-
sário devolve-lo à memória principal. Essa acção deve ser feita pela função free() 
que possui a seguinte sintaxe: 
 
void free (void *ptr); 
 
no qual 
 
*ptr é um ponteiro para um bloco de memória que deve ser liberado. 
 
Uma vez libertado o bloco de memória, é impossível aceder a esse espaço. Após a 
execução dessa função, todos os ponteiros que fazem referencia a esse espaço 
tornam-se inválidos. 
 
Constitui uma boa práctica de programação, executar a chamada de uma função 
free() para cada ponteiro obtido por uma função malloc(). Desta forma temos a 
certeza que toda a memória alocado foi libertada. 
 
2.6 – Realocação de Memória 
 
Para aumentar ou diminuir durante a execução de um programa a quantidadede memória, também podemos utilizar a função realloc, que possui a seguinte 
sintaxe: 
 
void *realloc (void *ptr, size_t total_new_size); 
 
no qual 
 
*ptr é o ponteiro para o bloco de memória previamente reservado; 
total_new_size é a nova dimensão do bloco de memória a reservar. 
 
Devemos salientar que o segundo argumento, size_t total_new_size, tem um 
significado semelhante ao da função malloc (size_t total_size). 
 
 
Estrutura de Dados e Algoritmos em C 
Para uso exclusivo dos alunos da Faculdade de Engenharia de Universidade Católica de Angola Prof. Manuel Menezes 18 
 
Suponhamos que no início de um programa tínhamos reservado um bloco de 
memória para a n inteiros: 
 
x = (int*) malloc(n, sizeof(int)); 
 
e, mais tarde, verificamos que tínhamos a necessidade de acrescentar 1000 po-
sições a este bloco de memória. Este resultado poderia ser obtido com a instru-
ção: 
 
x = (int*) realloc(x, (n+1000)*sizeof(int)); 
 
Para consolidar os conhecimentos, vamos descrever em pormenor o funciona-
mento dessas instruções. Suponhamos sem perda da generalidade que inicial-
mente tínhamos n=2000, e que o valor de x resultante da chamada da função 
malloc() era 10000. Isso quer dizer que reservamos um bloco de memória que 
começa no endereço 10000 e vai até o endereço 11999. Quando executarmos 
à chamada da função realloc(), duas situações podem ocorrer. Se os endereços 
de memória entre 12000 e 12999 estiverem livres, o bloco de memória é auto-
maticamente prolongado. Mas se algum endereço de memória estiver ocupado, 
é necessário deslocar todo o bloco de memória para uma nova região. Essa nova 
região é mapeada, e a função realloc() retorna o endereço da primeira posição 
de memória. 
 
2.7 - Alocação Dinâmica de Vectores 
 
Uma das aplicações mais interessantes na gestão de memória dinâmica é a 
criação e a manipulação de vectores. Nos programas que desenvolvemos, 
declaramos um vector com MAX elementos, onde MAX é uma constante, e esse 
vector é normalmente carregado com um número inferior de elementos. 
 
Durante o processo de compilação é alocado um espaço para armazenar esse 
vector, mas o programa não utiliza normalmente todo o espaço disponibilizado. 
Uma parte desse espaço é desperdiçado e só volta a estar disponível para o 
computador, quando o programa terminar a sua execução. 
 
O nosso objectivo é declarar o tamanho do vector a maior precisão, ou seja, o 
vector vai ser criado em tempo de execução com o tamanho exacto para que 
não se despedisse nenhum bloco de memória. 
 
Mas, para criarmos um vector de forma dinâmica, o compilador calcula o número 
de bytes que vai necessitar, e esse número depende da arquitectura da máquina. 
Por exemplo, para computadores de 16 bits um inteiro é armazenado em dois 
bytes, mas se a arquitectura for de 32 bits, um inteiro é armazenado em quatro 
bytes. 
 
Para tornar o programa genérico e o mais independente da arquitectura, 
devemos utilizar a função biblioteca sizeof(), que possui a seguinte sintaxe: 
 
int sizeof nome da variável; 
int sizeof ( tipo de dados); 
 
Estrutura de Dados e Algoritmos em C 
Para uso exclusivo dos alunos da Faculdade de Engenharia de Universidade Católica de Angola Prof. Manuel Menezes 19 
 
 
onde 
o tipo de dados é qualquer tipo de dados suportado pela linguagem C. 
 
Esta função retorna o número de bytes necessários para armazenar esse tipo de 
dados ou essa variável. 
 
Então, para criar um ponteiro para um vector, devemos seguir a seguinte 
sequencia de passos: 
 
1º- Calcular com a função sizeof() o número de bytes para armazenar a estrutura; 
2º- Invocar a função malloc() para retornar um apontador genérico que aponta 
para o primeiro byte desse bloco de memória; 
3º- Converter o ponteiro genérico retornado pela função malloc(), para um 
ponteiro cujo tipo de dados é compatível com o tipo do vector. 
 
Mas por consistência de código, devemos verificar se o ponteiro retornado pela 
função malloc() é válido. Se ele for igual a NULL, o pedido não foi satisfeito. Isso 
quer dizer que o computador não possui memória disponível e devemos notificar 
tal facto ao utilizador. 
 
Vamos consolidar este conceito com alguns exemplos simples. O primeiro 
consiste em desenvolver um programa para carregar num vector n números 
inteiros digitados pelo utilizador. 
 
A primeira solução consiste em utilizar a gestão de memória estática. 
 
#include <stdio.h> 
main () 
 { 
 int v[3000], n; 
 n = lerQtdNumjeros(); 
 for (i = 0; i < n, i++) 
 { 
 printf (“Insira um inteiro: “); 
 scanf (“%d”, &v[i]); 
 } 
 . . . 
 return 0; 
 } 
 
Agora, vamos reescrever esse programa, com a gestão de memória dinâmica. 
 
#include <stdio.h> 
main () 
 { 
 int *v, n; 
 
Estrutura de Dados e Algoritmos em C 
Para uso exclusivo dos alunos da Faculdade de Engenharia de Universidade Católica de Angola Prof. Manuel Menezes 20 
 
 n = lerQtdNumjeros(); 
 v = (int*) malloc (n*sizeof (int)); 
 if (v == NULL) 
 printf ("Erro: memória insuficiente \n "); 
 else 
 { 
 for (i = 0; i < n, i++) 
 { 
 printf (“Insira um inteiro: “); 
 scanf (“%d”, &v[i]); 
 } 
 . . . 
 free (v); 
 } 
 return 0; 
 } 
 
Na chamada da função malloc(), dois aspectos devem ser considerados. Em 
primeiro lugar o operador sizeof() ´e um operador intrínseco da linguagem C que 
devolve a dimensão em bytes do tipo ou variável indicado no argumento. Por 
outro lado, à esquerda da função malloc() foi acrescentada e expressão (int*). 
Esta expressão funciona como um operador de cast, e obriga à conversão do 
apontador genérico devolvido pela função malloc() para um ponteiro do tipo in-
teiro. Em geral, na operação de cast é indicado o tipo do ponteiro que se encontra 
do lado esquerdo da atribuição. 
 
Após a reserva dinâmica de memória, o ponteiro v pode ser tratado como um 
vector convencional. É evidente que o índice i, não pode ultrapassar a posição 
n-1, porque essas áreas de memória são inválidas. 
 
O segundo exemplo consiste em desenvolver um programa com funções para 
calcular a média e a variância para n números reias. 
 
#include <stdio.h> 
#include <stdlib.h> 
 int main () 
 { 
 int i, n; 
 float med, var; 
 n = lerQtdNumeros(); 
 float *v = (float*) malloc( n *sizeof (float)); 
 if (v == NULL) 
 printf ("Erro: memória insuficiente \n "); 
 else 
 { 
 for ( i = 0; i < n; i++ ) 
 { 
 printf (“Insira um inteiro: “); 
 scanf (“%d”, &v[i]); 
 } 
 
Estrutura de Dados e Algoritmos em C 
Para uso exclusivo dos alunos da Faculdade de Engenharia de Universidade Católica de Angola Prof. Manuel Menezes 21 
 
 med = media(n, v); 
 var = variancia(n, v, med); 
 printf ("Media = %f Variancia = %f \n", med, var); 
 free(v); 
 } 
 return 0; 
 } 
 
onde a função para calcular a média recebe como parâmetro o número de 
elementos do vector e um ponteiro para o primeiro elemento do vector. 
 
float media (int n, float *v) 
 { 
 int i; float s = 0.0; 
 for (i = 0; i < n; i++) 
 s += v[i]; 
 return s/n;} 
 
e a função para calcular a variância recebe como parâmetro o número de 
elementos do vector, um ponteiro para o primeiro elemento do vector e o valor 
da média. 
 
float variancia (int n, float *v, float m) 
 { 
 int i; float s = 0.0; 
 for (i = 0; i < n; i++) 
 s += (v[i] - m) * (v[i] - m); 
 return s/n; 
 } 
 
Para tornar o programa mais elegante e mais fácil de ler, devemos desenvolver 
uma função para alocar uma porção de memória. Essa função retorna um se a 
operação foi executada com sucesso e zero no caso contrário. Uma possível 
solução é dada por: 
 
 boolean aloca ( float *v, int n) 
 { 
 *v = (float*) malloc( n *sizeof (float)); 
 return ( v == NULL ); 
 } 
 
 
 
2.8 - Alocação Dinâmica de Matrizes 
 
Suponhamos que num determinado programa, pretendemos substituir a 
sequência de instruções 
 
 
Estrutura de Dados e Algoritmos em C 
Para uso exclusivo dos alunos da Faculdade de Engenharia de Universidade Católica de Angola Prof. Manuel Menezes 22 
 
#define N ... 
#define M ... 
... 
int x[N][M]; 
 
por uma estrutura dinâmica, em que os limites n e m são variáveis cujo valor 
deverá ser definido na fase de execução do programa. 
 
A solução para este problema consiste em substituir a estrutura x por um vector 
dinâmico de ponteiros, em que cada posição é, por sua vez, um vector dinâmico 
de ponteiros. Considere por exemplo, que se pretende criar uma matriz de di-
mensão n por m. Uma possível solução é descrita pela seguinte função. 
 
boolean aloca ( int ** x , int n , int m) 
 { 
 int k; 
 x = (int**) malloc(n, sizeof(int*)); 
 if (x == NULL) return 0; 
 else 
 { 
 for (k = 0 ; k < n ; k++) 
 { 
 x[k] = (int*) malloc(m,sizeof(int)); 
 if (x == NULL) return 0; 
 } 
 } 
 return 1; 
 } 
 
Agora, vamos criar uma matriz 4 por 2 e inicializa-la com valores inteiros digita-
dos pelo utilizador. Uma possível solução para esse problema é dada pelo se-
guinte programa: 
 
int main() 
 { 
 int k, j , n, m; 
 int **x; 
 n = lerDimensaoLinha(); 
 m = lerDimensaoColuna(); 
 if ( ! aloca ( x , n , m) ) 
 printf (" Erro: memória insuficiente \n "); 
 else 
 { 
 for (k = 0; k < n ; k++) 
 for (j = 0; j < m ; j++) 
 x[k][j] = lerElemento(); 
 } 
 return 0; 
 } 
 
 
Estrutura de Dados e Algoritmos em C 
Para uso exclusivo dos alunos da Faculdade de Engenharia de Universidade Católica de Angola Prof. Manuel Menezes 23 
 
Este exemplo mostra que para criar uma matriz em memória dinâmica, devemos 
declarar um ponteiro de ponteiros para os elementos da matriz e em seguida, 
reservar dinâmicamente um vector de ponteiros e criar dinamicamente os vecto-
res correspondentes a cada linha. 
 
2.9 - Alocação Dinâmica de Estruturas 
 
O procedimento para alocação dinâmica de estruturas (struct) é análogo ao 
procedimento para a alocação dinâmica de vectores. Para mostrar essa 
analogia, veremos a declaração de um ponto no plano cartesiano. 
 
typedef struct 
 { 
 int ordenada; 
 int abcissa; 
 } TPlano; 
 
Para criar um ponteiro para uma estrutura devemos utilizar os mesmos passos 
que utilizamos para criar um ponteiro para um vector. Veremos a seguir uma 
função que atende a essa necessidade. 
 
 boolean aloca ( TPlano *coordenada, int n ) 
 { 
 *Coordenda = (TPlano*)malloc ( n* sizeof (TPlano) ); 
 return (coordenada == NULL) ; 
 } 
 
Suponhamos que pretendemos colocar zeros em todos os elementos de um 
vector do tipo plano. Como o vector será criado em tempo de execução, o 
utilizador deverá definir o número de elementos e, esse número, será 
armazenado numa variável n. 
 
#include <stdlib.h> 
#include <stdio.h> 
int main ( ) 
{ 
 int i, j, n; 
 typedef struct 
 { 
 int ordenada; 
 int abcissa; 
 } TPlano; 
 n = lerQtdElementos(); 
 if ( !aloca (tabPonto, n )) 
 printf (" Erro: memória insuficiente \n "); 
 else 
 { 
 for ( i = 0; i < n; i++ ) 
 { 
 
Estrutura de Dados e Algoritmos em C 
Para uso exclusivo dos alunos da Faculdade de Engenharia de Universidade Católica de Angola Prof. Manuel Menezes 24 
 
 (tabPonto+i)->ordenada = 0; 
 (tabPonto+i)->abcissa = 0 ; 
 } 
 free (tabPontos); 
 return 0; 
 } 
 } 
 
Mas poderíamos realizar essa operação, com a seguinte notação: 
 
 for (i = 0; i < n; i++) 
 { 
 (* (tabPonto+i).ordenada = 0; 
 (tabPonto+i).abcissa = 0 ; 
 } 
 
Contudo, utilizamos uma notação é mais pesada, muito susceptível a erros, e 
facto, raramente utilizada em ambientes profissionais. 
 
Não é por demais salientar que a notação (tabPonto+i)->ordenada é equivalente 
a notação tabPonto[i]->ordenada. A primeira está na notação de ponteiros 
enquanto a segunda na notação vectorial. 
 
 
2.10 - Exercícios