MC102MN
Introdução a Algoritmos e programação de computadores
Aula XIII, matrizes
Uma matriz em C parece ser um vetor de vetores, mas é algo um pouco mais complexo. Existem dois jeitos de se lidar com matrizes em C. O primeiro só funciona com matrizes de tamanho fixo mas é mais fácil de entender e implementar, enquanto o segundo funciona com matrizes arbitrárias mas é mais complexo.
O jeito mais simples de declarar matrizes em C é lembrar que o conceito de matriz é um vetor de vetores, e C te deixa expressar isso naturalmente. Para declarar uma matriz assim, faça
<tipo> <nome>[n][m];
Isso pode ser extendido para valores arbitrários de n e m.
Matrizes assim em C são que nem vetores, mas mais complicadas. Por exemplo, o seguintes códigos funcionam:
void imprime_mat(int x[3][3], int n) {
printf("%d ", x[i][j]);
int mat[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
imprime_mat(mat, 3);
void imprime_mat(int x[][3], int n) {
mas os seguintes dão erro de compilação:
void imprime_mat(int x[][], int n) {
void imprime_mat(int *x[], int n) {
Efetivamente, uma função que usa matrizes em C dessa forma vai necessariamente precisar conhecer em tempo de compilação o tamanho da matriz. Caso isso não aconteça, o compilador não consegue gerar código para acessá-la. Isso é por causa do layout de memória que C usa. escrever o nome da matriz em C é um ponteiro para o primeiro elemento dela, mas esse ponteiro não existe na memória, então não é possível passar um ponteiro.
Então o jeito mais simples de lidar com matrizes é declarar um vetor de vetores, mas isso tem seus problemas.
O segundo jeito
O segundo jeito é declarar um vetor para guardar todos os elementos da matriz e fazer você mesmo as contas para acessá-los. Uma matriz de dimensão n x m tem n*m elementos. Se você escolher colocar as linhas da matriz uma depois da outra na memória, você pode então saber que o elemento (i,j) da matriz vai ficar na posição m*i + j. Por isso era necessário especificar, ao passar a matriz pra função, quantas colunas ela tinha.
Se vc faz essa conta, o código para acessar o elemento i,j da matriz então fica
mat[m*i + j]
Assim podemos fazer um código para somar duas matrizes da seguinte forma (guardando o resultado numa terceira):
void soma_mat(int *a, int *b, int *c, int linhas, int colunas) {
int i,j, tmp;
for (i = 0; i < linhas; ++i) {
for (j = 0; j < colunas; ++j) {
tmp = colunas*i+j;
c[tmp] = a[tmp] + b[tmp];
Ou fazer o código para multiplicar uma matriz por um vetor
double mult_mat_vec(double *mat, int linhas, int colunas, double *vec, double *res) {
s += mat[colunas*i+j]*vec[j];
res[i] = s;
Um armengue
Se você quiser mesmo acessar os elementos de uma matriz como
mat[i][j]
tem um jeito para resolver isso. Basta notar que para a função você vai passar um ponteiro para um ponteiro (já que os colchetes aparecem duas vezes). Então você quer dois vetores: um para os elementos da matriz e um para os ponteiros para o primeiro elemento de cada linha. Ou seja:
int mat[n][m];
int *p[n], i;
for (i = 0; i < n; ++i) p[i] = &mat[i][0];
com isso você pode declarar uma função para receber uma matriz como
int func(int **mat, int linhas, int colunas) {
só que você tem que passar p para a função, e não m, já que é p que tem os ponteiros. Podemos ver que isso funciona fazendo a dereferência dos ponteiros manualmente.
Resolvendo um sistema linear
Vamos assumir que temos um sistema linear com n equações e n variáveis. Podemos representar esse sistema como uma matrix n por n+1 (já que temos que considerar os termos constantes do Ax = b). Um jeito simples de resolver esse sistema (e numericamente instável, mas fácil de implementar) é a eliminação gaussiana. Ela consiste de, para cada linha da matriz,
transformar o primeiro coeficiente não-zero nessa linha para 1 (dividindo essa linha pelo valor desse coeficiente)
zerar todos os outros coeficientes dessa coluna com somas de vetores multiplicadas.
Para isso vamos usar uma função que usa ponteiros e vetores:
void soma_const(double *a, double *b, int n, double c, double d, double *res) {
res[i] = c*a[i]+d*b[i];
O algoritmo de eliminação gaussiana então é (assumindo que não temos zeros na matriz):
void inverte_m(double *mat, int n) {
int i, j, m = n+1;
soma_const(mat+m*i, mat+m*i, m, 1./mat[m*i+i], 0, mat+m*i); // a = a/a[i] + 0*a
soma_const(mat+m*i, mat+m*j, m, -mat[j*m+i], 1, mat+m*j); // b = b - a*b[i]
printf("X%d = %lf\n", i, mat[m*i+n]);
E assim podemos resolver um sistema linear de n variáveis, assumindo que não temos nenhum problema de super ou sub determinação.
Traduzir o código de invertem para funcionar com matrizes de tamanho fixo como é o tipo 1 dessa aula.