Algoritmos e Estruturas de Dados I – Ponteiros
Profa. Mercedes Gonzales Márquez
Alocação estática Até agora, todas as estruturas tinham tamanho pré-definido, exemplo matrizes e vetores. Esta alocação estática pode implicar em:
– desperdício dos recursos pois podemos definirmos um tamanho muito maior que aquele que normalmente será usado em tempo de execução.
– Pode-se, em contraste, subestimar o tamanho necessário para armazenar os dados.
Alocação dinâmica
Na alocação dinâmica os espaços são alocados durante a execução do programa, conforme este necessitar de memória.
Não há reserva antecipada de espaço. Alocar memória dinamicamente significa
gerenciar memória (isto é, reservar, utilizar e liberar espaço) durante o tempo de execução.
Ponteiros ou Apontadores Variáveis que armazenam um endereço de memória. Este
endereço geralmente é ocupado por um dado (variável) de um determinado tipo.
1000 1003
1001
1002
1003
Endereço na
memória
Valor variável
na memória
Ponteiro tem um tipo associado que determina o tipo do dado que ele apontar, ou seja, o tipo da variável alocada no endereço apontado. Pode ser um tipo pré-definido da linguagem ou um tipo definido pelo programador. Exemplo: variáveis inteiras, literais, reais, TipoProduto,etc.
Ponteiros - Declaração A declaração de um tipo ponteiro se faz com a
seguinte sintaxe:
tipo da variável apontada: *ponteiro
Exemplos:Real: *p1
Inteiro: *p2
Literal: *p3
O símbolo * indica que a variável é um ponteiro.
Ponteiros – Referenciando variáveis Um ponteiro pode armazenar o endereço de uma
variável existente. Para isso, utiliza-se o operador ‘&’, que obtém o endereço de uma variável. Exemplo: p ←&x.
Quando um ponteiro contém o endereço de uma variável, dizemos que o ponteiro está “apontando” para essa variável.
Ponteiros – Referenciando variáveis Para acessar o conteúdo apontado pelo ponteiro, é
necessário utilizar o símbolo “*”. Exemplo:
*p ←10 (lê-se o conteúdo do endereço apontado por p recebe 10)
p
Ponteiros – Referenciando variáveis Exemplo: Considere as declarações e inicializações
inteiro: x, y, *p1, *p2
x ← -42
y ← 163 Essas declarações alocam memória para duas variáveis do tipo inteiro e duas do tipo ponteiro a
inteiro. Os seus valores serão armazenados nos endereços de memória indicados no seguinte diagrama.
Ponteiros – Referenciando variáveis Se fizermos:
p1 ← &x
p2 ← &y
Teremos a memória no seguinte estado.
p1 e p2 apontam as variáveis que estão referenciando.
antes depois
Ponteiros – Referenciando variáveis Se fizermos:
*p1 ← 17
muda o valor na variável x devido que é onde p1 aponta. Assim, teremos a seguinte configuração.
Ponteiros – Referenciando variáveis Também é possível atribuir novos valores aos ponteiros. Por exemplo
p1 ← p2
leva ao computador a tomar o valor contido na variável p2 (1004) e copiá-lo na variável p1. Ao copiar este valor em p1, ambos p1 e p2 apontarão à variável y, como mostramos no diagrama:
1004
Ponteiros – Apontando para lixo Após um ponteiro ser declarado e antes que lhe seja
atribuído um valor, ele contém um valor desconhecido. Tentar acessar este valor pode gerar um erro fatal no nosso programa ou até sistema operacional.
Ponteiros – Constanto NULO Para evitar tal situação (apontamento para “Lixo”),
é necessário fazer com que os ponteiros apontem para o vazio, para isso usa-se a constante NULO.
Ponteiros – Alocação dinâmica Alocando espaço na Heap O uso mais importante de ponteiros é para apoio à alocação
dinâmica, isto é, ao invés de apontar variáveis já alocadas do espaço de dados, utilizar o espaço de heap para novas variáveis, que podem ser liberadas após o uso, mesmo antes do término do programa.
Para isso, é necessária uma operação de alocação de memória, e uma para liberação de memória.
Ponteiros – Alocação dinâmica A operação que aloca memória é implementada por uma função,
na forma: aloque(p) Esta operação reserva, na Heap, espaço suficiente para
armazenar um dado do tipo apontado por p. Em p é armazenado o endereço de memória deste dado.
A operação que libera memória é implementada por uma função, na forma: libere(p)
Esta operação ‘retorna’ para a Heap aquele espaço ocupado pelo dado apontado por p, e anula p.
Ponteiros ou Apontadores Após a alocação o ponteiro passará apontar para
uma área definida da memória capaz de armazenar uma variável de determinado tipo.Exemplo:real:*p1inteiro:*p2literal: *p3aloque(p1)aloque (p2)aloque (p3)
Ponteiros ou Apontadores Exemplo 1:
inteiro:*p2aloque(p2)*p2 ←‘ a’ (errado)*p2 ←5 (certo)
Ponteiros ou Apontadores Exemplo 2:
inteiro:*p2*p2 ←5 (erro, o ponteiro não foi alocado)
No seguinte exemplo atribuimos o valor nulo para um ponteiro, a fim de indicar que ainda não foi alocado espaço para ele.
real:*ap1ap1 ←NULO
Ponteiros ou Apontadores
Exemplo 3:inteiro: *p2aloque (p2)*p2 ←5 libere (p2)
Ponteiros ou Apontadores
Exemplo 4:
Inteiro:x, *p,*q
x ← 1
p ← &x
*q ← 3
q ← p
*q ← *p + 1
escreva(*p)
Teste de mesa inicialp x
q
lixo lixo
lixo
Ponteiros ou Apontadores
Exemplo 4:
Inteiro:x, *p,*q
x ← 1
p ← &x
*q ← 3
q ← p
*q ← *p + 1
escreva(*p)
p x
q
lixo 1
lixo
Ponteiros ou Apontadores
Exemplo 4:
Inteiro:x, *p,*q
x ← 1
p ← &x
*q ← 3
q ← p
*q ← *p + 1
escreva(*p)
p x
q
1
lixo
Ponteiros ou Apontadores
Exemplo 4:
Inteiro:x, *p,*q
x ← 1
p ← &x
*q ← 3
q ← p
*q ← *p + 1
escreva(*p)
p x
q
1
lixo
ERRO, q aponta para lixo
Ponteiros ou Apontadores
Exemplo 4:
Inteiro:x, *p,*q
x ← 1
p ← &x
*q ← 3
q ← p
*q ← *p + 1
escreva(*p)
p x
q
1
Ponteiros ou Apontadores
Exemplo 4:
Inteiro:x, *p,*q
x ← 1
p ← &x
*q ← 3
q ← p
*q ← *p + 1
escreva(*p)
p x
q
2
Ponteiros ou Apontadores
Exemplo 4:
Inteiro:x, *p,*q
x ← 1
p ← &x
*q ← 3
q ← p
*q ← *p + 1
escreva(*p)
p x
q
2
Resultado = 2
Ponteiros ou Apontadores
Exemplo 4:
Alocação dinâmica
Inteiro:*p,*q
aloque(p)
*p ← 1
q ← p
*q ← *p + 1
escreva(*p)
libere(p)
Teste de mesa inicialp
q
lixo
lixo
Ponteiros ou Apontadores
Exemplo 4:
Alocação dinâmica
Inteiro:*p,*q
aloque(p)
*p ← 1
q ← p
*q ← *p + 1
escreva(*p)
libere(p)
q
lixo
Ponteiros ou Apontadores
Exemplo 4:
Alocação dinâmica
Inteiro:*p,*q
aloque(p)
*p ← 1
q ← p
*q ← *p + 1
escreva(*p)
libere(p)
q
lixo
Ponteiros ou Apontadores
Exemplo 4:
Alocação dinâmica
Inteiro:*p,*q
aloque(p)
*p ← 1
q ← p
*q ← *p + 1
escreva(*p)
libere(p)
p
q
1
lixo
Ponteiros ou Apontadores
Exemplo 4:
Alocação dinâmica
Inteiro:*p,*q
aloque(p)
*p ← 1
q ← p
*q ← *p + 1
escreva(*p)
libere(p)
q
p
q
1
Ponteiros ou Apontadores
Exemplo 4:
Alocação dinâmica
Inteiro:*p,*q
aloque(p)
*p ← 1
q ← p
*q ← *p + 1
escreva(*p)
libere(p)
q
p
q
2
Ponteiros ou Apontadores
Exemplo 4:
Alocação dinâmica
Inteiro:*p,*q
aloque(p)
*p ← 1
q ← p
*q ← *p + 1
escreva(*p)
libere(p)Resultado = 2
q
p
q
2
Ponteiros ou Apontadores
Exemplo 4:
Alocação dinâmica
Inteiro:*p,*q
aloque(p)
*p ← 1
q ← p
*q ← *p + 1
escreva(*p)
libere(p)
Ponteiros ou Apontadores
Exemplo 4:
Alocação dinâmica
Inteiro:*p,*q
aloque(p)
*p ← 1
q ← p
*q ← *p + 1
escreva(*p)
libere(p)
Para evitar accidentes acrescente:
q ← nulo
p ← nulo
Ponteiros ou Apontadores
Exemplo 5:Tipo reg: registro
real:valorreg:*pont
Fim_Registroreg:*p,*q,x,x1
x.valor ←10.5
p ←&x
x.pont ←&x1
Teste de mesa inicialp
q
lixo
lixo
Ponteiros ou Apontadores
Exemplo 5:Tipo reg: registro
real:valorreg:*pont
Fim_Registroreg:*p,*q,x,x1
x.valor ←10.5
p ←&x
x.pont ←&x1
p
q
lixo
lixo
Ponteiros ou Apontadores Exemplo 5:Tipo reg: registro
real:valorreg:*pont
Fim_Registroreg:*p,*q,x,x1
x.valor ←10.5
p ←&x
x.pont ←&x1
x1.valor ← 0,2
q ← x.pont
x1.pont ← NULO
p
lixo
Usamos o símbolo
Para indicar que o ponteiro
aponta para nulo
Ponteiros ou Apontadores
escreva(*p.valor)
escreva(*q.valor)
escreva(*p.*pont.valor)
escreva(x.valor)
escreva(x.*pont.valor)
escreva(x1.valor)
p
Ponteiros ou Apontadores
escreva(*p.valor)
escreva(*q.valor)
escreva(*p.*pont.valor)
escreva(x.valor)
escreva(x.*pont.valor)
escreva(x1.valor)
p
10,5
0,2
0,2
10,5
0,2
0,2
Ponteiros ou ApontadoresExercícios:
(1) Qual é a saída de c em
inteiro *p,*q,a,b,c
a ←1
b ←2
p ← &a
q ← &b
c ← *p + *q
Ponteiros ou ApontadoresExercícios:
(2) Qual é a saída de c em
inteiro *p, **r,a,c,b
a ←1
b ←2
p ← &a
r ← &p
c ← **r + b
(3) Obtenha a saída do algoritmo anterior fazendo com que p e q sejam alocadas dinamicamente. Não use x nem x1.
Ponteiros ou ApontadoresExercícios:
(4) Por que o algoritmo abaixo está errado?
procedimento troca (inteiro: *i, *j)
inteiro *temp
Início
*temp ← *i
*i ← *j
*j ← *temp
Fim
Ponteiros ou Apontadores(5) Dado o seguinte algoritmo, complete as
Tabelas 1 e 2.
inteiro: i, j, *p_1, *p_2, **p_p_1, **p_p_2
i ← 4
j ← 5
p_1 ← &i
p_2 ← &j
p_p_1 ← &p_2
p_p_2 ← &p_1
Ponteiros ou Apontadores(6) Dado o seguinte algoritmo, complete as
Tabelas 3 e 4.
inteiro: i, j, *p_1, *p_2, **p_3, ***p_4
i ← 4
j ← 5
p_1 ← &j
p_2 ← &i
p_3 ← &p_1
p_4 ← &p_3