MC-102 — Aula 20Ponteiros III
Eduardo C. Xavier
Instituto de Computacao – Unicamp
18 de Maio de 2017
Roteiro
1 Exemplo de Ponteiros e Alocacao Dinamica
2 Exercıcio
3 Informacoes Extras: Ponteiros para Ponteiros e Alocacao Dinamica deMatrizes
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 2 / 26
Exemplo de Ponteiros e Alocacao Dinamica
Vamos criar uma aplicacao que cria um vetor dinamico com funcoes paraimplementar as seguintes operacoes:
Inclusao de um elemento no final do vetor.
Exclusao da primeira ocorrencia de um elemento no vetor.
Impressao do vetor.
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 3 / 26
Exemplo de Ponteiros e Alocacao Dinamica
O tamanho do vetor deve se ajustar automaticamente: se elementossao inseridos devemos “aumentar”o tamanho do vetor para inclusaode novos elementos, e se elementos forem removidos devemos”diminuir”o tamanho vetor.
Temos duas variaveis associadas ao vetor:I size: denota quantos elementos estao armazenados no vetor.I maxSize: denota o tamanho alocado do vetor.
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 4 / 26
Exemplo de Ponteiros e Alocacao Dinamica
Temos as seguintes regras para ajuste do tamanho alocado do vetor:
O vetor deve ter tamanho alocado no mınimo igual a 4.
Se o vetor ficar cheio, entao devemos alocar um novo vetor com odobro do tamanho atual.
Se o numero de elementos armazenados no vetor for menor do que1/4 do tamanho alocado do vetor, entao devemos alocar um novovetor com metade do tamanho atual.
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 5 / 26
Exemplo de Ponteiros e Alocacao Dinamica
Implementaremos as seguintes funcoes:
i n t ∗ i n i t V e t ( i n t ∗ s i z e , i n t ∗maxSize ) ;
Aloca um vetor inicial de tamanho 4, setando size com valor 0,maxSize com valor 4, e devolve o endereco do vetor alocado.
v o i d p r i n t V e t ( i n t ∗v , i n t s i z e , i n t maxSize ) ;
Imprime o conteudo e tamanhos associados ao vetor v.
i n t ∗ addVet ( i n t ∗v , i n t ∗ s i z e , i n t ∗maxSize , i n t e ) ;
Adiciona o elemento e no final do vetor v. Caso nao haja espaco, umnovo vetor com o dobro do tamanho deve ser alocado. A funcaosempre retorna o endereco do vetor, sendo um novo alocado ou nao.Alem disso os valores de size e maxSize devem ser atualizados.
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 6 / 26
Exemplo de Ponteiros e Alocacao Dinamica
Implementaremos as seguintes funcoes:
i n t f i n d ( i n t ∗v , i n t s i z e , i n t e ) ;
Determina se o elemento e esta presente ou nao no vetor v. Casoesteja presente, retorna a posicao da primeira ocorrencia de e em v.Caso nao esteja presente, retorna -1.
i n t ∗ removeVet ( i n t ∗v , i n t ∗ s i z e , i n t ∗maxSize , i n t e ) ;
Remove a primeira ocorrencia do elemento e do vetor v caso esteesteja presente. O valor de size deve ser decrementado de 1. Caso onumero de elementos armazenados seja menor do que 1
4 maxSize,entao um novo vetor de tamanho 1
2 maxSize deve ser alocado no lugarde v. A funcao sempre retorna o endereco inicial do vetor alocado,sendo um novo vetor alocado ou nao.
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 7 / 26
Exemplo de Ponteiros e Alocacao Dinamica
Funcoes initVet e printVet:
// C r i a v e t o r com maxSize i n i c i a l 4 .// Devo lve o e n d e r e c o do v e t o r c r i a d o .i n t ∗ i n i t V e t ( i n t ∗ s i z e , i n t ∗maxSize ){
i n t ∗v = m a l l o c (4∗ s i z e o f ( i n t ) ) ;∗ s i z e = 0 ;∗maxSize = 4 ;r e t u r n v ;
}
// Imprime v e t o r .v o i d p r i n t V e t ( i n t ∗v , i n t s i z e , i n t maxSize ){
i n t i ;p r i n t f ( ” Vetor de tamanho %d ( max . a l o c a d o %d )\n” , s i z e , maxSize ) ;f o r ( i =0; i<s i z e ; i ++){
p r i n t f ( ”%d , ” , v [ i ] ) ;}p r i n t f ( ”\n” ) ;
}
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 8 / 26
Exemplo de Ponteiros e Alocacao Dinamica
A funcao addVet:
i n t ∗ addVet ( i n t ∗v , i n t ∗ s i z e , i n t ∗maxSize , i n t e ){i f (∗ s i z e < ∗maxSize ){ //Tem esp aco para o e lemento .
v [∗ s i z e ] = e ;(∗ s i z e )++;r e t u r n v ;
} e l s e { // P r e c i s a m o s a l o c a r um espa co maior .. . .
}}
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 9 / 26
Exemplo de Ponteiros e Alocacao Dinamica
A funcao addVet:
i n t ∗ addVet ( i n t ∗v , i n t ∗ s i z e , i n t ∗maxSize , i n t e ){i f (∗ s i z e < ∗maxSize ){ //Tem esp aco para o e lemento .
. . .} e l s e { // P r e c i s a m o s a l o c a r um espa co maior .
i n t ∗ vaux = m a l l o c ( 2∗ (∗maxSize )∗ ( s i z e o f ( i n t ) ) ) ;i n t i ;f o r ( i =0; i < ∗ s i z e ; i ++) // S a l v a dados de v em vaux .
vaux [ i ] = v [ i ] ;vaux [∗ s i z e ] = e ; // A d i c i o n a e lemento no f im .
(∗ s i z e )++;∗maxSize = 2∗(∗maxSize ) ; // A t u a l i z a dados de tamanho .
f r e e ( v ) ; // L i b e r a memoria nao mais n e c e s s a r i a .r e t u r n vaux ;
}}
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 10 / 26
Exemplo de Ponteiros e Alocacao Dinamica
A funcao addVet completa:
i n t ∗ addVet ( i n t ∗v , i n t ∗ s i z e , i n t ∗maxSize , i n t e ){i f (∗ s i z e < ∗maxSize ){ //Tem esp aco para o e lemento .
v [∗ s i z e ] = e ;(∗ s i z e )++;r e t u r n v ;
} e l s e { // P r e c i s a m o s a l o c a r um espa co maior .i n t ∗ vaux = m a l l o c ( 2∗ (∗maxSize )∗ ( s i z e o f ( i n t ) ) ) ;i n t i ;f o r ( i =0; i < ∗ s i z e ; i ++) // S a l v a dados de v em vaux .
vaux [ i ] = v [ i ] ;vaux [∗ s i z e ] = e ; // A d i c i o n a e lemento no f im .
(∗ s i z e )++;∗maxSize = 2∗(∗maxSize ) ; // A t u a l i z a dados de tamanho .
f r e e ( v ) ; // L i b e r a memoria nao mais n e c e s s a r i a .r e t u r n vaux ;
}}
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 11 / 26
Exemplo de Ponteiros e Alocacao Dinamica
A funcao find e:
// Retorna p o s i c a o da p r i m e i r a o c o r r e n c i a de e// ou −1 caso e nao s e j a e n c o n t r a d oi n t f i n d ( i n t ∗v , i n t s i z e , i n t e ){
i n t i ;f o r ( i =0; i<s i z e ; i ++)
i f ( v [ i ] == e )r e t u r n i ;
r e t u r n −1;}
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 12 / 26
Exemplo de Ponteiros e Alocacao Dinamica
A funcao removeVet e:
i n t ∗ removeVet ( i n t ∗v , i n t ∗ s i z e , i n t ∗maxSize , i n t e ){i n t i ;i = f i n d ( v , ∗ s i z e , e ) ;i f ( i != −1){ // Se e lemento e s t a em v .
// Copia dados a p a r t i r da p o s i c a o i +1 uma p o s i c a o para t r a s .f o r ( ; i < (∗ s i z e )−1 ; i ++){
v [ i ] = v [ i +1] ;}(∗ s i z e )−−;
// Se tamanho do v e t o r f o r > 4 e e s t i v e r menos de 1/4 ocupado// devemos d i m i n u i r tamanho do v e t o r p e l a metade .i f ( ∗ s i z e < ( 0 . 2 5 ∗ (∗maxSize ) ) && ∗maxSize > 4 ){
. . .E x e r c ı c i o .
}}r e t u r n v ;
}
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 13 / 26
Exemplo de Ponteiros e Alocacao Dinamica
Com as funcoes implementadas podemos executar o exemplo:
i n t main (){i n t ∗vet , s i z e , maxSize ;i n t i ;
v e t = i n i t V e t (& s i z e , &maxSize ) ;
f o r ( i =0; i <20; i ++){v e t = addVet ( vet , &s i z e , &maxSize , i ) ;
}p r i n t V e t ( vet , s i z e , maxSize ) ;
v e t = removeVet ( vet , &s i z e , &maxSize , 1 4 ) ;p r i n t V e t ( vet , s i z e , maxSize ) ;
f o r ( i =5; i <15; i ++){v e t = removeVet ( vet , &s i z e , &maxSize , i ) ;
}p r i n t V e t ( vet , s i z e , maxSize ) ;
f o r ( i =0; i <20; i ++){v e t = removeVet ( vet , &s i z e , &maxSize , i ) ;
}p r i n t V e t ( vet , s i z e , maxSize ) ;
f r e e ( v e t ) ;}
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 14 / 26
Exercıcio
Implemente a funcao de remocao de um elemento do vetor de tal formaque se o numero de elementos armazenados (size) for menor do que14maxSize, entao o tamanho do vetor alocado deve ter tamanho igual ametade do anterior. A funcao deve devolver o endereco do inıcio do vetor,sendo um novo alocado ou nao. Alem disso a funcao deve atualizar osvalores size e maxSize caso necessario.
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 15 / 26
Informacoes Extras: Alocacao Dinamica de Matrizes
Em aplicacoes cientıficas e de engenharias, e muito comum arealizacao de diversas operacoes sobre matrizes.
Em situacoes reais o ideal e alocar memoria suficiente para conter osdados a serem tratados. Nao usar nem mais e nem menos!
Como alocar vetores-multidimensionais dinamicamente?
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 16 / 26
Informacoes Extras: Ponteiros para ponteiros
Uma variavel ponteiro esta alocada na memoria do computador comoqualquer outra variavel.
Portanto podemos criar um ponteiro que contem o endereco dememoria de um outro ponteiro.
Para criar um ponteiro para ponteiro: tipo **nomePonteiro;
I i n t main ( ){i n t a=5, ∗b , ∗∗ c ;b = &a ;c = &b ;p r i n t f ( ”%d\n” , a ) ;p r i n t f ( ”%d\n” , ∗b ) ;p r i n t f ( ”%d\n” , ∗(∗ c ) ) ;
}
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 17 / 26
Informacoes Extras: Ponteiros para ponteiros
O programa imprime 5 tres vezes, monstrando as tres formas de acesso avariavel a: a, *b, **c.
1036
c ba
100 200
200100 5
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 18 / 26
Informacoes Extras: Ponteiros para ponteiros
Pela nossa discussao anterior sobre ponteiros, sabemos que umponteiro pode ser usado para referenciar um vetor alocadodinamicamente.
I i n t ∗p ;p = c a l l o c ( 5 , s i z e o f ( i n t ) ) ;
0
p
0 0 0 0
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 19 / 26
Informacoes Extras: Ponteiros para ponteiros
A mesma coisa acontece com um ponteiro para ponteiro, so que nestecaso o vetor alocado e de ponteiros.
I i n t ∗∗p ;p = c a l l o c ( 5 , s i z e o f ( i n t ∗ ) ) ;
0
p
0 0 0 0
I Note que cada posicao do vetor acima e do tipo int *, ou seja, umponteiro para inteiro!
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 20 / 26
Informacoes Extras: Ponteiros para ponteirosComo cada posicao do vetor e um ponteiro para inteiro, podemosassociar cada posicao dinamicamente com um vetor de inteiros!
I i n t ∗∗p ;i n t i ;p = c a l l o c ( 5 , s i z e o f ( i n t ∗ ) ) ;
f o r ( i =0; i <5; i ++){p [ i ] = c a l l o c ( 3 , s i z e o f ( i n t ) ) ;
}
384
p
104
234
406
512
560
384
104
234
406
512
560
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 21 / 26
Informacoes Extras: Alocacao Dinamica de Matrizes
Esta e a forma de se criar matrizes dinamicamente:
Crie um ponteiro para ponteiro.
Associe um vetor de ponteiros dinamicamente com este ponteiro deponteiro. O tamanho deste vetor e o numero de linhas da matriz.
Cada posicao do vetor sera associada com um outro vetor do tipo aser armazenado. Cada um destes vetores e uma linha da matriz(portanto possui tamanho igual ao numero de colunas).
OBS: No final voce deve desalocar toda a memoria alocada!!
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 22 / 26
Informacoes Extras: Alocacao Dinamica de Matrizesi n t main ( ){
i n t ∗∗p , i , j ;
p = c a l l o c ( 5 , s i z e o f ( i n t ∗ ) ) ;f o r ( i =0; i <5; i ++){
p [ i ] = c a l l o c ( 3 , s i z e o f ( i n t ) ) ;} // Alocou m a t r i z 5 x3
p r i n t f ( ” D i g i t e os v a l o r e s da m a t r i z \n” ) ;f o r ( i = 0 ; i <5; i ++)
f o r ( j =0; j <3; j ++)s c a n f ( ”%d” , &p [ i ] [ j ] ) ;
p r i n t f ( ” M a t r i z l i d a \n” ) ;f o r ( i = 0 ; i <5; i ++){
f o r ( j =0; j <3; j ++){p r i n t f ( ”%d , ” , p [ i ] [ j ] ) ;
}p r i n t f ( ”\n” ) ;
}// d e s a l o c a n d o memoria usadaf o r ( i =0; i <5; i ++){
f r e e ( p [ i ] ) ;}f r e e ( p ) ;
}Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 23 / 26
Informacoes Extras: Alocacao Dinamica de MatrizesOutro exemplo:i n t main ( ){
i n t ∗∗mat ; i n t i , j , n , m;
p r i n t f ( ”Numero de l i n h a s : ” ) ;s c a n f ( ”%d” , &n ) ;p r i n t f ( ”Numero de c o l u n a s : ” ) ;s c a n f ( ”%d” , &m) ;
mat = m a l l o c ( n ∗ s i z e o f ( i n t ∗ ) ) ;f o r ( i =0; i<n ; i ++){
mat [ i ] = m a l l o c (m ∗ s i z e o f ( i n t ) ) ;}
f o r ( i =0; i<n ; i ++){f o r ( j =0; j<m; j ++){
mat [ i ] [ j ] = i ∗ j ;}
}...
}
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 24 / 26
Informacoes Extras: Alocacao Dinamica de MatrizesOutro exemplo:
.
.
.f o r ( i =0; i<n ; i ++){
f o r ( j =0; j<m; j ++){mat [ i ] [ j ] = i ∗ j ;
}}
f o r ( i =0; i<n ; i ++){f o r ( j =0; j<m; j ++){
p r i n t f ( ”%d , ” , mat [ i ] [ j ] ) ;}p r i n t f ( ”\n” ) ;
}
f o r ( i =0; i<n ; i ++){f r e e ( mat [ i ] ) ;
}f r e e ( mat ) ;
}
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 25 / 26
Informacoes Extras: Alocacao Dinamica de Matrizes
Mas a forma mais eficiente de criar matrizes e:
Para uma matriz de dimensoes n ×m, crie um vetor unidimensionaldinamicamente deste tamanho.
Use linearizacao de ındices para trabalhar com o vetor como se fosseuma matriz.
Desta forma tem-se um melhor aproveitamento da cache pois amatriz inteira esta sequencialmente em memoria.
No final voce deve desalocar toda a memoria alocada!!
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 26 / 26
Linearizacao de Indices
Podemos usar sempre vetores simples para representar matrizes (napratica o compilador faz isto por voce).
Ao declarar uma matriz como int mat[3][4], sabemos que seraoalocados 12 posicoes de memoria associadas com a variavel mat.
Poderıamos simplesmente criar int mat[12]. Mas perdemos asimplicidade de uso dos ındices em forma de matriz.
I Voce nao mais podera escrever mat[1][3] por exemplo.
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 27 / 26
Linearizacao de Indices
A linearizacao de ındices e justamente a representacao de matrizesusando-se um vetor simples.
Mas devemos ter um padrao para acessar as posicoes deste vetorcomo se sua organizacao fosse na forma de matriz.
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 28 / 26
Linearizacao de Indices
Considere o exemplo:int mat[12]; // ao inves de int mat[3][4]
Fazemos a divisao por linhas como segue:I Primeira linha: mat[0] ate mat[3]I Segunda linha: mat[4] ate mat[7]I Terceira linha: mat[8] ate mat[11]
Para acessar uma posicao [i ][j ] usamos:I mat[i*4 + j];
onde 0 ≤ i ≤ 2 e 0 ≤ j ≤ 3.
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 29 / 26
Linearizacao de Indices
De forma geral, seja matriz mat[n*m], representando mat[n][m].
Para acessar a posicao correspondente a [i ][j ] usamos:I mat[i*m + j];
onde 0 ≤ i ≤ n − 1 e 0 ≤ j ≤ m − 1.
Note que i pula de blocos de tamanho m, e j indexa a posicao dentrode um bloco.
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 30 / 26
Linearizacao de Indices
Podemos estender para mais dimensoes. Seja matriz mat[n*m*q],representando mat[n][m][q].
I As posicoes de 0 ate (m ∗ q)− 1 sao da primeira matriz.I As posicoes de (m ∗ q) ate (2 ∗m ∗ q)− 1 sao da segunda matriz.I Etc...
De forma geral, seja matriz mat[n*m*q], representandomat[n][m][q].
Para acessar a posicao correspondente a [i ][j ][k] usamos:I mat[i*m*q + j*q + k];
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 31 / 26
Linearizacao de Indices
int main(){
int mat[40]; //representando mat[5][8]
int i,j;
for(i=0; i<5; i++)
for(j=0;j<8; j++)
mat[i*8 + j] = i*j;
for(i=0; i<5; i++){
for(j=0;j<8; j++)
printf("%d, ",mat[i*8 + j]);
printf("\n");
}
}
Eduardo C. Xavier (Instituto de Computacao – Unicamp) MC-102 — Aula 20 18 de Maio de 2017 32 / 26