Algoritmos e Estruturas de Dados I – Ponteiros Profa. Mercedes Gonzales Márquez

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)


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


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


Exemplo 4:

Inteiro:x, *p,*q

x ← 1

p ← &x

*q ← 3

q ← p

*q ← *p + 1

escreva(*p)

p x

q

1

lixo


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


Exemplo 4:

Inteiro:x, *p,*q

x ← 1

p ← &x

*q ← 3

q ← p

*q ← *p + 1

escreva(*p)

p x

q

1


Exemplo 4:

Inteiro:x, *p,*q

x ← 1

p ← &x

*q ← 3

q ← p

*q ← *p + 1

escreva(*p)

p x

q

2


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


Exemplo 4:


Inteiro:*p,*q

aloque(p)

*p ← 1

q ← p

*q ← *p + 1

escreva(*p)

libere(p)

Teste de mesa inicialp

q

lixo

lixo


Exemplo 4:


Inteiro:*p,*q

aloque(p)

*p ← 1

q ← p

*q ← *p + 1

escreva(*p)

libere(p)

q

lixo


Exemplo 4:


Inteiro:*p,*q

aloque(p)

*p ← 1

q ← p

*q ← *p + 1

escreva(*p)

libere(p)

q

lixo


Exemplo 4:


Inteiro:*p,*q

aloque(p)

*p ← 1

q ← p

*q ← *p + 1

escreva(*p)

libere(p)

p

q

1

lixo


Exemplo 4:


Inteiro:*p,*q

aloque(p)

*p ← 1

q ← p

*q ← *p + 1

escreva(*p)

libere(p)

q

p

q

1


Exemplo 4:


Inteiro:*p,*q

aloque(p)

*p ← 1

q ← p

*q ← *p + 1

escreva(*p)

libere(p)

q

p

q

2


Exemplo 4:


Inteiro:*p,*q

aloque(p)

*p ← 1

q ← p

*q ← *p + 1

escreva(*p)

libere(p)Resultado = 2

q

p

q

2


Exemplo 4:


Inteiro:*p,*q

aloque(p)

*p ← 1

q ← p

*q ← *p + 1

escreva(*p)

libere(p)


Exemplo 4:


Inteiro:*p,*q

aloque(p)

*p ← 1

q ← p

*q ← *p + 1

escreva(*p)

libere(p)

Para evitar accidentes acrescente:

q ← nulo

p ← nulo


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


Exemplo 5:Tipo reg: registro

real:valorreg:*pont


x.valor ←10.5

p ←&x

x.pont ←&x1

p

q

lixo

lixo

Ponteiros ou Apontadores Exemplo 5:Tipo reg: registro

real:valorreg:*pont


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


escreva(*p.valor)

escreva(*q.valor)

escreva(*p.*pont.valor)

escreva(x.valor)

escreva(x.*pont.valor)

escreva(x1.valor)

p


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


(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.


(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

Documents

Algoritmos e Estruturas de Dados I – Ponteiros Profa. Mercedes Gonzales Márquez