A0405 - Alocação de Memória

Prévia do material em texto

Alocação de memória
ESTRUTURA DE DADOS
Objetivos de Aprendizagem
 Descrever o procedimento de aplicação 
de memória estática;
 Analisar diferentes procedimentos de 
alocação estática de memória em 
estruturas de dados;
 Projetar estruturas de dados em 
determinada linguagens de programação 
com alocação estática de memória;
Objetivos de Aprendizagem
 Descrever o procedimento de alocação 
de memória dinâmica;
 Analisar diferentes procedimentos de 
alocação dinâmica de memória em 
estruturas de dados;
 Projetar estruturas de dados em 
determinada linguagem de programação 
com alocação.
Agenda
 Mapa de memória da Linguagem C
 Alocação de Memória
◦ Estática x Dinâmica
◦ Sequencial x Encadeada
◦ Estática e Sequencial
◦ Estática e Encadeada
◦ Dinâmica e Sequencial
◦ Dinâmica e Encadeada
 Alocando memória em C.
Mapa de Memória da Linguagem C
Mapa Conceitual de memória
Fonte: http://diegofatec.xpg.uol.com.br/dados/apostilando_c.pdf
Mapa de Memória da Linguagem C
 Região Pilha
◦ Possui endereço de retorno das chamadas das 
funções;
◦ Argumentos para funções e variáveis locais;
◦ Guarda o estado atual da UCP.
Mapa de Memória da Linguagem C
 A heap é uma região de memória livre 
usada pelos programadores, via funções 
de alocação dinâmica de C, em aplicações 
como listas encadeadas e árvores
 Região Variáveis Globais
É aquela em que as variáveis globais 
estão armazenadas
 Região Código do Programa
É a memória que contém o código do 
seu programa (Herbert Schildt)
Memória
 Necessidade para executar um programa;
 Solicitação ao Sistema Operacional;
 Memória alocada na iniciação do 
programa;
 Memória alocada durante a sua execução.
Alocação de Memória
Estática vs. Dinâmica
 Estática
◦ Quantidade total de memória utilizada pelos 
dados é previamente conhecida e 
definida de modo imutável, no próprio 
código-fonte do programa
◦ Durante toda a execução do programa a 
quantidade de memória não varia
Alocação estática
 Na alocação estática o espaço de 
memória, que as variáveis irão utilizar 
durante a execução do programa, é 
definido no processo de compilação.
 Não sendo possível alterar o tamanho 
desse espaço durante a execução do 
programa. 
Alocação estática
 char a; // 1 byte na memoria
 int vetor[10]; /* O int ocupa 4 bytes na 
memória, portanto 4x10=40 bytes */
 double matriz[3][3]; /* O double ocupa 8 
bytes na memória, portanto 3x3x8=72 
bytes */
Estática vs. Dinâmica
 Estática
◦ Vantagem:
 Mantém os dados organizados na memória
◦ Desvantagem:
 Desperdício de memória
 Limitação de memória
Estática vs. Dinâmica
 Dinâmica
◦ É capaz de criar novas variáveis enquanto 
executa, ou seja, em tempo de execução (run
time)
◦ As práticas mais usadas desse tipo de 
alocação são: 
 Alocação das variáveis locais
 E parâmetros passados por valor
Sequencial x Encadeada
 Sequencial
◦ Consiste em alocar os itens nas células de 
memória consecutiva
Sequencial x Encadeada
 Vantagens
◦ Fácil endereçamento
 Item pode ser alcançado de uma forma direta
 Desvantagens
◦ Manutenabilidade difícil
 Há dificuldades para inserir e remover itens após 
criação do array
Sequencial x Encadeada 
 Encadeada
◦ Os itens alocados podem ocupar qualquer 
endereço na memória
◦ Para preservar a forma linear é armazenado o 
endereço da próxima estrutura junto com 
cada item alocado
Sequencial x Encadeada 
 Encadeada
◦ A estrutura deve possuir pelo menos dois 
campos:
 Um com os dados do item
 E outro com o endereço da próxima estrutura
Sequencial x Encadeada 
 Encadeada
◦ Vantagem:
 Facilidade na inserção e retirada dos itens na lista
◦ Desvantagem:
 Menor velocidade de acesso
 pois precisamos partir do primeiro item da fila para seguir 
os campos de ligação
Alocação Estática e Sequencial
 A forma mais natural de armazenar um 
conjunto de dados, com quantidade de 
elementos pré-determinada, consiste em 
colocar os elementos em células de 
memórias consecutivas, um após o outro
Alocação Estática e Sequencial
 Assim, se cada célula tem um endereço único ᵋ e utiliza k
bytes, temos:
◦ Endereço do elemento ai = ᵋ
◦ Endereço do elemento ai - 1 = ᵋ - k
◦ Endereço do elemento ai + 1 = ᵋ + k
Alocação Estática e Sequencial
 Implementação
◦ Há duas formas de implementar, em C, a alocação estática e 
sequencial:
 Através das variáveis globais ou dos ponteiros
◦ O importante é que ambas as formas devem fixar o tamanho 
do array.
Alocação Estática e Sequencial
 Exemplo de uma alocação estática usando variáveis globais
Alocação Estática e Sequencial
 Exemplo de uma alocação estática usando variáveis globais
Alocação Estática e Sequencial
 Exemplo de uma alocação estática usando ponteiros
Alocação Estática e Sequencial
 Exemplo de uma alocação estática usando ponteiros
Alocação Estática e Sequencial
 Exemplo de uma alocação estática usando malloc
Alocação Estática e Sequencial
 Exemplo de uma alocação estática usando malloc
Alocação Estática e Encadeada
 As listas estáticas são armazenadas como 
vetores
 tem seu tamanho SEMPRE fixo
 E as operações de inserção podem ser de 
dois tipos: 
◦ desordenada e ordenada
Alocação Estática e Encadeada
 Na forma estática sequencial, ordenar significa movimentar os 
elementos para os espaços livre na extremidade
Alocação Estática e Encadeada
 Realizar inserções numa estrutura de dados onde os 
elementos podem estar fisicamente desordenados, mas 
estarão logicamente ordenados
Alocação Estática e Encadeada
 Passo a Passo da inserção na lista estática e encadeada
Alocação Estática e Encadeada
Alocação Estática e Encadeada
Alocação Estática e Encadeada
Alocação Estática e Encadeada
Alocação Dinâmica e Sequencial
 Ao se tratar de realizar uma alocação que altera a 
quantidade de elementos durante o tempo de 
execução, e ao mesmo tempo trabalha em uma 
memória consecutiva, ou seja, memória sequencial, 
estamos nos referindo aos arrays dinâmicos
Alocação Dinâmica e Sequencial
Alocação Dinâmica e Encadeada
 Esse tipo de alocação gera estruturas de 
dados bastantes utilizadas e com grande 
poder de armazenamento e manipulação:
◦ Listas encadeadas
◦ Filas
◦ Pilhas
◦ Deques
◦ Árvores 
◦ Grafos
Alocação Dinâmica e Encadeada
 A vantagem de usar esse tipo de alocação 
está no fato de a qualquer momento que 
precisarmos de espaço em memória 
poderemos alocar de maneira simples e 
rápida
Alocação Dinâmica e Encadeada
 Características que devem ser 
observadas:
◦ Os dados estão espalhados no computador 
em vários blocos;
◦ Utiliza-se registros como estrutura de dados
 Esta por sua vez incluem um campo do tipo 
ponteiro (link), para permitir encadear os dados e 
indicar onde está o dado seguinte na memória 
(encadeando);
Alocação Dinâmica e Encadeada
 Características que devem ser 
observadas:
◦ Espaços são criados conforme a necessidade 
em tempo de execução
 Permitindo criar programas que utilize apenas 
memórias necessárias;
◦ Podemos liberar espaço de memória quando 
estes não forem mais necessários pelos 
programas
Alocação Dinâmica e Encadeada
 Memória Suficiente
◦ O primeiro passo a ser verificado nesse tipo 
de alocação, é o de memória suficiente
Alocação Dinâmica e Encadeada
 A figura mostra uma estrutura criada com 
registros que são encadeados através do 
uso de ponteiros Estes blocos espalhados pela memória, 
vão resultar em estruturas denominadas 
de listas encadeadas
Alocação de Memória
 Ex: Armazenando 10 elementos inteiros
int *v
v = (int *) malloc(10*sizeof(int));
if(v==NULL){
printf(“Memória insuficiente”);
/*aborta o programa e retorna 1 para o sist. operacional*/ 
exit(1); 
}
/*libera o espaço de memória alocado dinamicamente*/
free(v); 
Alocação de Memória
 Vale salientar...
◦ Vetores estáticos tendem a ser mais eficientes do que os 
dinâmicos, já que estes têm uma indireção a mais -
primeiro acessa o valor do endereço armazenado na 
variável ponteiro para então acessar o elemento do 
vetor
(CELES, W., CERQUEIRA, R., RANGEL, J.L.)
Alocação de Memória
 Vetores Bidimensionais – matrizes
float mat[4][3];
 Armazenamento contínuo...
 float mat[4][3] = {{5.0,10.0,15.0},
{20.0,25.0,30.0},
{35.0,40.0,45.0},
{50.0,55.0,60.0}}
Alocação de Memória
 Armazenamento contínuo...
5.0,10.0,15.0
20.0,25.0,30.0
35.0,40.0,45.0
50.0,55.0,60.0
j
i
60.0
55.0
50.0
45.0
40.0
35.0
30.0
25.0
20.0
15.0
10.0
5.0
Vetor-linha
Contém a mesma limitação dos vetores
Alocação de Memória
 Matrizes Dinâmicas
◦ Para trabalhar com matrizes alocadas 
dinamicamente, temos que criar abstrações 
conceituais com vetores:
1. Matriz representada por um vetor simples
2. Matriz representada por um vetor de 
ponteiros
Alocação de Memória
 Matriz representada por um vetor 
simples
a b c d
e f g h
i j k l
j = 2
i = 1
a b c d e f g h i j k 
l
•Acesso ao elemento:
•mat[i*n+j], onde n é o 
número de colunas
float *mat;
...
mat = (float*) malloc(m*n*sizeof(float));
Alocação de Memória
 Matriz representada por um vetor de 
ponteiros
◦ A matriz é representada por um vetor de 
vetores, ou vetor de ponteiros, no qual cada 
elemento armazena o endereço do primeiro 
elemento de cada linha
int i;
/*matriz representada por um vetor de ponteiros*/
float **mat; 
...
mat = (float**) malloc(m*sizeof(float*));
for(i=0; i<m; i++)
mat[i] = (float*) malloc(n*sizeof(float));
Alocação de Memória
 Matriz representada por um vetor 
de ponteiros
a b c d
e f g h
i j k l
j = 2
i = 1
a b c d
e f g h
i j k l
i = 1
j = 2
Alocando memória em C
Linguagem C
 O padrão C ANSI define 4 funções para o 
sistema de alocação dinâmica, disponíveis 
na biblioteca stdlib.h
 malloc
 calloc
 realloc
 free
Linguagem C - 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;
Linguagem C - malloc
 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 
Linguagem C - malloc
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]){
int *p, a=4, i;
//Alocando memoria a numeros inteiros
p = (int *) malloc(a*sizeof(int)); 
//p pode ser tratado como um vetor com a posicoes
if(!p){ //se nao exite p
printf("ERRO: Memória Insuficiente!!");
exit;
}
system("PAUSE"); return 0;
}
Calcula o tamanho do 
inteiro conforme a 
plaforma de HW
Linguagem C - 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. 
 Ela zera toda espaço alocado. Zerar significa colocar o 
byte 0 em todas posições de memória alocadas.
Linguagem C - calloc
 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 
 calloc() é como chamar malloc() e memset()
Linguagem C - calloc
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]){
int *p, a=4, i;
//Alocando memoria a numeros inteiros
p = (int *) calloc(a, sizeof(int)); 
//p pode ser tratado como um vetor com a posicoes
if(!p){ //se nao exite p
printf("ERRO: Memória Insuficiente!!");
exit;
}
system("PAUSE"); return 0;
}
Calcula o tamanho do 
inteiro conforme a 
plaforma de HW
Linguagem C – realloc
 A função realloc
void * realloc (void *ptr, unsigned int num);
 A função realloc serve para realocar memória
 A função modifica o tamanho da memória 
previamente alocada apontada por *ptr para o 
tamanho num
 O valor de num pode ser maior ou menor do que o 
tamanho original
 A memória apontada pelo ptr deve ter sido alocada 
por malloc ou calloc
Linguagem C – realloc
 Um ponteiro para o bloco é devolvido porque 
realloc() pode precisar mover o bloco para 
aumentar seu tamanho
◦ Se isso ocorre, o conteúdo do bloco antigo é copiado no 
novo bloco e nenhuma informação é perdida
 Se o ponteiro 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 
Linguagem C – realloc
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]){
int *p, a=30, i;
//Alocando memoria a numeros inteiros
p = (int *) malloc(a*sizeof(int)); 
//p pode ser tratado como um vetor com a posicoes
if(!p){ //se nao exite p
printf("ERRO: Memória Insuficiente!!");
exit;
}
...
Linguagem C – realloc
for (i=0; i<a ; i++)
p[i] = i*i;
//O tamanho de p deve ser modificado, por algum 
motivo
a = 100;
p = realloc (p, a*sizeof(int));
for (i=0; i<a ; i++) 
p[i] = a*i*(i-6);
system("PAUSE"); return 0;
}
 O programa guarda o número de bytes 
alocados numa “tabela de alocação”
interna
Linguagem C – realloc
Como o programa sabe a quantidade de bytes 
que devem ser liberados?
Linguagem C – free
 free()
◦ Quando alocamos memória dinâmica é necessário 
que nós a liberemos quando ela não for mais 
necessária
void free (void *p);
◦ Basta passar para free() o ponteiro que aponta 
para o início da memória alocada
...
int main(int argc, char *argv[]){
int *p, a=30, i; 
//Alocando memoria a numeros inteiros
p = (int *) malloc(a, sizeof(int)); 
//p pode ser tratado como um vetor com a posicoes
if(!p){ //se nao exite p
printf("ERRO: Memória Insuficiente!!");
exit;
}
...
free(p);
...
return 0
}
Linguagem C – free
Alocação de memória
ESTRUTURA DE DADOS