Computadores Digitais 2
Prof. Rodrigo de Souza Couto
Linguagens de Programação – DEL-Poli/UFRJ
Prof. Miguel Campista
Aula de Hoje
• Matrizes
– Alocação estática versus dinâmica
– Vetores bidimensionais – matrizes
– Matrizes dinâmicas
Computadores Digitais II– DETEL-FEN/UERJ
Prof. Rodrigo de Souza Couto
ATENÇÃO
• Esta apresentação foi baseada nos seguinte trabalhos:
– Notas de aula do Prof. Marco Casanova da PUC-Rio
• http://www.inf.puc-rio.br/~inf1620/material.html
– Waldemar Celes, Renato Cerqueira, José Lucas Rangel,
“Introdução a Estruturas de Dados”, Editora Campus,
2004
Computadores Digitais II– DETEL-FEN/UERJ
Prof. Rodrigo de Souza Couto
Parte 1
Programação (linguagem C)
Matrizes
Computadores Digitais II– DETEL-FEN/UERJ
Prof. Rodrigo de Souza Couto
Alocação Estática versus
Dinâmica
• Alocação estática de vetor
– É necessário saber de antemão a dimensão máxima do
vetor
– Variável que representa o vetor armazena endereço
ocupado pelo primeiro elemento do vetor
– Vetor declarado dentro do corpo de uma função não
pode ser usado fora do corpo da função
#define N 10
int v[N]
Computadores Digitais II– DETEL-FEN/UERJ
Prof. Rodrigo de Souza Couto
Alocação Estática versus
Dinâmica
• Alocação dinâmica de vetor
– Dimensão do vetor pode ser definida em tempo de
execução
– Variável do tipo ponteiro recebe o valor do endereço do
primeiro elemento do vetor
– Área de memória ocupada pelo vetor permanece válida
até que seja explicitamente liberada (função free)
• Vetor alocado dentro do corpo de uma função pode ser
usado fora do corpo da função, enquanto estiver alocado
int v;
...
v = (int*) malloc(n*sizeof(int))
Computadores Digitais II– DETEL-FEN/UERJ
Prof. Rodrigo de Souza Couto
Alocação Estática versus
Dinâmica
• Função realloc
– Permite realocar um vetor preservando o conteúdo dos
elementos, que permanecem válidos após a realocação
– Exemplo
• m representa a nova dimensão do vetor
int v;
...
v = (int*) malloc(n*sizeof(int))
v = (int*) realloc(v,m*sizeof(int))
Computadores Digitais II– DETEL-FEN/UERJ
Prof. Rodrigo de Souza Couto
Vetores Bidimensionais:
Matrizes
• Vetor bidimensional (ou matriz)
– Elementos armazenados de forma contínua
• Linha a linha
– Alocação Estática
124
int m[3][2] = {{1,2},{3,4},{5,6}}
m[i][j]
i
j
1
2
3
4
5
6
Computadores Digitais II– DETEL-FEN/UERJ
m
6
120
5
116
4
3
112
2
104
1
100
108
Prof. Rodrigo de Souza Couto
Vetores Bidimensionais:
Matrizes
• Vetor bidimensional (ou matriz)
– Elementos armazenados de forma contínua
• Linha a linha
– Alocação Estática
124
int m[3][2] = {{1,2},{3,4},{5,6}}
m[i][j]
i
j
1
2
3
4
5
6
Primeiro elemento: m[0]0]
Último elemento: m[2][1]
Computadores Digitais II– DETEL-FEN/UERJ
m
6
120
5
116
4
3
112
2
104
1
100
108
Prof. Rodrigo de Souza Couto
Vetores Bidimensionais:
Matrizes
• Variável m do exemplo representa um ponteiro para o
primeiro “vetor-linha”
– m[1] é um ponteiro para o segundo “vetor-linha”
– m[2] é um ponteiro para o terceiro “vetor-linha”
124
int m[3][2] = {{1,2},{3,4},{5,6}}
6
120
m[2]
5
116
112
m[1]
4
3
2
104
1
100
m
Computadores Digitais II– DETEL-FEN/UERJ
108
Prof. Rodrigo de Souza Couto
Vetores Bidimensionais:
Matrizes
• Outra Formas de inicialização
– Explícita
int m[3][2] = {{1,2},{3,4},{5,6}}
– Sequencial
int m[3][2] = {1,2,3,4,5,6}
– Omissão do número de linhas
• Número de colunas sempre é obrigatório
int m[][2] = {1,2,3,4,5,6}
Computadores Digitais II– DETEL-FEN/UERJ
Prof. Rodrigo de Souza Couto
Passagem de Matrizes para
Funções
• Declaração na função principal
float m[4][3];
• Parâmetro declarado como “vetor-linha”
void (...,float (*m)[3],...);
• Parâmetro declarado como matriz
void (...,float m[][3],...);
Primeira dimensão pode ser
sempre omitida
Matriz pode ser modificada
pela função
• Dentro da função a matriz é acessada com a
indexação dupla normal de matrizes
Computadores Digitais II– DETEL-FEN/UERJ
Prof. Rodrigo de Souza Couto
Mais Dimensões
• Exemplo de Declaração
int m[3][2][4][4][3];
• Exemplo de Passagem para função
void (...,int m[][2][4][4][3],...);
Compilador pode definir
limites para dimensões
Computadores Digitais II– DETEL-FEN/UERJ
Prof. Rodrigo de Souza Couto
Matrizes Dinâmicas
• Assim, como no caso de vetores, às vezes as
dimensões das matrizes são conhecidas apenas em
tempo de execução
• Em C, apenas vetores podem ser alocados
dinamicamente
Como posso alocar matrizes
dinamicamente ?
Computadores Digitais II– DETEL-FEN/UERJ
Prof. Rodrigo de Souza Couto
Matrizes Dinâmicas
• Soluções
– Matriz com vetor simples
• Ex: Matriz 2x2
– 2 primeiros elementos do vetor -> linha 1
– 2 últimos elementos do vetor -> linha 2
1
2
3
4
1
2 3
4
– Matriz com vetor de ponteiros
• Cada elemento do vetor é um ponteiro para outro vetor
– Cada vetor apontado é uma linha
Computadores Digitais II– DETEL-FEN/UERJ
Prof. Rodrigo de Souza Couto
Matrizes Dinâmicas com
Vetor Simples
• Matriz com vetor simples
– Matriz m[i][j] com n colunas mapeada em um vetor v[k]
• k = i*n + j
j=1
i=2
a
p
c
d
e
f
g
r
z
x
o
b
a
p
c
d e
f
g
r
z
x
o
b
k = i*n + j = 2*4 + 1 = 9
Computadores Digitais II– DETEL-FEN/UERJ
Prof. Rodrigo de Souza Couto
Matrizes Dinâmicas com
Vetor Simples
• Trecho de código para matriz com m linhas e n colunas
float a;
float *mat;
...
mat = (float*) malloc(m*n*sizeof(float));
a = mat[i*n + j];
...
Veja que a notação não é
intuitiva, como era no caso
de uma matriz estática
Computadores Digitais II– DETEL-FEN/UERJ
Acesso ao elemento m[i][j]
Prof. Rodrigo de Souza Couto
Exercício
• Crie uma função que retorne um ponteiro para a
matriz transposta de uma dada matriz
– Matriz transposta t
• matrizT[j][i] = mat[i][j]
– Matriz transposta deve ser alocada dinamicamente
dentro da função
– Matriz recebida foi alocada na função principal como um
vetor
– Protótipo da função
float* transposta(int nrLinhas, int nrColunas, float* mat);
Computadores Digitais II– DETEL-FEN/UERJ
Prof. Rodrigo de Souza Couto
Exercício: Resposta
float* transposta(int nrLinhas, int nrColunas, float* mat){
int i, j;
float *matrizT;
/*Aloca matriz transposta*/
matrizT = (float*)malloc(nrColunas*nrLinhas*sizeof(float));
/*Preenche a matriz*/
for (i=0; i<nrLinhas; i++)
for (j=0; j< nrColunas; j++)
matrizT[j*nrLinhas + i] = mat[i*nrColunas + j];
return matrizT;
}
Computadores Digitais II– DETEL-FEN/UERJ
Prof. Rodrigo de Souza Couto
Matrizes Dinâmicas com
Vetor de Ponteiros
• Cada elemento do vetor armazena o endereço do
primeiro elemento de cada linha da matriz
j=1
j=1
i=2
a
p
c
d
e
f
g
r
z
x
o
b
Computadores Digitais II– DETEL-FEN/UERJ
i=2
a
p
c
d
e
f
g
r
z
x
o
b
Prof. Rodrigo de Souza Couto
Matrizes Dinâmicas com
Vetor de Ponteiros
• Trecho de código para matriz com m linhas e n colunas
int i;
float a;
float **mat; /*Indica um vetor para ponteiros*/
...
mat = (float**) malloc(m*sizeof(float*));
for (i=0; i<m; i++)
mat[i] = (float*) malloc(n*sizeof(float));
a = mat[2][3];
...
Acesso ao elemento mat[2][3]
Grande vantagem do vetor de
ponteiros: Matrizes podem ser
tratadas como no caso
estático!
Computadores Digitais II– DETEL-FEN/UERJ
Prof. Rodrigo de Souza Couto
Matrizes Dinâmicas com
Vetor de Ponteiros
• Liberação de memória
– Cada linha tem que ser liberada antes de se liberar o
vetor de ponteiros
...
for (i=0; i<m; i++)
free(mat[i]);
free(mat);
...
Computadores Digitais II– DETEL-FEN/UERJ
Prof. Rodrigo de Souza Couto
Exercício
• Como no exercício anterior, crie uma função que
retorne um ponteiro para a matriz transposta de uma
dada matriz
– Matriz transposta t
• matrizT[j][i] = mat[i][j]
– Matriz transposta deve ser alocada dinamicamente
dentro da função
– Matriz recebida foi alocada na função principal como um
vetor de ponteiros
– Protótipo da função
float** transposta(int nrLinhas, int nrColunas, float** mat);
Computadores Digitais II– DETEL-FEN/UERJ
Prof. Rodrigo de Souza Couto
Exercício: Resposta
float** transposta(int nrLinhas, int nrColunas, float** mat){
int i, j;
float **matrizT;
/*Aloca matriz transposta*/
matrizT = (float*)malloc(nrColunas*sizeof(float*));
for (i=0; i<nrColunas; i++)
matrizT[i] = (float*)malloc(nrLinhas*sizeof(float));
/*Preenche a matriz*/
for (i=0; i<nrLinhas; i++)
for (j=0; j< nrColunas; j++)
matrizT[j][i] = mat[i][j];
return matrizT;
}