[APORTE] Matrices dinamicas en C/C++

[AlanChavez]

Este artículo lo hice para mi pagina web y decidi compartirlo en foros del web, porque es una pregunta recurrente. Aclaro que el codigo aqui expuesto, es codigo simplemente para demostrar el concepto y no debe usarse en producción.

Una pregunta recurrente en cualquier foro de programación es la implementación de las matrices dinámicas. Este concepto se encuentra muy mitificado, haciendolo pasar muchas veces como algo de alto nivel y muy sofisticado, el objetivo de este articulo es desmitificar dicho concepto y simplificarlo al máximo.


Memoria dinámica? Que es?

Si estás leyendo esto, es muy probable que la gran mayoría de tus programas hayas conocido la cantidad de datos a almacenar de antemano. Sin embargo en problemas reales, la mayoría de las ocasiones, desconocemos la cantidad de datos a almacenar, y tenemos que echar a andar diversos recursos que los lenguajes de programación nos ofrecen, para lidiar con este problema.

Uno de ellos, es la asignación dinámica de memoria, que nos permite asignar bloques de memoria, en tiempo de ejecución, para almacenar datos en dichos bloques.

Bueno ya se que es, ahora como la programo?

C++ nos brinda el operador new y delete que asignan y liberan la memoria de una zona denominada free store (Almacén libre). A diferencia de malloc() y free() en C, new y*delete de C++ implementados como operadores y son mas fiables ya que el compilador realiza verificación de tipos cada vez que un programa aloja memoria.

Existen dos maneras muy sencillas de implementar matrices dinamicas en C/C++, la primera es creando un arreglo dinamico, y dentro de cada casilla del arreglo dinamico, creamos otro arreglo dinamico, simulando una matriz dinamica. La segunda forma, es utilizando el concepto de filas de orden mayor (row major order) o columnas de orden mayor (column major order).

Opcion 1: Arreglo de arreglos dinamicos

Un arreglo dinámico, es un arreglo comun y corriente, cuya capacidad va incrementando conforme se le van agregando datos, asi que puede ser tan grande como la memoria lo permita.


Si creamos un arreglo dinamico, en cada una de las casillas, de un arreglo dinamico, entonces obtendremos una matriz dinámica


Implementación en C

Código c:

int **matriz;
int i, int filas_dinamicas, int columnas_dinamicas;
matriz = (int**) malloc(filas_dinamicas*sizeof(int));
    for(i=0;i<filas_dinamicas;i++)
    {
      matriz[i] = (int**)malloc(columnas_dinamicas*sizeof(int));
    }
 

Implementacion en C++

Código c++:

int **matriz;
int fila_dinamica;
int columna_dinamica;
matriz = new int *[fila_dinamica];
  for(int i = 0; i<=fila_dinamica; i++)
   {
     matriz[i] = new int[columna_dinamica];
   }
 

Opcion 2: Renglones o Columnas de orden mayor

Este método me parece que es aun mas sencillo que la implementación de un arreglo de arreglos, ya que es la manera en como el compilador almacena las matrices estaticas en la memoria. La memoria de la computadora no es capaz de alojar una matriz en filas y columnas, debido a que el acceso a la memoria es secuencial, por lo tanto el compilador debe descomponer la matriz en renglones o columnas, para que sean almacenadas secuencialmente en la memoria de la computadora.

Existen dos formas, almacenarlas por renglones o almacenarlas por columnas. El compilador de C/C++ asi como de la mayoría de los lenguajes de programación utilizan el método de renglones de orden mayor (row major order), ya que es la manera mas natural de leer una matriz, esto es, que el compilador va a almacenar renglon por renglon la matriz de manera secuencial, tal y como se muestra en la figura.


Una vez que hemos transformado nuestra Matriz, en un Arreglo, podemos accesar a cualquier posicion i,j de la matriz, mediante la formula mostrada en la imagen, la cual calcula el indice del array, en donde estará almacenado el valor de la posición i,j de una Matriz.



Indice = Fila*Numero de columnas + Columna



Implementación en C

Código c:

int *arreglo;
int k, int filas, int columnas,i,j;
arreglo = (int*) malloc(filas*columnas*sizeof(int));
   for(i=0;i<=3;i++)
   {
     for(j=0;j<=3;j++)
      {
        arreglo[k] = i*columnas + j;
       }
    }
 

Implementacion en C++

Código c++:

int *arreglo;
int filas, int columnas, int k;
arreglo = new int *[filas*columnas];
   for(int i = 0; i<=3; i++)
   {
     for(int j=0;j<=3;j++)
       {
         arreglo[k] = i*columnas + j;
       }
   }
 

El metodo de columnas de orden mayor, es muy similar al de renglones de orden mayor. La diferencia es que en lugar de almacenar las matrices renglon por renglon, lo hace columna por columna. Un lenguaje de programación que utiliza este acercamiento, es FORTRAN, al principio puede llegar a ser desafiante acostumbrarse a que FORTRAN, utiliza columnas de orden mayor (column major order) y el metodo de acceso es al reves del acostumbrado, almenos desde mi punto de vista, lo siento menos natural.

El indice del array para el metodo de columna mayor se puede calcular mediante la formula:



Indice = Columna*Numero de filas + Fila



Notas Finales

El articulo se encuentra orientado hacia programadores que ya saben como compilar y depurar un programa en C/C++, sin embargo cabe resaltar que los códigos mostrados son simplemente como demostración del concepto y una manera de implementación y no proponen una implementación ideal de éstos métodos.

Mi página web esta principalmente orientada al desarrollo de aplicaciones en Flash y ActionScript 3, sin embargo estaré escribiendo algunos artículos principalmente orientados hacia C/C++ principalmente programas implementando metodos numericos (interpolacion, extrapolacion, integracion y derivacion numerica, etc..)

Mi pagina web esta en mi firma, y en mi perfil :)