9/8/2005 (c) Dept. Informtica - PUC-Rio 1
Estruturas de Dados
Mdulo 6 Matrizes
9/8/2005 (c) Dept. Informtica - PUC-Rio 2
Referncias
Waldemar Celes, Renato Cerqueira, Jos Lucas Rangel, Introduo a Estruturas de Dados, Editora Campus (2004)Captulo 6 Matrizes
9/8/2005 (c) Dept. Informtica - PUC-Rio 3
Tpicos
Alocao esttica versus dinmica Vetores bidimensionais matrizes Matrizes dinmicas Operaes com matrizes Representao de matrizes simtricas
9/8/2005 (c) Dept. Informtica - PUC-Rio 4
Alocao Esttica versus Dinmica
Alocao esttica de vetor: necessrio saber de antemo a dimenso mxima do vetor varivel que representa o vetor armazena o endereo ocupado
pelo primeiro elemento do vetor vetor declarado dentro do corpo de uma funo no pode ser
usado fora do corpo da funo
#define N 10int v[N];
9/8/2005 (c) Dept. Informtica - PUC-Rio 5
Alocao Esttica versus Dinmica
Alocao dinmica de vetor: dimenso do vetor pode ser definida em tempo de execuo varivel do tipo ponteiro recebe o valor do endereo do primeiro
elemento do vetor rea de memria ocupada pelo vetor permanece vlida at que
seja explicitamente liberada (atravs da funo free) vetor alocado dentro do corpo de uma funo pode ser usado fora
do corpo da funo, enquanto estiver alocado
int* v;
v = (int*) malloc(n * sizeof(int));
9/8/2005 (c) Dept. Informtica - PUC-Rio 6
Alocao Esttica versus Dinmica
Funo realloc: permite re-alocar um vetor preservando o contedo dos
elementos, que permanecem vlidos aps a re-alocao Exemplo:
m representa a nova dimenso do vetor
v = (int*) realloc(v, m*sizeof(int));
9/8/2005 (c) Dept. Informtica - PUC-Rio 7
Vetores Bidimensionais - Matrizes
Vetor bidimensional (ou matriz):float m[4][3] = {{ 5.0,10.0,15.0},
{20.0,25.0,30.0},{35.0,40.0,45.0},{50.0,55.0,60.0}};
5.0 10.0 15.0 20.0 25.0 30.035.0 40.0 45.050.0 55.0 60.0
j
i
60.0 55.0 50.0 45.0 40.0 35.030.0 25.0 20.015.0 10.0 5.0 104
152float m[4][3] = {{ 5.0,10.0,15.0},
{20.0,25.0,30.0},{35.0,40.0,45.0},{50.0,55.0,60.0}};
5.0 10.0 15.0 20.0 25.0 30.035.0 40.0 45.050.0 55.0 60.0
j
i
60.0 55.0 50.0 45.0 40.0 35.030.0 25.0 20.015.0 10.0 5.0 104
15260.0 55.0 50.0 45.0 40.0 35.030.0 25.0 20.015.0 10.0 5.0 104
152
9/8/2005 (c) Dept. Informtica - PUC-Rio 8
Vetores Bidimensionais - Matrizes
Vetor bidimensional (ou matriz): declarado estaticamente elementos acessados com indexao dupla m[ i ][ j ]
i acessa a linha e j acessa a coluna indexao comea em zero:
m[0][0] o elemento da primeira linha e primeira coluna varivel representa um ponteiro para o primeiro vetor-linha matriz tambm pode ser inicializada na declarao
9/8/2005 (c) Dept. Informtica - PUC-Rio 9
Vetores Bidimensionais - Matrizes
Passagem de matrizes para funes:declarao da matriz na funo principal:
float mat[4][3]
prottipo da funo (opo 1): parmetro declarado como vetor-linha
void f (..., float (*mat)[3], ...);
prottipo da funo (opo 2): parmetro declarado como matriz, omitindo o nmero de linhas
void f (..., float mat[ ][3], ...);
9/8/2005 (c) Dept. Informtica - PUC-Rio 10
Matrizes Dinmicas
Limitaes: alocao esttica de matriz:
necessrio saber de antemo suas dimenses
alocao dinmica de matriz: C s permite alocao dinmica de conjuntos unidimensionais necessrio criar abstraes conceituais com vetores
para representar matrizes (alocadas dinamicamente)
9/8/2005 (c) Dept. Informtica - PUC-Rio 11
Matrizes Dinmicas
Matriz representada por um vetor simples: conjunto bidimensional representado em vetor unidimensional
estratgia: primeiras posies do vetor armazenam elementos da primeira linha seguidos dos elementos da segunda linha, e assim por diante
exige disciplina para acessar os elementos da matriz
9/8/2005 (c) Dept. Informtica - PUC-Rio 12
Matrizes Dinmicas
Matriz representada por um vetor simples (cont.): matriz mat com n colunas representada no vetor v:
mat[ i ][ j ] mapeado em v[ k ] onde k = i * n + j
a b c de f g hI j k l
j=2
i=1
a b c d e f g h I j k l
k = i*n+j = 1*4+2 = 6
a b c de f g hI j k l
j=2
i=1
a b c d e f g h I j k l
k = i*n+j = 1*4+2 = 6
9/8/2005 (c) Dept. Informtica - PUC-Rio 13
Matrizes Dinmicas
Matriz representada por um vetor simples (cont.): mat[ i ][ j ] mapeado em v[ i * n + j ]
float *mat; /* matriz m x n representada por um vetor */...
mat = (float*) malloc(m*n*sizeof(float));
9/8/2005 (c) Dept. Informtica - PUC-Rio 14
Matrizes Dinmicas
Matriz representada por um vetor de ponteiros: cada elemento do vetor armazena o endereo
do primeiro elemento de cada linha da matriz
a b c de f g hI j k l
j=2
i=1
a b c d
e f g h
I j k l
j=2
i=1
a b c de f g hI j k l
j=2
i=1
a b c d
e f g h
I j k l
j=2
i=1
9/8/2005 (c) Dept. Informtica - PUC-Rio 15
Operaes com Matrizes
Exemplo funo transposta: entrada: mat matriz de dimenso m x n sada: trp transposta de mat, alocada dinamicamente
Q a matriz transposta de M se e somente se Qij = Mji
Soluo 1: matriz alocada como vetor simples Soluo 2: matriz alocada como vetor de ponteiros
9/8/2005 (c) Dept. Informtica - PUC-Rio 16
/* Soluo 1: matriz alocada como vetor simples */float* transposta (int m, int n, float* mat){
int i, j;float* trp;
/* aloca matriz transposta com n linhas e m colunas */trp = (float*) malloc(n*m*sizeof(float));
/* preenche matriz */for (i=0; i
9/8/2005 (c) Dept. Informtica - PUC-Rio 17
/* Soluo 2: matriz alocada como vetor de ponteiros */float** transposta (int m, int n, float** mat){
int i, j;float** trp;
/* aloca matriz transposta com n linhas e m colunas */trp = (float**) malloc(n*sizeof(float*));for (i=0; i
9/8/2005 (c) Dept. Informtica - PUC-Rio 18
Representao de Matrizes Simtricas
Matriz simtrica n x n: mat uma matriz simtrica sse
mat[ i ][ j ] = mat[ j ][ i ] estratgia de armazenamento:
basta armazenar os elementos da diagonal e metade dos elementos restantes, por exemplo, os elementos abaixo da diagonal, ou seja, mat[ i ][ j ], onde i > j
em lugar de n2 valores, armazena-se apenas s valores, onde:
(1 elemento da primeira linha, 2 elementos da segunda, 3 da terceira, ... )2
)1(...21 +=+++= nnns
10967984564237531
9/8/2005 (c) Dept. Informtica - PUC-Rio 19
Representao de Matrizes Simtricas
Exemplo: funo para criar matriz quadrada simtrica funo para, dada uma matriz j criada, acessar seus elementos
isola o fato da matriz no estar explicitamente toda armazenada permite teste adicional para evitar acessos invlidos:
verifica se os ndices representam elementos da matriz
9/8/2005 (c) Dept. Informtica - PUC-Rio 20
Representao de Matrizes Simtricas
Soluo 1: matriz alocada como vetor simples funo para criar matriz quadrada simtrica
conforme discutido anteriormente
funo para acessar os elementos da matriz acesso a elemento mat[ i,j ] acima da diagonal (ij) salta-se os elementos das linhas superiores, ou seja,
1+2+...+i = i*(i+1)/2 elementos utiliza-se o ndice j para acessar a coluna
acesso a elemento mat[ i,i ] na diagonal: retorna o elemento representado (como acima)
10967984564237531
9/8/2005 (c) Dept. Informtica - PUC-Rio 21
/* Soluo 1: matriz alocada como vetor simples */float* cria (int n){
int s = n*(n+1)/2;float* mat = (float*) malloc(s*sizeof(float));return mat;
}
9/8/2005 (c) Dept. Informtica - PUC-Rio 22
/* Soluo 1: matriz alocada como vetor simples */float acessa (int n, float* mat, int i, int j){
int k; /* ndice do elemento no vetor */
if (i=n || j=n) {printf("Acesso invlido!\n);exit(1);
}if (i>=j)
k = i*(i+1)/2 + j; /* acessa elemento representado */else
k = j*(j+1)/2 + i; /* acessa elemento simtrico */return mat[k];
}
9/8/2005 (c) Dept. Informtica - PUC-Rio 23
Representao de Matrizes Simtricas
Soluo 2: matriz alocada como vetor de ponteiros funo para criar matriz quadrada simtrica
primeira linha representada por um vetor de 1 elemento, segunda linha representada por um vetor de 2 elementose assim por diante
funo para acessar os elementos da matriz acesso aos elementos natural cuidado de no acessar diretamente elementos
que no estejam explicitamente alocados (isto , elementos com i
9/8/2005 (c) Dept. Informtica - PUC-Rio 24
/* Soluo 2: matriz alocada como vetor de ponteiros */float** cria (int n){
int i;float** mat = (float**) malloc(n*sizeof(float*));for (i=0; i
9/8/2005 (c) Dept. Informtica - PUC-Rio 25
/* Soluo 2: matriz alocada como vetor de ponteiros */float acessa (int n, float** mat, int i, int j){
if (i=n || j=n) {printf("Acesso invlido!\n);exit(1);
}if (i>=j)
return mat[ i ] [ j ]; /* acessa elemento representado */else
return mat[ j ][ i ]; /* acessa elemento simtrico */}
9/8/2005 (c) Dept. Informtica - PUC-Rio 26
ResumoMatriz representada por vetor bidimensional esttico:
elementos acessados com indexao dupla m[ i ][ j ]
Matriz representada por um vetor simples:conjunto bidimensional representado em vetor unidimensional
Matriz representada por um vetor de ponteiros:cada elemento do vetor armazena o endereo do primeiro elemento de cada linha da matriz
Funo alicional para gerncia de memria:realloc permite re-alocar um vetor preservando o contedo dos
elementos, que permanecem vlidos aps a re-alocao
Recommended