resultado da execução de matriz.c

fabio@fabio-System-Product-Name:~/Desktop/array$ gcc matriz.c fabio@fabio-System-Product-Name:~/Desktop/array$ ./a.out 1000 1012 1024 1036 1048 1060 1072 1084 1096 1108 1120 1132 1001 1013 1025 1037 1049 1061 1073 1085 1097 1109 1121 1133 1002 1014 1026 1038 1050 1062 1074 1086 1098 1110 1122 1134 1003 1015 1027 1039 1051 1063 1075 1087 1099 1111 1123 1135 1004 1016 1028 1040 1052 1064 1076 1088 1100 1112 1124 1136 1005 1017 1029 1041 1053 1065 1077 1089 1101 1113 1125 1137 1006 1018 1030 1042 1054 1066 1078 1090 1102 1114 1126 1138 1007 1019 1031 1043 1055 1067 1079 1091 1103 1115 1127 1139 1008 1020 1032 1044 1056 1068 1080 1092 1104 1116 1128 1140 1009 1021 1033 1045 1057 1069 1081 1093 1105 1117 1129 1141 0x7fff890a3870 0x7fff890a38a0 0x7fff890a38d0 0x7fff890a3900 0x7fff890a3930 0x7fff890a3960 0x7fff890a3990 0x7fff890a39c0 0x7fff890a39f0 0x7fff890a3a20 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 fabio@fabio-System-Product-Name:~/Desktop/array$

Matrizes estruturadas (da apostila de W. Honda e I. Paraboni

   O objetivo deste post é esclarecer idéias que fazem matrizes esparsas (no caso estruturadas) tão importantes.
   A álgebra de matrizes (ou álgebra linear...) é aplicada para modelar ou para simular os mais variados processos dentre eles: processos químicos (sistemas de reações químicas que resultam em um ou mais produtos de grande valor), mecânica de fluidos (consequentemente previsão do tempo - com impacto na agricultura), circuitos elétricos (desde distribuição de energia até projeto e simulação de circuitos integrados), processamento de imagens (imagens médicas, realidade virtual, jogos,...).
    Nestes processos milhares ou até milhões de sistemas lineares com milhares de variáveis precisam ser resolvidos. É algo que um computador faz, mas precisa de muita memória e capacidade de processamento, OU de algoritmos que aproveitam a estrutura do problema (das matrizes) para economizar memória e processamento.
    Em problemas muito grandes é até comum que as matrizes que os representam tenham muitos elementos nulos (da ordem de 90% da matriz) que poderiam não ser representados e com isso não ocupar memória.
    Deve-se considerar também a ordem e frequência com que os elementos da matriz serão visitados. Por exemplo em um produto de matrizes: A x B, A os elementos de A serão varridos por linhas e os de B por colunas, em ordem. Ligar os elementos não nulos nas linhas e nas colunas (listas ligadas) pode ser uma boa estratégia para poupar memória e operações. Algo similar ocorre na fatoração LU (triangularização de matrizes) e na fatoração QR - estas duas usadas para resolver sistemas lineares.
    Na fatoração LU, as matriz M é fatorada em duas: L - triangular inferior e U - triangular superior. Em geral as duas são armazenadas juntas (é o que faz o algoritmo de Gauss), mas apenas U é necessária para resolver o sistema. Neste caso seria vantajoso armazenar apenas U. Existe uma forma de armazenar e indexar matrizes triangulares.
   Da mesma forma, existem formas de armazenar matrizes diagonais e matrizes tridiagonais.


Matriz diagonal
(a) tamanho do vetor de alocação: n
(b) elementos não nulos m(i,j) são tais que i == j;
(c) endereçamento: m(i,j) == V(i) ou j...

Em código:

double *criaMatrizDiagonal (int n) {
// cria uma matriz diagonal n x n
    return malloc (n*sizeof (double));   // usa só n elementos
}

double leMatrizDiagonal (double *M, int i, int j) {
    if (i==j) return M[i];
    return 0.0;
}

Matriz tridiagonal
(a) tamanho do vetor de alocação: 3n – 2
(b) elementos não nulos m(i,j) são tais que |i –j| <= 1
(c) endereçamento ordenada por linhas,m[i, j ] == v[(2*i+ j –2)]

Em código:

double *criaMatrizTridiagonal (int n) {
// cria uma matriz tridiagonal n x n
    return malloc ((3*n-2)*sizeof (double));   // usa só 3n-2 elementos
}

double leMatrizTridiagonal (double *M, int i, int j) {
    if (abs(i-j)<=1) return M[(2*i+j-2)];
    return 0.0;
}


Matriz triangular inferior
a) tamanho do vetor de alocação (supondo matriz quadrada)- Há n^2 elementos na matriz;-Há n elementos na diagonal principal; - Logo, há (n^2+ n) / 2 elementos não nulos.
(b) elementos não nulos: Na triangular superior, m[i,j] == 0 se i < j. Na triangular inferior, m[i,j] == 0 se i>j.
(c) endereçamento:
    Triangular superior ordenada por colunas, m[i, j ] == v[(i^2-i) / 2+ j]
    Triangular inferior ordenada por linhas, m[i, j ] == v[(j^2-j) / 2+ i ]

Em código:

double *criaMatrizTriangularSuperior (int n) {
// cria uma matriz Triangular Superior n x n
    return malloc ((n*(n+1)/2)*sizeof (double));   // usa só (n^2+n)/2 elementos
}

double leMatrizTriangularInferior (double *M, int i, int j) {
    if (i>=j) return M[(i*i-i)/2+j)];
    return 0.0;
}

Nota: usando interfaces e vinculação tardia a chamada dos métodos pode ser unificada e a implementação da estrutura de dados pode ser ocultada, criando uma interface única independente da estrutura subjacente.

Matriz em C - entendendo a estrutura

#include <stdio.h>
#include <stdlib.h>

void main (void) {
   int m[10][12];
   int i, j;
   /*Usa uma funcao para mapear uma matriz 10x12 no array de 120 elementos.*/
   for (i=0;i<10;i++) {
      for (j=0;j<12;j++) {
         m[i][j]=i+j*12+1000;
      }
   }
   for (i=0;i<10;i++) {
      for (j=0;j<12;j++) {
         printf ("%d ", m[i][j]);
      }
   }
   /*Tentando hackear a estrutura:*/
   for (i=0;i<10;i++) {
      printf ("%p ", m[i]);  /* eh ponteiro?*/
   }
   /*Sim! mas veja os valores: eles saltam de 48 em 48 bytes - 
     a região de memória eh continua! */
   /* o conteudo eh ponteiro ou eh inteiro? */
#if 0
   for (i=0;i<10;i++) {
      printf ("%p ", *(m[i]));  /* o conteúdo eh ponteiro?*/
   }
/*
fabio@fabio-virtual-machine:~/Documents/array$ gcc matriz.c 
matriz.c: In function ‘main’:
matriz.c:26:15: warning: format ‘%p’ expects argument of type ‘void *’, but argument 2 has type ‘int’ [-Wformat=]
       printf ("%p ", *(m[i]));  
               ^
o erro indica que o conteúdo é inteiro!!!!
*/
#endif
   for (i=0;i<10;i++) {
      printf ("%d ", *(m[i]));  /* eh inteiro entao...*/
   }

}

array em C - diferentes formas de acesso

#include <stdio.h>
#include <stdlib.h>

void main (void) {
   int v[120];
   int i;
#if 0
   /*Acesso usual*/
   for (i=0;i<120;i++) {
      v[i]=i+1000;
   }
   for (i=0;i<120;i++) {
      printf ("%d ", v[i]);
   }
#endif
#if 0
   /*Acesso por ponteiro: como o tipo do elemento eh declarado e a região de memória é contínua, entao o endereco do elemento pode ser calculado. */
   for (i=0;i<120;i++) {
      *(v+i)=i+1000;
   }
   for (i=0;i<120;i++) {
      printf ("(%p, %d) ", v+i, *(v+i)); //imprime endereco e valor armazenado
   }
#endif
   /*Usa uma funcao para mapear uma matriz 10x12 no array de 120 elementos.*/
   for (i=0;i<10;i++) {
      int j;
      for (j=0;j<12;j++) {
         v[i*12+j]=i+j*12+1000;
      }
   }
   for (i=0;i<10;i++) {
      int j;
      for (j=0;j<12;j++) {
         printf ("%d ", v[i*12+j]);
      }
   }
}