Matriz poco densa regular

Una matriz poco densa es aquella que está formada por elementos que en su mayoría son ceros. Este tipo de matrices son matrices cuadradas que se dividen en los siguientes tipos:

  • Matriz triangular superior
  • Matriz triangular inferior
  • Matriz tridiagonal

Matriz triangular superior

En este tipo de matriz los elementos iguales a cero se encuentran debajo de la diagonal principal. Ejemplo:

Matriz triangular superior

Para evitar el desperdicio de memoria que se ocasionaría al almacenar una matriz en donde la mayoría de los elementos son ceros, es conveniente traspasar a un arreglo unidimensional todos los elementos diferentes de cero.

El arreglo con los elementos distintos de cero de la matriz anterior es el siguiente:

Arreglo de la Matriz triangular superior

Una vez que hallamos vaciado la matriz  es indispensable conocer el lugar dentro del arreglo unidimensional en el cual quedaron situados los elementos, y esto se logra con la siguiente formula:

LOC(A[i,j])=base(A) + (n*(i-1)) – ((i-2)*(i-1))/2 + (j-1)

donde:

A=Matríz triangular superior
n=No. total de elementos
j= renglones
i=columnas

Matriz triangular inferior

En este tipo de matrices los elementos iguales a cero se encuentran por encima de la diagonal principal. Ejemplo:

Matriz triangular inferior

Una vez que vaciamos la matriz en un arreglo unidimensional, la formula para obtener las posiciones de los elementos es la siguiente:

Arreglo de la Matriz triangular inferior

LOC(A[i,j])=base(A) + ((i-1)*i)/2 + (j-1)

Matriz tridiagonal

En ésta, los elementos diferentes de cero se encuentran en la diagonal principal ó en las diagonales por debajo ó encima de ésta. Ejemplo:

Matriz tridiagonal

Y el arreglo con los elementos diferentes de cero correspondiente a esta matriz es el siguiente:

Arreglo de la Matriz triangular tridiagonal

La localización de los elementos distintos de cero en el arreglo unidimensional se realiza aplicando la siguiente formula:

LOC(A[i,j])=base(A) + 2*i + (j-3)

Fuente: Apunte de Estructura de Datos del Instituto tecnológico de la Paz

Publicado en Estructura de datos

Suscríbete:

who's online