UNIVERSIDADE FEDERAL DO RIO GRANDECENTRO DE CIÊNCIAS COMPUTACIONAIS

INTRODUÇÃO A CIÊNCIA DA COMPUTAÇÃO

Apostila de Alocação Dinâmica na

Linguagem de Programação C

André Mendes da RosaMestrando em Engenharia de Computação

Diana AdamattiProfessora Doutora do Centro de Ciências Computacionais

Rio Grande, 01 de fevereiro de 2013.

IntroduçãoEsta apostila de alocação dinâmica em C foi desenvolvida para dar uma noção inicial das

funções de alocação dinâmica na Linguagem de Programação C. Portanto, inicialmente, é

necessário um estudo sobre ponteiros, pois através do conhecimento destes, fica mais

fácil trabalhar com Estruturas de Dados, as quais na maioria dos casos faz uso de

alocação dinâmica.

A apostila não pretende findar o assunto, é apenas um incentivo para os alunos se

prepararem para disciplinas de computação mais avançadas, sendo necessário que os

exercícios da apostilas sejam feitos e analisados, seus valores sejam trocados,

implementações diferentes sejam feitas, pois isso vai facilitar um maior aprendizado e

consolidação do conhecimento em alocação dinâmica.

1. PonteirosA linguagem C é altamente dependente dos ponteiros, fazendo com que se torne

imprescindível ter um bom domínio de ponteiros para se tornar o bom programador na

linguagem C.

Um ponteiro é uma variável que contém um endereço de memória, sendo que este

endereço pode ser a localização de uma ou mais variáveis, ou seja, um ponteiro é uma

variável que guarda (aponta) o endereço de outra variável ou variáveis.

Abaixo na Figura 1 está a representação das informações de uma variável comum e uma

variável ponteiro na memória RAM (Random Access Memory – Memória de Acesso

Randômico).

Figura 1. Uma variável comum e uma variável ponteiro.

Tal como variáveis, os ponteiros também possuem um tipo, sendo este tipo relativo ao tipo

da variável que o ponteiro aponta.

tipo_ponteiro nome_ponteiro;

Um ponteiro que aponta para uma variável do tipo X, deve ser declarada da seguinte

forma na linguagem C:

• int ponteiro_para_inteiro; /* ponteiro para inteiro */

• float ponteiro_para_float; /* ponteiro para ponto flutuante */

• char ponteiro_para_caractere; /* ponteiro para caractere */

• double ponteiro_para_double; /* ponteiro para ponto flutuante de precisão dupla */

Existem dois operadores unários que são utilizados com os ponteiros, o operador * que

retorna o valor da variável para a qual o ponteiro aponta e, o operador & que retorna o

endereço de memória da variável apontada pelo ponteiro.

Exemplo: Para entender o uso dos operadores unários * e &.

Saída do Exemplo:

Como pode-se verificar na saída do programa acima, os endereços de memória foram

impressos em hexadecimal, os endereços dos ponteiros diferem das variáveis, pois a

variável está localizada em um local da memória e o ponteiro em outro local, ou seja,

ponteiros tem endereço e guardam endereço e variáveis tem endereço e guardam um

valor. O operador & seguido do ponteiro imprime o endereço da variável apontada e o *

imprime o valor da variável apontada.

Como ponteiros contém endereços de memória, as vezes até para um programador

experiente é um pouco difícil entender as construções de ponteiros e, para isso, um boa

forma de comunicar informação e entender ponteiros é através de diagramas, como o

mostrado na Figura 2.

Figura 2. Uma ilustração de algumas operações com ponteiros.

Para entender a Figura 2 acima, assume-se as declarações: int a, *p1, *p2, *p3;

No passo 1, o ponteiro p1 recebe o endereço de a e passa a apontar para essa variável,

no passo 2, o ponteiro p2 recebe o endereço apontado por p1 e, também, passa a

apontar para a variável a, já no passo 3, o endereço apontado por p2 recebe o valor 100,

fazendo com que a variável inteira a tenha o valor 100. No passo 4, o ponteiro p3 recebe

o valor NULL (representado por uma linha terminada com uma barra dupla), pois como a

linguagem C não faz a verificação de ponteiros, o chamados ponteiros pendentes, ou

seja, que não apontam para nada e podem danificar muitas coisas, devido a poderem

apontar para endereços inválidos.

A linguagem C utiliza ponteiros de três modos diferentes:

• A linguagem C usa ponteiros para criar estruturas dinâmicas de dados, que são

estruturas de dados criadas a partir de blocos de memória localizados na pilha

durante o tempo de execução.

• A linguagem C usa ponteiros para manipular parâmetros de variáveis passados

para as funções.

• Os ponteiros em C oferecem um modo alternativo para acessar informações

armazenadas em matrizes. As técnicas de ponteiros são especialmente valiosas

quando se trabalha com strings de caracteres. Há uma estreita relação entre

matrizes e ponteiros em linguagem C.

2. Agregados e Aritmética de PonteirosUm dos mais comuns usos de ponteiros em C é referenciando dados agregados. Dados

agregados são dados compostos de múltiplos elementos agrupados porque possuem

algum tipo de relação. C suporta dois tipos de dados agregados: Structures (estruturas) e

arrays (vetores e matrizes).

2.1 Structuras (Structs)

Structuras são sequencias de elementos diferentes (heterogêneos) agrupados, de modo

que possam ser tratadas em conjunto como um único tipo de dados coerente. Ponteiros

para struturas são uma importante parte da construção de estruturas de dados. Enquanto

as estruturas nos permitem agrupar dados em conjuntos convenientes, ponteiros deixam

ligar estes conjuntos um ao outro na memória e, pela ligação de estruturas juntas, pode-

se organizá-las de modo significativo para ajudar a resolver problemas reais.

Como um exemplo, considere o encadeamento de um número de elementos juntos na

memória para formar uma lista ligada. Para fazer isto, precisasse usar uma estrutura

como a struct lista no código abaixo:

typedef struct lista {

void *dado;

struct lista *proximo;

} lista;

A estrutura lista é usada para cada elemento que fará parte da lista para ligar uma

sequencia de elementos da lista juntos, é definido proximo para cada elemento da lista

para apontar para apontar para o elemento que vem a seguir. O proximo do último

elemento da lista é definido como NULO para marcar o fim da lista.

O membro dado de cada elemento da lista aponta para o dado que o elemento contém.

Tendo uma lista contendo elementos ligados deste modo, pode-se atravessar a lista

seguindo o ponteiro proximo após o outro.

Estruturas não podem conter instâncias delas mesmas, mas podem conter ponteiros para

instâncias delas mesmas.

2.2 Arrays (vetores e matrizes)

São sequencias de elementos do mesmo tipo (homogêneos) arranjados

consecutivamente na memória. Arrays estão intimamente relacionados com ponteiros. De

fato, quando um identificador de array ocorre em uma expressão. C converte o array

transparentemente em um não modificável ponteiro que aponta para o primeiro elemento

do array.

Exemplos equivalentes:1) Referente a array

int f() {int a[10], *p;p = a;p[0] = 5;

return 0;}

2) Referente a ponteiroint f() {

int a[10], *p;p = a;*p = 5;

return 0;}

Como pode ser observado, no exemplo 1, o primeiro elemento do array a recebe o valor

5, pois p[0] aponta para o primeiro endereço de a. Já no exemplo 2, como o ponteiro

sempre aponta para o primeiro elemento do array, o comando *p = 5, guardará o valor 5

na primeira posição do array a.

Para um melhor entendimento da relação existente entre arrays e ponteiros em C, é só

observar que para acessar o i-ésimo elemento de um array, usa-se a expressão:

a[ i ]

E, a razão para está expressão acessar o i-ésimo elemento de a é que C trata a nesta

expressão do mesmo modo como um ponteiro que aponta para o primeiro elemento de a.

Esta expressão como um todo, é equivalente a:

*(a + i)

A qual é avaliada usando as regras da aritmética de ponteiros. Ou seja, quando adiciona-

se um inteiro i a um ponteiro, o resultado é o endereço mais i vezes o número de bytes do

tipo de dado que o ponteiro faz referência.

Exemplo: Se um array ou ponteiro contém o endereço 0x10000000, no qual uma

sequencia de cinco (5) inteiros de quatro bytes (4 bytes) é armazenada, a[3] irá acessar o

inteiro no endereço 0x1000000c. Este endereço é obtido pela soma de 3X4 = 1210

(Decimal) = c16 (Hexadecimal) ao endereço 0x10000000, como na figura abaixo:

Quando um array ou ponteiro faz referência a vinte (20) caracteres (string – cadeia de

caracteres), a[3] acessa o caractere no endereço 0x10000003, pois um caractere só

ocupa um byte (1 byte), então 3X1 = 310 (Decimal) = 316 (Hexadecimal) somado ao

endereço 0x10000000, tal como na figura abaixo:

A conversão para um array multidimensional (matriz) em C para um ponteiro é análoga a

conversão de um array unidimensional e, para isso, uma linha da matriz é armazenada

inteira em uma linha na memória depois é armazenada a linha seguinte e, assim,

sucessivamente.

Em uma matriz, o índice mais a direita varia mais rapidamente, tal como na figura abaixo:

Figura 3. Representação conceitual de uma matriz 3x2 e representação da mesma na memória.

Onde para acessar o elemento da linha i e da coluna j, usa-se a expressão:

a[i][j]

A qual tem seu equivalente em ponteiros:

*(*(a + i) + j)

3. Ponteiros como Parâmetros para FunçõesPonteiros são uma parte essencial da chamada funções em C. Mais importante ainda,

porque os ponteiros são usados para dar suporte ao tipo de passagem de parâmetros por

referência. Em uma passagem de parâmetros chamada por referência, quando uma

função muda os parâmetros passados para ela, esta mudança persiste após a função

retornar. Ao contrário da passagem de parâmetros em uma chamada por valor, na qual as

mudanças nos parâmetros persistem somente dentro da função.

3.1 Passagem de Parâmetros por Chamada por Referência

Formalmente, C apenas suporta passagem de parâmetros por valor, mas pode-se simular

a chamada por referência passando ponteiros como parâmetros para funções. Usando

esta aproximação, uma função obtém uma cópia privada de um ponteiro para cada

parâmetro do ambiente chamador.

Exemplo: para entender como isto funciona, primeiro considere a função troca_errada na

figura baixo, que ilustra uma implementação incorreta de troca de dois inteiros usando

passagem de parâmetros pela chamada por valor.

Saída do programa que usa a função troca_errada:

Como pode ser observado na saída do programa, não houve a troca dos valores, pois

como a passagem de parâmetros foi por valor, a troca de valores ocorreu apenas dentro

da função troca_errada e não foi retornada para o programa chamador, o qual continuou

com os mesmos valores iniciais, ou seja, a função troca_errada recebe os valores da

variáveis a e b (argumentos) e não o endereço das mesmas, pois a função troca_errada

não está usando ponteiros como parâmetros. Então, os valores foram trocados apenas

nas variáveis locais x e y da função troca_errada e, quando a função troca_errada

retorna, os valores das variáveis a e b são os mesmos que estavam, inicialmente, em

suas posições de memória.

Refazendo o exemplo acima com chamada de parâmetros por referência usando

ponteiros, tem-se a resposta esperada, o programa e sua saída estão nas figuras abaixo:

Saída do porgrama com a função troca, agora usada corretamente com ponteiros.

Como pode ser visto na saída do programa acima, a função troca recebeu como

argumentos o endereço de duas variáveis (&a e &b) e, utilizando a variável temporária

tmp fez a troca dos valores, através de uma chamada a função troca com passagem de

parâmetros por referência, ou seja, as variáveis não são diretamente passadas como

argumentos para a função troca (isso geraria um erro em tempo de compilação), mas são

passados os endereços dessas variáveis, os quais são armazenados nos respectivos

ponteiros, os quais trocam os valores das posições de memória das variáveis a e b.

Outro uso de ponteiros é quando passamos arrays (vetores e matrizes) para funções. C

trata todos nomes de arrays transparentemente como ponteiros não modificáveis. Por

exemplo, se passarmos um array de objetos do tipo T para uma função, será equivalente

a passar um ponteiro para o objeto T.

Exemplo: O programa seguinte tem uma matriz 2x2 e usa a função funcao_array_soma2 para somar 2 a cada valor da matriz e, após imprime os novos valores na tela.

A saída do exemplo acima fica da forma abaixo:

Como pode ser observado, C não exige que seja passado o número de linhas para uma

função quando ela recebe uma matriz de duas dimensões, a mesma coisa acontece para

vetores (arrays unidimensionais), ou seja, a função que recebe um vetor como argumento,

não precisa de sua dimensão, como mostrado abaixo:

A saída do exemplo acima é a seguinte:

Como pode ser observado, C não verifica os limites do vetor e isso fica a cargo do programador!Agora, veja como fica o exemplo acima da soma dos elementos do vetor, sendo que agora é usado ponteiros.

A saída do exemplo com ponteiros é a seguinte:

A figura a seguir dá uma explicação ilustrativa de como um array multidimensional (matriz) é alocado na memória em C. O array tem 3 (três) linhas e 2 (duas) colunas.

Figura 4. Representação conceitual de uma matriz 3x2 e representação da mesma na memória.

Como pode ser observado, a matriz 3x2 é armazenada na memória linha após linha,

pode-se verificar isso, através dos índices que apontam cada posição na memória.

4. Alocação de Espaço de ArmazenamentoQuando um ponteiro é declarado em C, uma certa quantidade de memória é reservada

para ele e, geralmente ocupam uma palavra (word) de máquina, mas seu tamanho pode

variar. Portanto, para casos de portabilidade, nunca devemos assumir que um ponteiro

tem um tamanho específico, pois frequentemente variam de tamanho devido as definições

do compilador e especificadores de tipo permitidos por certas implementações de C.

É importante salientar que quando um ponteiro é declarado, somente espaço (memória)

para ele é alocado, mas nenhum espaço é alocado para os dados que o ponteiro aponta.

Há dois modos de alocar espaço para os dados: pela declaração de uma variável para

isto ou pela alocação dinâmica de espaço em tempo de execução (usando as funções

calloc, malloc e realloc).

Quando declaramos uma variável, seu tipo diz ao compilador quanto de armazenamento

reservar para ela conforme o programa executa.

Armazenamento (espaço de memória) para as variáveis é alocado dinâmicamente.

Essas vantagens de C, permitem que o programador trabalhe diretamente com o

gerenciamento de memória. Dependendo do projeto, o espaço necessário para

armazenar uma quantidade de dados pode ser variável. Para isso, o C fornece algumas

funções para alocar/desalocar memória dinamicamente. Muitos programadores ignoram o

fato de que o gerenciamento de memória deve ser feito com muito cuidado. E se o

tamanho da memória for muito limitado, esta pode se esgotar em algum ponto durante a

execução do programa.

A alocação dinâmica permite ao programador alocar memória para variáveis quando o

programa está sendo executado. Assim, pode-se definir, por exemplo, um vetor ou uma

matriz cujo tamanho descobre-se em tempo de execução.

O padrão C ANSI define apenas 4 (quatro) funções para o sistema de alocação dinâmica,

disponíveis na biblioteca stdlib.h.

4.1 Alocação Dinâmica com malloc

A função malloc serve para alocar memória e tem o seguinte protótipo:

void *malloc (unsigned int num);

A função toma o número de bytes que queremos alocar num, aloca na memória e retorna

um ponteiro void * para o primeiro byte alocado. O ponteiro void * pode ser atribuído a

qualquer tipo de ponteiro. Se não houver memória suficiente para alocar a memória

requisitada a função malloc() retorna um ponteiro nulo. Ou seja, Aloca n bytes

consecutivos na memória e retorna o endereço da região alocada. Se não for possível

alocar, retorna NULL. Como a função malloc retorna um ponteiro void (sem tipo) é

necessário tipar o ponteiro alocado dinamicamente usando um cast.

Exemplo: Faça um programa que utilize a função malloc(), sendo que deve ser passado

um valor inteiro para que o programa saiba quanto de espaço deve ser alocado

dinâmicamente e, após em cada posição do vetor coloque o valor do índice multiplicado

por ele mesmo e apresente na tela.

Saída do Exemplo:

No exemplo acima, é alocada memória suficiente para se armazenar a números inteiros.

O operador sizeof() retorna o número de bytes de um inteiro. Ele é util para se saber o

tamanho de tipos. O ponteiro void* que malloc() retorna é convertido para um int* pelo

cast (muda uma variável de um tipo para outro) e é atribuído a p. A declaração seguinte

testa se a operação foi bem sucedida. Se não tiver sido, p terá um valor nulo, o que fará

com que !p retorne verdadeiro. Se a operação tiver sido bem sucedida, pode-se usar o

vetor de inteiros alocados normalmente, por exemplo, indexando-o de p[0] a p[(a-1)].

4.2 Alocação Dinâmica com calloc

A função calloc() também serve para alocar memória, mas possui um protótipo um pouco

diferente:

void *calloc (unsigned int num, unsigned int size);

A função aloca uma quantidade de memória igual a num * size, isto é, aloca memória

suficiente para um vetor de num objetos de tamanho size. Retorna um ponteiro void * para

o primeiro byte alocado. O ponteiro void * pode ser atribuído a qualquer tipo de ponteiro.

Se não houver memória suficiente para alocar a memória requisitada, a função calloc()

retorna um ponteiro nulo. Em relação a malloc, calloc tem uma diferença (além do fato de

ter protótipo diferente): calloc inicializa o espaço alocado com 0. Ou seja, Aloca n

elementos de t bytes na memória, inicializa todos os bits da região com zero e retorna o

endereço da região alocada. Se não for possível alocar, retorna NULL.

Exemplo: Refaça o exemplo acima usando calloc().

A saída do exemplo acima é:

No exemplo acima, é alocada memória suficiente para se colocar a números inteiros. O

operador sizeof() retorna o número de bytes de um inteiro. Ele é util para se saber o

tamanho de tipos. O ponteiro void * que calloc() retorna é convertido para um int * pelo

cast e é atribuído a p. A declaração seguinte testa se a operação foi bem sucedida. Se

não tiver sido, p terá um valor nulo, o que fará com que !p retorne verdadeiro. Se a

operação tiver sido bem sucedida, podemos usar o vetor de inteiros alocados

normalmente, por exemplo, indexando-o de p[0] a p[(a-1)].

4.3 Alocação Dinâmica com realloc

A função realloc() serve para realocar memória e tem o seguinte protótipo:

void *realloc (void *ptr, unsigned int num);

A função modifica o tamanho da memória previamente alocada apontada por *ptr para

aquele especificado por num. O valor de num pode ser maior ou menor que o original. Um

ponteiro para o bloco é devolvido porque realloc() pode precisar mover o bloco para

aumentar seu tamanho. Se isso ocorrer, o conteúdo do bloco antigo é copiado no novo

bloco, e nenhuma informação é perdida. Se ptr for nulo, aloca num bytes e devolve um

ponteiro; se num é zero, a memória apontada por ptr é liberada. Se não houver memória

suficiente para a alocação, um ponteiro nulo é devolvido e o bloco original é deixado

inalterado. Ou seja, Altera o tamanho do bloco apontado para n bytes e retorna o

endereço da região alocada. Se não for possível alocar, retorna NULL e o bloco não é

alterado.

Exemplo: Faça um programa que aloque 4 (quatro) números inteiros e imprima-os na tela

e depois realoque 16 números inteiros e utilize a seguinte equação para calcular o valor

das posições a x i x ( i – 6).

A saída do exemplo acima é:

Como pode ser observado, primeiramente, foi usada a função malloc para alocar um vetor

de inteiros de tamanho e, após imprimir esse vetor, houve uma realocação dinâmica do

mesmo vetor, mas agora para um espaço para 16 inteiros, o qual também é mostrado na

tela.

4.3 Free

Quando alocamos memória dinamicamente é necessário que nós a liberemos quando ela

não for mais necessária. Para isto existe a função free() cujo protótipo é:

void free (void *p);

Basta então passar para free() o ponteiro que aponta para o início da memória alocada.

Mas você pode se perguntar: como é que o programa vai saber quantos bytes devem ser

liberados? Ele sabe pois quando você alocou a memória, ele guardou o número de bytes

alocados numa tabela de alocação interna. Ou seja, recebe um ponteiro para uma região

alocada e desaloca.

Exemplo: supondo-se que você queira alocar certa quantidade de memória durante a

execução de seu aplicativo. Você pode chamar a função malloc a qualquer momento e ela

solicitará um bloco de memória da pilha. O sistema operacional reservará um bloco de

memória para seu programa e você poderá usá-lo da maneira que quiser. Quando você

termina de usar o bloco, você o retorna ao sistema operacional para reciclagem,

invocando a função free. Depois, os outros aplicativos podem reservá-lo para seu próprio

uso. O código a seguir demonstra o uso mais simples possível da pilha:

Saída do exemplo:

A primeira linha neste programa invoca a função malloc. Esta função faz três

coisas:

1. Primeiro, a instrução malloc analisa a quantidade de memória disponível na pilha e

pergunta: “Há memória suficiente disponível para alocar um bloco de memória do

tamanho solicitado?". A quantidade de memória necessária para o bloco é

conhecida a partir do parâmetro passado em malloc - neste caso, sizeof(int) é 4

bytes. Se não houver memória suficiente disponível, a função malloc retorna o

endereço zero para indicar o erro (outro nome para zero é NULL e você verá que

ele é usado por todo o código C). Caso contrário, a função malloc prossegue;

2. Se houver memória disponível na pilha, o sistema "aloca" ou "reserva" um bloco da

pilha do tamanho especificado. O sistema reserva o bloco de memória de forma

que ele não seja usado acidentalmente por mais de uma instrução malloc;

3. O sistema então coloca na variável do ponteiro (neste caso, p) o endereço do bloco

reservado. A própria variável do ponteiro contém um endereço. O bloco alocado é

capaz de manter um valor do tipo especificado e o ponteiro aponta para ele.

O seguinte diagrama mostra o estado de memória depois de executar malloc:

Figura 5. O bloco à direita é o bloco de memória malloc alocada.

O programa então verifica o ponteiro para garantir que a solicitação de alocação ocorreu

com a linha if (p == 0) (que também poderia ter sido escrita como if (p == NULL) ou

mesmo if (!p). Em caso de falha da alocação (se p for zero) o programa encerra. Em caso

de êxito na alocação, o programa inicializa o bloco com o valor 5, imprime o valor e

executa a função free para retornar a memória à pilha antes do programa encerrar. Duas

dúvidas comuns:

• É mesmo importante verificar se o ponteiro é zero após cada alocação? Sim.

Como a pilha varia de tamanho constantemente, dependendo dos programas em

execução e quantidade de memória que alocaram, etc., não há garantias de que

uma invocação de malloc será bem sucedida. Você deve verificar o ponteiro depois

de qualquer chamada a malloc para conferir se o ponteiro é válido.

• O que acontece se eu esquecer de apagar um bloco de memória antes que o

programa encerre? Quando um programa encerra, o sistema operacional "faz a

limpeza" depois do encerramento, liberando o espaço de código executável, pilha,

espaço de memória global e qualquer alocação de pilha para reciclagem. Assim,

não há conseqüências de longo prazo em deixar as alocações pendentes no

término do programa. Todavia, é considerada uma forma inadequada e os

"vazamentos de memória" durante a execução de um programa são prejudiciais.

Exemplo: Faça um programa que aloque em tempo de execução um vetor de tamanho

digitado pelo usuário e guarde elementos do tipo inteiro, também digitados pelo usuário.

Depois, apresente o vetor na tela.

A saída do exemplo:

Exemplo: refazendo o exemplo anterior usando calloc.

A saída do exemplo:

Exemplo: Aloque a quantidade de memória suficiente para armazenar e mostrar na tela o nome Andre e, depois realoque para armazenar e mostrar na tela o nome Andre Mendes da Rosa. Depois libere a memória, ou seja, desaloque.

A saída do exemplo é a seguinte: