ELC1066 - Estrutura de Dados
Primeiro Semestre de 20152
Professora: Juliana Kaizer Vizzotto
Matrizes Dinâmicas
- A linguagem C permite a criação de vetores bidimensionais,
declarados estaticamente. Por exemplo, para declarmos uma
matriz de valores reais com 4 linhas e 3 colunas, fazemos:
float mat[4][3];
Esta declaração reserva um espaço de memória necessário para armazenar os 12 elementos da matriz, que são armazenados de forma contínua, organizados linha a linha. - Os elementos da matriz são acessados com indexação dupla:
`mat[i][j]`
. O primeiro índice,`i`
, acessa a linha e o segundo,`j`
, acessa a coluna. Como em C a indexação começa em zero, o elemento da primeira linha e primeira coluna é acessado por`mat[0][0]`
. Após a declaração estática de uma matriz, a variável que representa a matriz,`mat`
no exemplo acima, representa um ponteiro para o primeiro vetor-linha, composto por 3 elementos. Com isto,`mat[1]`
aponta para o primeiro elemento do segundo vetor-linha, e assim por diante. - As matrizes também podem ser inicializadas na declaração:
float mat[4][3]=<{1,2,3},{4,5,6},{7,8,9},{10,11,12}>;
- Ou podemos inicializar sequencialmente:
float mat[4][3]=<1,2,3,4,5,6,7,8,9,10,11,12>;
- O número de elementos por linha pode ser omitido numa inicialização, mas o número de colunas deve, obrigatoriamente, ser
fornecido:
float mat[][3]=<1,2,3,4,5,6,7,8,9,10,11,12>;
Passagem de Matrizes para funções
- Conforme vimos acima, uma matriz criada estaticamente é
representada por um ponteiro para um vetor de elementos com o número de elementos da linha. Quando passamos uma matriz para uma
função, o parâmetro da função deve ser desse tipo.
Por exemplo, o protótipo de uma função que recebe a matriz declarada acima seria:
void f (..., float (*mat)[3],...);
Uma segunda opção é declarar o parâmetro como matriz, podendo omitir o número de linhas:void f (..., float mat[][3],...);
De qualquer forma, o acesso aos elementos da matriz dentro da função é feito da forma usual, com indexação dupla.
Matrizes Dinâmicas
- A linguagem C somente permite alocarmos dinamicamente conjuntos unidimensionais. Para trabalharmos com matrizes alocadas dinamicamente, temos que criar abstrações conceituais com vetores para representar conjuntos bidimensionais.
Matriz Representada por um Vetor Simples
- Conceitualmente, podemos representar uma matriz num vetor simples. Reservamos as primeiras posições do vetor para armazenar os elementos da primeira linha, seguidos dos elementos da segunda linha, e assim por diante. Como, de fato, trabalharemos com um vetor unidimensional, temos que criar uma disciplina para acessar os elementos da matriz representada conceitualmente.
- A estratégia de endereçamento para acessar os elementos é a seguinte: se quisermos acessar o que seria o elemento
`mat[i][j]`
de uma matriz, devemos acessar o elemento`v[i*n+j]`
, onde n representa o número de colunas da matriz. - Esta conta de endereçamento é intuitiva: se quiseremos acessar elementos da terceira (i=2) linha, temos que pular duas linhas de elementos (i*n) e depois indexar o elemento da linha com j.
- Com esta estratégia, a alocação da matriz recai numa
alocação de vetor que tem m*n elementos, onde m e n representam
as dimensões da matriz:
float *mat; ... mat = (float*) malloc(m*n sizeof(float)); ...
Matriz Representada por um Vetor de Ponteiros
- Nessa estratégia cada linha da matriz é representada por um vetor independente. A matriz é então representada por um vetor de vetores, ou vetor de ponteiros, no qual cada elemento armazena o endereço do primeiro elemento de cada linha.
- A alocação da matriz agora é mais elaborada. Primeiro
temos que alocar o vetor de ponteiros. Em seguida, alocamos cada uma das linhas da matriz, atribuindo seus endereços aos elementos do vetor de ponteiros criado:
int i; float **mat; /*matriz representada por vetor de ponteiros */ ... mat = (float**) malloc(m*sizeof(float*)); for(i =0;i<m;i++) m[i] = (float*) malloc(n*sizeof(float));
- A grande vantagem desta estratégia é que o acesso aos
elementos é feito da mesma forma que quando temos uma matriz criada
estaticamente, pois, se
`mat`
representa uma matriz alocada segundo esta estratégia,`mat[i]`
representa o ponteiro para o primeiro elemento da linha, e`mat[i][j]`
acessa o elemento da coluna j da linha i.
- A liberação do espaço de memória ocupado pela matriz também
exige a construção de um laço, pois temos que liberar cada linha
antes de liberar o vetor de ponteiros.
... for (i=0;i<m;i++) free(mat[i]); free(mat);
Links
Apostilas
- Algoritmos e Estrutura de Dados.
HONDA, W.Y. & PARABONI, I.
Livros
- Introdução a Estrutura de Dados.
CELES, W.; CERQUEIRA, R. & RANGEL, J.L. - Introduction to Algorithms
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein.