Estruturas de Dados - T.332
Capítulo 3
Parte 2:
Alocação Dinâmica de Memória
Transparência 1
3.1 As Funções de Alocação Dinâmica de
Memória em "C"


Alocação Dinâmica é um meio pelo qual o
programa pode obter memória enquanto está em
execução.
Já visto até agora:
são "codificadas" dentro do código objeto
de um programa em tempo de compilação.
 Variáveis globais (estáticas) têm a sua alocação
codificada em tempo de compilação e são alocadas
logo que um programa inicia a execução.
 Variáveis locais em funções (ou métodos) são
alocadas através da requisição de espaço na pilha
(stack).
 Constantes
Transparência 2

Programa:
#include <stdio.h>
char *a, *b;
Topo da Memória
HeapPointer
Início da Área
Alocável
Variáveis estáticas
Código objeto
Constantes
a
b
10010101...
"Essa aula é ...
"Será mesmo..
Programa
int func_A ()
{
int local1, local2;
- - }
void func_B ()
{
int localA, localB;
localA = func_A();
localB = func_A();
}
main ()
{
a = "Essa aula é legal";
b = "Será mesmo?"
func_B();
}
StackPointer
Inicio da Pilha
Sist.Operacional
Base da Memória
Transparência 3

Programa:
#include <stdio.h>
char *a, *b;
int func_A ()
{
int local1, local2;
- - }
void func_B ()
{
int localA, localB;
localA = func_A();
localB = func_A();
}
main ()
{
a = "Essa aula é legal";
b = "Será mesmo?"
func_B();
}
StackPointer
Inicio da Pilha
Topo da Memória
HeapPointer
Início da Área
Alocável
Variáveis estáticas
Código objeto
Constantes
a
b
10010101...
"Essa aula é ...
"Será mesmo..
Sist.Operacional
Base da Memória
Transparência 4

Programa:
#include <stdio.h>
char *a, *b;
int func_A ()
{
int local1, local2;
- - }
void func_B ()
{
int localA, localB;
localA = func_A();
localB = func_A();
}
main ()
{
a = "Essa aula é legal";
b = "Será mesmo?"
func_B();
}
StackPointer
Topo da Pilha
Topo da Memória
HeapPointer
Topo da Área
Alocável
Variáveis estáticas
Código objeto
Constantes
a
b
10010101...
"Essa aula é ...
"Será mesmo..
Sist.Operacional
Base da Memória
Transparência 5

Programa:
#include <stdio.h>
char *a, *b;
int func_A ()
{
int local1, local2;
- - }
void func_B ()
{
int localA, localB;
localA = func_A();
localB = func_A();
}
main ()
{
a = "Essa aula é legal";
b = "Será mesmo?"
func_B();
}
Topo da Memória
StackPointer
Topo da Pilha
&main-#3
localA
localB
HeapPointer
Topo da Área
Alocável
Variáveis estáticas
Código objeto
Constantes
a
b
10010101...
"Essa aula é ...
"Será mesmo..
Sist.Operacional
Base da Memória
Transparência 6

Programa:
#include <stdio.h>
char *a, *b;
int func_A ()
{
int local1, local2;
- - }
void func_B ()
{
int localA, localB;
localA = func_A();
localB = func_A();
}
main ()
{
a = "Essa aula é legal";
b = "Será mesmo?"
func_B();
}
Topo da Memória
StackPointer
Topo da Pilha
&main-#3
localA
localB
HeapPointer
Topo da Área
Alocável
Variáveis estáticas
Código objeto
Constantes
a
b
10010101...
"Essa aula é ...
"Será mesmo..
Sist.Operacional
Base da Memória
Transparência 7

Programa:
Topo da Memória
#include <stdio.h>
char *a, *b;
int func_A ()
{
int local1, local2;
- - }
void func_B ()
{
int localA, localB;
localA = func_A();
localB = func_A();
}
main ()
{
a = "Essa aula é legal";
b = "Será mesmo?"
func_B();
}
StackPointer
Topo da Pilha
&main-#3
localA
localB
&func_B-#2
local1
local2
HeapPointer
Topo da Área
Alocável
Variáveis estáticas
Código objeto
Constantes
a
b
10010101...
"Essa aula é ...
"Será mesmo..
Sist.Operacional
Base da Memória
Transparência 8

Programa:
Topo da Memória
#include <stdio.h>
char *a, *b;
int func_A ()
{
int local1, local2;
- - }
void func_B ()
{
int localA, localB;
localA = func_A();
localB = func_A();
}
main ()
{
a = "Essa aula é legal";
b = "Será mesmo?"
func_B();
}
StackPointer
Topo da Pilha
&main-#3
localA
localB
&func_B-#2
local1
local2
HeapPointer
Topo da Área
Alocável
Variáveis estáticas
Código objeto
Constantes
a
b
10010101...
"Essa aula é ...
"Será mesmo..
Sist.Operacional
Base da Memória
Transparência 9

Programa:
#include <stdio.h>
char *a, *b;
int func_A ()
{
int local1, local2;
- - }
void func_B ()
{
int localA, localB;
localA = func_A();
localB = func_A();
}
main ()
{
a = "Essa aula é legal";
b = "Será mesmo?"
func_B();
}
Topo da Memória
StackPointer
Topo da Pilha
&main-#3
localA
localB
HeapPointer
Topo da Área
Alocável
Variáveis estáticas
Código objeto
Constantes
a
b
10010101...
"Essa aula é ...
"Será mesmo..
Sist.Operacional
Base da Memória
Transparência 10

Programa:
Topo da Memória
#include <stdio.h>
char *a, *b;
int func_A ()
{
int local1, local2;
- - }
void func_B ()
{
int localA, localB;
localA = func_A();
localB = func_A();
}
main ()
{
a = "Essa aula é legal";
b = "Será mesmo?"
func_B();
}
StackPointer
Topo da Pilha
&main-#3
localA
localB
&func_B-#3
local1
local2
HeapPointer
Topo da Área
Alocável
Variáveis estáticas
Código objeto
Constantes
a
b
10010101...
"Essa aula é ...
"Será mesmo..
Sist.Operacional
Base da Memória
Transparência 11

Programa:
Topo da Memória
#include <stdio.h>
char *a, *b;
int func_A ()
{
int local1, local2;
- - }
void func_B ()
{
int localA, localB;
localA = func_A();
localB = func_A();
}
main ()
{
a = "Essa aula é legal";
b = "Será mesmo?"
func_B();
}
StackPointer
Topo da Pilha
&main-#3
localA
localB
&func_B-#2
local1
local2
HeapPointer
Topo da Área
Alocável
Variáveis estáticas
Código objeto
Constantes
a
b
10010101...
"Essa aula é ...
"Será mesmo..
Sist.Operacional
Base da Memória
Transparência 12

Programa:
#include <stdio.h>
char *a, *b;
int func_A ()
{
int local1, local2;
- - }
void func_B ()
{
int localA, localB;
localA = func_A();
localB = func_A();
}
main ()
{
a = "Essa aula é legal";
b = "Será mesmo?"
func_B();
}
Topo da Memória
StackPointer
Topo da Pilha
&main-#3
localA
localB
HeapPointer
Topo da Área
Alocável
Variáveis estáticas
Código objeto
Constantes
a
b
10010101...
"Essa aula é ...
"Será mesmo..
Sist.Operacional
Base da Memória
Transparência 13

Programa:
#include <stdio.h>
char *a, *b;
int func_A ()
{
int local1, local2;
- - }
void func_B ()
{
int localA, localB;
localA = func_A();
localB = func_A();
}
main ()
{
a = "Essa aula é legal";
b = "Será mesmo?"
func_B();
}
StackPointer
Topo da Pilha
Topo da Memória
HeapPointer
Topo da Área
Alocável
Variáveis estáticas
Código objeto
Constantes
a
b
10010101...
"Essa aula é ...
"Será mesmo..
Sist.Operacional
Base da Memória
Transparência 14
Alocação Dinâmica em "C"

A memória alocada pelas funções de alocação
dinâmica é obtida do heap.
O
heap é a região de memória livre que se encontra
entre o programa (com a área de armazenamento
permanente) e a pilha (stack).
 O tamanho do heap é, a princípio, desconhecido do
programa.

"C" possui duas funções básicas para gerência de
memória:

malloc(nº de bytes) - aloca memória.

free(endereço) - libera memória
Transparência 15
Função malloc():

Protótipo:
void *malloc(size_t número_de_bytes);

Detalhes :
 Devolve
um ponteiro do tipo void (sem tipo) para o início
(1º byte) da área de memória alocada.
 Isto significa que o valor deste ponteiro pode ser atribuído
a qualquer variável do tipo ponteiro.
 Para
isto deve ser utilizado sempre um typecasting.
Ex.: se x é ponteiro para inteiro então explicitar isto com
x = (int *) malloc( sizeof(int) );
 número_de_bytes
é a quantidade de bytes alocada.
 Se
a memória for alocada no topo do heap, o heapPointer
é atualizado (incrementado de número_de_bytes).
 O tipo size_t é definido em stdlib.h.
Transparência 16

Exemplo:
StackPointer
Topo da Pilha
Topo da Memória
#include <stdlib.h>
#include <stdio.h>
char
int
*p;
*q;
main ()
{
p = (char *) malloc(1000);
// Aloca 1000
// bytes de RAM
q = (int *) malloc(50*sizeof(int));
// Aloca espaço
// para 50 inteiros.
}
HeapPointer
Topo da Área
Alocável
50*int = 200 bytes
1000 bytes
Variáveis estáticas
Código objeto
p
q
10010101...
Constantes
Sist.Operacional
Base da Memória
Transparência 17

malloc devolve:



Topo da Memória
um ponteiro para a área alocada
o ponteiro nulo (NULL) caso
não seja possível alocar a
memória requisitada.
Convém verificar se foi possível alocar a memória:
#include <stdio.h>
#include <stdlib.h>
char
*p;
main ()
{ ................
p = malloc(1000)
// Tenta alocar 1000
// bytes de RAM
if (p == NULL)
// Testa se p
// diferente de 0
printf("Sem memória.");
}
Espaço de variáveis
locais alocado
StackPointer
Topo da Pilha
HeapPointer
Topo da Área
Alocável
Já alocado antes
p
Variáveis estáticas
Código objeto
10010101...
Constantes
"Sem memória"
Sist.Operacional
Base da Memória
Transparência 18
Função free:

Protótipo:
void free( void *p );

Detalhes :
 Devolve
memória previamente alocada ao sistema.
 A memória devolvida é aquela que foi alocada com um
ponteiro com o valor de p.
valor de p deve ser um valor que foi alguma vez retornado por
malloc().
 Não é possível alocar-se um vetor enorme e depois dealocar-se a
parte dele que "sobrou".
O
de free() com um valor de ponteiro qualquer
poder ter resultados catastróficos.
 A gerência de buracos no heap é responsabilidade do
sistema operacional.
 A utilização
Transparência 19
Exercício:
Lista com um vetor de Ponteiros para Strings.



Uma lista ordenada pode conter Strings de qualquer
comprimento < 10000.
Esta lista tem número de elementos máximo fixo = 100 e é
implementada como um vetor de ponteiros para Strings.
 Utilize as rotinas de lista com vetor que você utilizou para a
agenda.
Um novo String é lido primeiramente para dentro de uma variável
auxiliar qualquer.
 Então é alocada memória para exatamente o seu tamanho e ele é
copiado para esta área. Para copiar um String utilize strcpy().
 Por fim um lugar na lista é encontrado para ele. A posição
escolhida do vetor de ponteiros da lista é instanciada através da
atualização dos valores do ponteiro da posição do string na lista
com o endereço do string.
Transparência 20
Modelagem da estrutura
Strings lidos
do usuário
e alocados
no Heap
-1
4
3
2
1
0
S a b ã o \0
C o n s t i t u i r \0
Lista com
Vetor de
Ponteiros
Transparência 21
Modelagem da Lista

Pseudo-código:
constantes Maxlista = 100;
tipo Lista {
caracter
inteiro
};

*dados[Maxlista];
“ Vetor de ponteiros para char “
ultimo;
Importante: Observe que criando uma variável do tipo
Lista você não vai estar alocando memória para os strings
a serem lidos, apenas para os ponteiros para eles.
Transparência 22
Topo da Memória

Organização de
memória do
Exercício:
StackPointer
Topo da Pilha
Espaço de variáveis
locais alocado
HeapPointer
Topo da Área
Alocável
str4
str3
str2
str1
Var.Estáticas
Código objeto
10010101...
Constantes
Sist.Operacional
Base da Memória
Transparência 23

Para verificar o comprimento de um String:



Utilize a função strlen().
Esta função devolve o comprimento (em caracteres
imprimíveis) de um String.
Protótipo: int strlen(char *p);
#include <stdio.h>
#include <stdlib.h>
#include <sting.h>
char
p[90] = "Carro";
main ()
{
printf("%i", strlen(p) );
}
Imprime: 5.
Transparência 24

Para copiar um String:



Utilize a função strcpy().
Esta função copia o conteúdo de um string (dado por um
apontador) para a posição de memória dada por outro apontador.
Protótipo:
char *strcpy(char *destino, *fonte);
#include <stdio.h>
#include <stdlib.h>
#include <sting.h>
char
p[90] = "Carro";
char
lata[20];
main ()
{
strcpy(lata, p) );
printf("s%", lata);
}
Imprime: Carro.
Transparência 25
Detalhes:
Lista Ordenada com um vetor de
ponteiros para Strings.





Como você não sabe o comprimento do String que o usuário vai
digitar, use primeiro uma variável auxiliar grande (10000
posições) para guardar o que foi digitado.
A lista deve ser passada como parâmetro para todas as funções
que a utilizam.
Da mesma maneira as variáveis de controle da lista.
Todas as funções de lista ordenada implementadas
anteriormente devem ser reimplementadas para utilizar estes
Strings.
Para a leitura de um String utilize scanf("%s", entrada)
onde char entrada[10000].
Transparência 26
Exercício Nº 2:
Trabalho com Passagem de Parâmetros





Agora você vai fazer um programa que manipula mais de
uma lista.
O programa fará isto com um único conjunto de funções e
passagem das diversas listas como parâmetros.
Como aplicação imaginemos um sistema de contabilidade
simples.
Você vai ter um Plano de Contas constituído por duas
listas: débitos e créditos.
O mesmo conjunto de funções (que você já implementou)
vai poder ser utilizado para isso: você somente precisa
ampliar o conjunto de parâmetros da função para passar
por referência também a lista que você quer alterar.

A passagem de parâmetro da lista deve ser por referência porque
você deseja que as alterações sejam persistentes.
Transparência 27
Modelagem de um Lancamento

Cada lista de débitos ou créditos é constituida de
um lançamento. O lançamento possui:
 Um
valor real (positivo).
 Um nome, por exemplo “pagar proteção à Mafia”

Estrutura:
tipo Lancamento {
caracter
real
};
*nome;
“ponteiro para char alocado no heap“
valor;
Transparência 28
Modelagem de um tipo Lista para
Débitos ou Créditos

Pseudo-código:
constantes Maxlista = 100;
tipo ListaContabil {
Lancamento
dados[Maxlista];
“ Vetor de Estrutura Lançamento “
inteiro
ultimo;
};

Importante: Observe que criando um vetro de lancamentos, você não
vai estar reservando memória para os nomes destes, pois o campo
nome é só ponteiros. Lembre-se de alocar.
Transparência 29
Usando (pseudo código)

Crie variáveis globais:
ListaContabil

debitos, creditos;
Passe estas variáveis como parâmetro por
referência:
adiciona(&debitos, nomeLanc, valorLanc)

Cabeçalho:
Inteiro FUNÇÃO adiciona(ListaContabil *plano;
caracter
*nome;
real
valor)

Importante: nome é passado como ponteiro para caracter.
Use um buffer global para ler o nome do lancamento do
usuário.
Transparência 30
Strings lidos
do usuário
e alocados
no Heap
Desenho
R$ 5,00
-1
4
3
2
1
0
S a b ã o \0
R$ 505,00
P a s s a g e n s \0
Lista de debitos ou
de créditos com Vetor
de Estruturas do tipo
Lançamento
Transparência 31
Usando (código C)

Referencie diferentemente se estiver usando ponteiros
para a lista ou a lista diretamente:
ListaContabil debitos, creditos;
debitos.dados[2].valor = 5.0;
strcpy(debitos.dados[2].nome, buffer);
Dentro das funções:
Suponha: ListaContabil
*ponteiro
e ponteiro = &debitos;
ponteiro->dados[2].valor = 5.0;
strcpy(ponteiro->dados[2].nome, buffer);
Transparência 32
Headerfile: Como Garantir Inclusão Única
/* Arquivo: pilha.h */
#ifndef EstruturaDaPilha
#define EstruturaDaPilha
/* Definir uma estrutura para a pilha */
struct estruturaDaPilha
{
int topo;
int dados[MaxPilha];
};
/* Def. um tipo que tem a estrutura da pilha. */
typedef struct estruturaDaPilha pilha;
#endif
Transparência 33
Headerfiles: Importante




A diretiva de compilação #ifndef (if not defined) diz que
aquela área de código fonte entre o #ifndef e o #endif
somente será levada em conta pelo compilador se o argumento
de #ifndef ainda não houver sido definido na mesma sessão
de compilação no escopo de um módulo.
Isso garante que código que a gente "por via das duvidas"
inclui mais de uma vez em um modulo não seja considerado
duas vezes.
Um exemplo de como isto e útil esta na diretiva #include
<stdio.h> que esta presente tanto em pilha.h como em pilha.c
como em aplic.c.
Como aplic.c carrega pilha.h "para dentro" de si mesmo,
carregara também stdio.h. Como está explicitamente também
carregando stdio.h, se não houver uma diretiva #ifndef em
stdio.h, ele terá o mesmo código existente em stdio.h duas
vezes.
Transparência 34
Projetos de Implementação: Usando Make

Make: Utilitário que auxilia a compilação
de projetos formados por vários arquivos
de programas

Realiza checagem de dependências entre o
arquivo destino e os fontes

Baseia-se nas datas de arquivos
Transparência 35
Projetos de Implementação: Sintaxe do Makefile
aplic: aplic.o pilha.o
gcc -g -o aplic aplic.o pilha.o
aplic.o: aplic.c pilha.h
gcc -g - c aplic.c
pilha.o: pilha.c pilha.h
gcc -g -c pilha.c
meta: dependencia1 dependênciaN
<tab>um comando para atingir meta
<tab>outro comando para atingir meta
Transparência 36
Projetos de Implementação: Usando o Makefile

Chamada:
make -f <nome do Makefile>
 Se
o nome não for dado, make procurará por arquivos
chamados Makefile e makefile, nesta ordem.

Para definir qual meta será a primeira a ser
considerada:
 Se
você não diz nada, a primeira meta será
considerada.
 Voce pode passar como último parâmetro o nome da
meta:
make -f meuMakefile compilar

Todas as dependencias de compilar, se esta meta existir,
serão também levadas em consideração.
Transparência 37

Módulo lista.h:
#ifndef Lista
#define Lista
typedef
char
int
int
};
struct estruLista {
*elemento[30];
ultimo;
max;
typedef struct estruLista lista;
#endif

Módulo lista.c:
#include <stdio.h>
#include <stdlib.h>
#include “lista.h”
lista *criaLista ()
{
lista *nova;
nova = malloc( sizeof(lista) );
nova->max = 30;
nova->ultimo = -1;
return (nova);
}
void destroiLista(lista *morta)
{
// Libera memória p/os strings
for (i=0; morta->ultimo; i++)
free (morta->elemento[i]);
// Libera memória da lista
free ( morta );
}
Transparência 38