11_Ponteiros

8/18/2019 11_Ponteiros

1/45

Ementário

• Noções de hardware e software.• Conceitos Fundamentais.• Vetores, cadeia de caracteres e registros.• Definição e manipulação de arquivos eternos.• !u"programação.

• #locação din$mica de mem%ria. • Estruturas de dados básicas: listas lineares, pilha e

fila. Árvores e grafos.• Métodos de ordenação.• #plicações pr&ticas utili'ando uma linguagem

estruturada de alto n(vel (inguage! "#.• $oç%es de &rogra!ação 'rientada a 'betos co!

a inguage! ")).


2/45

&*'+*M Á*E -*E

Me!/ria 0ispon1vel no "o!putador

"/digo e2ecutável:3 instruç%es (co!pilador#

3 ar!a4ena!ento do dados (estrutura dos dados#

Me!/ria livre, gerenciada pelo siste!a operacional


3/45

locação de Me!/ria (567#

• Estática 8 9uantidade total de !e!/ria utili4ada pelos

dados é previa!ente conhecida e definida de!odo i!utável, no pr/prio c/digo3fonte do

progra!a.

8 0urante toda a e2ecução, a uantidade de!e!/ria utili4ada pelo progra!a não varia.

8 ista de variáveis declaradas.


4/45

locação de Me!/ria (767#

• 0in;!ica 8 9uanto o progra!a é capa4 de criar novas

variáveis enuanto está sendo e2ecutado. 8 locação de !e!/ria para co!ponentes

individuais no instante e! ue eles co!eça! a

e2istir durante a e2ecução do progra!a. 8 malloc: alocar !e!/ria.

8 free: li"erar áreas da !e!/ria ocupadas.


5/45

locação Estática

2locação 0in;!ica


6/45

locação Estática (56 5???@# 8 te!po de co!pilação 8 alocados e! !e!/ria de for!a estática


7/45

locação Estática (76


8/45

locação Estática (


9/45

locação 0in;!ica

• i!ple!entação eficiente: ponteiros ou apontadores

• vantagens: 8 ta!anho variável 8 te!po de e2ecução

8 alocados e! !e!/ria de for!a din;!ica• desvantage!, ou restrição: 8 capacidade da !e!/ria, acesso seuencial


10/45

ariável > endereço de !e!/ria

Área de !e!/ria onde dados são ar!a4enados:• variável estática (lista de variáveis#

8 e2istAncia prevista no c/digo do progra!a(te!po de co!pilação#

8 uantidade de !e!/ria utili4ada pelo progra!anão varia

• variável din;!ica (malloc, free# 8 passa! a e2istir durante a e2ecução do progra!a


11/45

ariáveis 0in;!icas (ponteiros#

• ponteiros, ou apontadores, ou indicadores,ou referAncias

• variáveis especiais ue ar!a4ena!endereços de !e!/ria, isto é, endereços deoutras variáveis na !e!/ria

• ar!a4ena! u! endereço e não u! valor • e! ", o ponteiro é !ais u! tipo per!itidoco!o ualuer outro


12/45

Variáveis Ponteiros

&ara declarar u! ponteiro de u! certo tipo, usa3se a seguinte sinta2e:

TipoBase *nome@

Onde:TipoBase é o tipo da infor!ação ue será apontada pelo ponteiro

(infor!a o total de bBtes ocupados pela infor!ação#

o s1!bolo * serve para indicar ue se trata da definição de u! ponteiro

nome corresponde ao no!e da variável ponteiro


13/45

Definição de Variáveis do Tipo Ponteiro:

1! onteiros ptipos pr&2de'inidos 3$sicos56

int *pt7nt;float *pt8loat;char *ptChar; // definição de string

9! onteiros ptipos de'inidos pelo programador6struct rg8unc {

char nome[40];

char sexo;

float salario;

};

struct rg8unc *pt8unc;


14/45

Os Operadores de Ponteiros: * e !"#$%

' operador C devolve o endereço na !e!/ria doseu operando. &or e2e!plo:

int x = 10;

int *p = &x;

coloca e! p o endereço da !e!/ria ue conté! avariável . Esse endereço é a posição interna

ao co!putador da variável. ' endereço não te!relação algu!a co! o valor de . ' operador C pode ser i!aginado co!o retornando Do endereço

de, ou sea, D p recebe o endereço de .


15/45

Os Operadores de Ponteiros: * e !$#$%

' operador F é o co!ple!ento de C, ele devolve o

valor da variável locali4ada no endereço ue o segue.&or e2e!plo, se p conté! o endereço da variável 2,

int x = 10;int *p = &x;int : = *p;

print'3


16/45

&sando os operadores de ponteiros !* e %

void main35 {

int x, *p; x = 10;

p = &x; print'3


17/45


18/45

'epresentação (nterna de Variáveis do TipoPonteiro:

s variáveis din;!icas não são e2plicita!entedeclaradas co!o as estáticas, direta!ente por apelidos ou identificadores.

Hão referenciadas por seus endereços de mem)ria,ar!a4enados e! variáveis (estáticas# especiais

cha!adas de ponteiros ou apontadores.


19/45

Trabalando com a mem)ria apontada peloponteiro:

&ara trabalhar a !e!/ria ue o ponteiro p está apontando, utili4a3se ooperador *, co! a sinta2e: *p.

$atura!ente p deverá ter u! endereço válido, isto é, p deve estar

apontando para u!a variável ou para u!a !e!/ria de tipoco!pat1vel. &ara tanto, dois outros tipos de atribuiç%es pode! ser feitos co! variáveis do tipo ponteiro:

a% u! ponteiro pode receber o conteIdo de outro ponteiro co!pat1vel(apontar para u! endereço ue contA! u! valor do !es!o tipo#@

b% u! ponteiro pode receber u! endereço especial, cha!ado +&,, (nulo#, ue serve para di4er ue é u! endereço nulo e ue não haverá

nenhu!a variável neste endereço de !e!/ria.


20/45

-locação Din.mica de /em)ria em 0:

área de !e!/ria ue não é utili4ada por u! progra!a é organi4ada e

gerenciada pelo siste!a operacional, podendo ser alocada através deco!andos padroni4ados oferecidos pela pr/pria linguage! ".

&ara alocar u!a porção da área livre, basta utili4ar o co!ando malloc,sendo p u!a variável ponteiro: p > (int *# malloc(si4eof(int##@ aloca

u!a área de !e!/ria suficiente para ar!a4enar u! nI!ero inteiro eguarda o endereço ocupado e! p, á o co!ando: free(p#@ serve paraliberar a área de !e!/ria cuo endereço está e! p. J!a área de!e!/ria, ue foi alocada pelo co!ando malloc, so!ente volta a ficar

dispon1vel se for e2plicita!ente liberada pelo co!ando free, casocontrário, a liberação da área s/ ocorrerá uando o progra!a ue fe4 aalocação ter!inar de e2ecutar.

&ara co!pletar, p > $J@ !arca p co!o u! endereço nulo. Este

endereço é Itil para di4er ue o ponteiro ainda não te! nenhu!


21/45

Lixo10

Lixo1FFA

'epresentação (nterna da Variável do TipoPonteiro:void main35 {

int *p;

p = 3int *5 malloc3si.eo'3int55;

*p = 10; !!!

free3p5;} mem-ria usada

pelo programa

p:

endereo

1FFA

mem-ria livreno sistema

aloca a variável estatica!ente

aloca a variável dina!ica!ente

!

Lixo

mem-ria usada

pelo programa

p: mem-ria livreno sistema


22/45

Entendendo o c)di1o:

int *p;a variável p é u! ponteiro para u! nI!ero inteiro, ou sea, Daponta

para u! endereço de !e!/ria ue será Dalocado para ar!a4enar u!nI!ero inteiro (7 bBtes#

p = 3int *5 malloc3si.eo'3int55;solicita ao siste!a operacional 7 bBtes da !e!/ria livre e o Dendereçodo espaço alocado é colocado na variável ponteiro p

*p = 10;no endereço apontado por p ar!a4ena o nI!ero inteiro 5?

free3p5;libera o espaço de !e!/ria ocupado cuo endereço está e! p (devolve o recurso ao siste!a operacional#


23/45

Operadores ponto !2% e seta !34%:'s operadores ponto e seta são usados para especificar ele!entos individuais deestruturas (struct# e uni%es. ' operador ponto é usado para especificar direta!ente o

ele!ento e o operador seta para especificar o ele!ento através de u! ponteiro.

>include ?stdio!h@

>include ?string!h@

struct rgessoa A

char nome[B]; char apelido[90];

D;

int main35 A

struct rgessoa pessoa; struct rgessoa * pont"essoa = & pessoa;

strcp:3 pessoa#nome, Emero 8rancisco Fertol5; strcp:3 pessoa#apelido, Chico5;

print'3Gesultado6n5;

print'3Nome!!!6


24/45


25/45

Lista ncadeada com !etor '()( * * * AL+CA,-+ .//CA * * *

struct /ipotem { // cada item da lista corresponde a um registro char nome[B0]; // (/ipotem ) composto apenas do campo nome};

void estatica3void5 { fflush3stdin5; const maxTam = 100; // maxTam = tamanho máximo da lista

int n = 0, i; // n = quantidade efetiva de itens na lista

/ipotem lista[maxTam], x; hile 315 { clrscr35;

printf3Hista de nomes 3+locaão *st$tica5n5; for 3i=0; i?n; iII5 printf3


26/45

,istas Encadeadas com Ponteiros !"#5%

's tipos ponteiros ou apontadores são Iteis para criar estruturas de

dados encadeadas, do tipo listas (pilha e fila#, árvores e grafos. J!apontador é u!a variável ue referencia u!a outra variável alocadadinamicamente. E! geral a variável referenciada é definida co!o u!registro ue inclui ta!bé! u! apontador para outro ele!ento do

!es!o tipo. &or E2e!plo: struct Celula { /ipotem 7tem; Celula *prox;};

Celula *primeiro, *ultimo, *p;

Hendo a variável primeiro u! endereço para u! registro Celula ueconté! o *tem ar!a4enado e o endereço ( pro# da pr/2i!a célula dalista3 é poss1vel criar u!a lista encadeada através de ponteiros.


27/45

,istas Encadeadas com Ponteiros !$#5%

(tem

Ponteiro ou -pontador

+&,,

0elula

pro6

...7oão /aria -na

primeiro

$a alocação encadeada, os ele!entos são ar!a4enados e! blocos de!e!/ria deno!inados c8lulas, ou nodos, sendo ue cada célula éco!posta por dois ca!pos: u! para ar!a4enar os dados ( *tem# e outro

para ar!a4enar o endereço do pr/2i!o ele!ento da lista ( pro#3 para!anter a relação de orde! linear. Hão endereços especiais da listaencadeada co! ponteiros: a% primeiro: endereço do pri!eiro ele!entoda lista (célula cabeça#, e, b% ultimo: endereço do Ilti!o ele!ento dalista (o endereço do ele!ento nulo ($J# segue o Ilti!o ele!entoda lista.

ultimo

08lula

0abeça


28/45

,istas Encadeadas !9#5%

Vanta1em de istas Encadeadas co! ponteiros ou apontadores:

3 acilidade de inserir ou remover elementos do meio da lista2 "o!o os ele!entos não precisa! estar ar!a4enados e! posiç%esconsecutivas de !e!/ria, nenhu! dado precisa ser !ovi!entado,

bastando atuali4ar o ca!po de ligação (pro6# do ele!ento ue

precede auele inserido ou re!ovido.

Desvanta1em de istas Encadeadas co! ponteiros ou apontadores:3 -cessar uma posição espec;fica dentro da lista2

"o!o apenas o pri!eiro ele!ento é acess1vel direta!ente através doendereço primeiro, deve3se partir do pri!eiro e ir seguindo os ca!posde ligação (pro6#, u! a u!, até atingir a posição deseada. 'bvia!ente,

para listas e2tensas, esta operação pode ter u! alto custo e! relação a

te!po.

Lista ncadeada com "onteiro '5)5 * * * AL+CA,-+ 6789CA * * *


29/45

Lista ncadeada com "onteiro '5)5 * * * AL+CA,-+ 6789CA * * *void dinamica3void5 { fflush3stdin5; struct Celula { Tipo7tem 7tem;

Celula *prox; }; Tipo7tem x;

Celula *primeiro, *ultimo, *p;// cria a célula ca#eça

primeiro = 3Celula *5 malloc3si.eo'3Celula55; primeiro$% prox = NLHH; ultimo = primeiro;

hile 315 { clrscr35; print'3Hista de nomes 3+locaão Minmica5n5;

p = primeiro2@prox;

hile 3p K= 7LL5 { print'3


30/45

"élula especial, ue Dnão ar!a4ena itens, !as ue é usada paraindicar o pri!eiro ele!ento da lista. Obs. uando a lista está va4ia a

Inica célula e2istente é a célula cabeça, portanto, antes de ualuer operação co! a lista deve3se criar a célula cabeça.

Celula *primeiro, *ultimo;!!!

1! primeiro = 3Celula *5 malloc3si.eo'3Celula55;(! primeiro$% prox = NLHH;! ultimo = primeiro;

0riando a 08lula 0abeça da ,ista

+&,,

(tem

0elula

pro6

primeiro ultimo

1

(


31/45

Entendendo o 0)di1o !"#$%:

primeiro = 3Celula *5 malloc3si.eo'3Celula55;

primeiro$% prox = NLHH;

o operador 34 (seta# é usando para referenciar ele!entos individuais(ou ca!pos# de estruturas (ou registros# apontadas por variávies

ponteiros

indica o valor retornado pela função malloc, ou sea, oendereço do espaço alocado pelo siste!a operacional

para ar!a4enar u!a célula da lista

cha!a a função malloc paraalocar a !e!/ria dina!ica!ente,serão alocados si4eof("elula# bBtes


32/45

Entendendo o 0)di1o !$#$%:

Celula *primeiro, *ultimo;

as variáveis primeiro e ultimo são ponteiros para u! registro D"elula,ou sea, Daponta! para endereços de !e!/ria ue serão usados paraar!a4enar os itens (ou células# da lista

primeiro = 3Celula *5 malloc3si.eo'3Celula55;

solicita ao siste!a operacional si4eof("elula# bBtes da !e!/rialivre e o Dendereço do espaço alocado é colocado na variável

ponteiro primeiro

primeiro$% prox = NLHH;

no ca!po Dpro2 da célula apontada pelo ponteiro primeiro ar!a4enao endereço $J, ou sea, o endereço de ningué!

ultimo = primeiro;

o ponteiro ultimo aponta para o !es!o endereço ar!a4enado noonteiro rimeiro


33/45

1! ultimo$% prox = 3Celula *5 malloc3si.eo'3Celula55;(! ultimo = ultimo$% prox;

! ultimo$% 7tem = x;5! ultimo$% prox = 7LL;

0olocando o +ovo (tem no inal da ,ista

+&,,Omero /aria 7uca

(tem

0elula

pro6

primeiro ultimo

pro6

1

+&,,

5

(

-na

6

(tem pro6

-na


34/45

' algorit!o para percorrer u!a lista do pri!eiro ele!ento até o Ilti!o,se resu!e, na utili4ação de u! apontador au2iliar p ue deve

inicial!ente receber o endereço da pri!eira célula da ista( p = primeiro-> prox;#. seguir, u! processo repetitivo ue fa4 p

pular, através do ca!po de ligação ( prox #, do nodo atual para o nodosucessor ( p = p-> prox;# até ue p passe pelo Ilti!o nodo da lista

(+&,,, o Ilti!o nodo da lista aponta para o va4io#.

*esu!indo e! ter!os de progra!a, o processo para percorrer u!a listaencadeada pode ser descrito co!o segue:

Celula *p;

!!!// endereço da primeira célula da lista

p = primeiro$% prox; hile 3p K= 7LL5 {

print'3


35/45

' algorit!o para liberar os endereços de !e!/ria alocados na criaçãoda lista deve percorrer, a partir da célula cabeça, todas as células dalista liberando o espaço de !e!/ria ocupado pela célula através dafunção free. &or e2e!plo:

Celula *primeiro, *p;!!!

// endereço da célula ca#eça

p = primeiro;

hile 3p K= 7LL5 {

// endereço do nodo sucessor (prximo) primeiro = primeiro$% prox;

liera a $rea de mem-ria cu/o endereo est$ em p free3p5;

// prxima célula a ser li#erada

p = primeiro;

}

,iberando os Espaços -locados na 0riaçãoda ,ista Encadeada


36/45

(nserindo uma +ova 08lula na ,ista !"#5%

+&,,-na 0arlos ,uana

0ada u!a cadeia de células (ou nodos#, é necessário e2pandir

esta cadeia co! novos blocos. &ara entender co!o isto podeser feito, basta considerar a situação esue!ati4ada, naLigura abai2o, onde u! nodo de endereço novo deve ser inserido e! u!a ista, ap/s a posição indicada pelo

ponteiro p:p

Danielnovo

(tem

0elula

pro6

primeiro ultimo


37/45

(nserindo uma +ova 08lula na ,ista !$#5%


"o!o o novo nodo será inserido logo ap/s auele ue

ar!a4ena o ele!ento GCarlosG, seu sucessor será auelenodo ue ar!a4ena o ele!ento G +uanaG. &ara isto, bastaatuali4ar o ca!po de ligação ( prox # do novo nodo co! oendereço dauele ue guarda o ele!ento G +uanaG.

p

Danielnovonovo-> prox = p-> prox;

(tem

0elula

pro6

primeiro ultimo


38/45

(nserindo uma +ova 08lula na ,ista !9#5%


$a pr/2i!a etapa, fa43se o sucessor do nodo apontado por p

(GCarlosG# ser auele apontado por novo (G Daniel G#.

p

Danielnovo

p-> prox = novo;

(tem

0elula

pro6

primeiro ultimo


39/45

(nserindo uma +ova 08lula na ,ista !5#5%

+&,,-na 0arlos

*esu!indo e! ter!os de progra!a, o processo de inserção pode ser

descrito co!o segue:1! novo$% prox = p$% prox;(! p$% prox = novo;

p

Danielnovo 1

(

(tem

0elula

pro6

primeiro ultimo

,uana


40/45

'emovendo uma 08lula da ,ista !"#


41/45

'emovendo uma 08lula da ,ista !$# prox;

(tem

0elula

pro6

ultimo

+&,,

primeiro


42/45

'emovendo uma 08lula da ,ista !9#


43/45

'emovendo uma 08lula da ,ista !5#


44/45

'emovendo uma 08lula da ,ista !


45/45

*eferAncias (&onteiros e! &ascal#

• Estrutura de 0ados Lunda!entais: conceitos eaplicaç%es.

8 Hilvio do ago &ereira. 8 7 M ed. 3 Hão &aulo: Nrica, 5OOP.

• -nstituto de "o!putação da J$-"M&

8 Llávio Q. MiBa4aRa C =o!as4 QoRaltoRsSi 8 http:66oli!piada.ic.unica!p.br6apostila.ht!l
http://olimpiada.ic.unicamp.br/apostila.htmlhttp://olimpiada.ic.unicamp.br/apostila.html

Documents

11_Ponteiros