capitulo06a

9/8/2005 (c) Dept. Informtica - PUC-Rio 1

Estruturas de Dados

Mdulo 6 Matrizes


Referncias

Waldemar Celes, Renato Cerqueira, Jos Lucas Rangel, Introduo a Estruturas de Dados, Editora Campus (2004)Captulo 6 Matrizes


Tpicos

Alocao esttica versus dinmica Vetores bidimensionais matrizes Matrizes dinmicas Operaes com matrizes Representao de matrizes simtricas


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];



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));



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));


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



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



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], ...);


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)


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


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


j=2

i=1

a b c d e f g h I j k l

k = i*n+j = 1*4+2 = 6


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));


Matrizes Dinmicas

Matriz representada por um vetor de ponteiros: cada elemento do vetor armazena o endereo

do primeiro elemento de cada linha da matriz


j=2

i=1

a b c d

e f g h

I j k l

j=2

i=1


j=2

i=1

a b c d

e f g h

I j k l

j=2

i=1


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


/* 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


/* 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


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



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



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


/* 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;

}


/* 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];

}



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


/* 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


/* 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 */}


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

Documents

capitulo06a