Método eficiente para almacenar una array triangular inferior utilizando el mapeo de columnas principales

Dada una array triangular inferior Mat[][] , la tarea es almacenar la array utilizando el mapeo de columnas principales .

Array triangular inferior: una array triangular inferior es una array cuadrada en la que la parte triangular inferior de una array consta de elementos distintos de cero y la parte triangular superior consta de 0 s. La array triangular inferior para una array 2D Mat[][] se define matemáticamente como:

• Si i < j , establece Mat[i][j] = 0 .
• Si i >= j , establece Mat[i][j] > 0 .

Ilustración:

5 × 5 array 2D 0s

array triangular inferior N

• Recuento de elementos distintos de cero = 1 + 2 + 3 + … + N = N * (N + 1) /2 .
• Recuento de 0 s = N ² – (N * (N + 1) /2 = (N * (N – 1)/2 .

Ahora veamos cómo representar arrays triangulares inferiores en el programa. Tenga en cuenta que se debe evitar almacenar 0 para reducir el consumo de memoria. Según lo calculado, para almacenar elementos distintos de cero, se necesita N*(N + 1)/2 espacio. Tomando el ejemplo anterior, N = 5 . Se requiere una array de tamaño 5 * (5 + 1)/2 = 15 para almacenar los elementos distintos de cero.

Ahora, los elementos de la array 2D se pueden almacenar en una array 1D, columna por columna, como se muestra a continuación:

Array para almacenar Elementos Triangulares Inferiores

una estera[i][j]

Estera[i][j]

A continuación se muestra la implementación del artículo anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
#include<stdio.h>
using namespace std;
 
// Dimensions of the matrix
const int N = 5;
 
// Structure of a memory
// efficient matrix
struct Matrix {
    int* A;
    int size;
};
 
// Function to set the
// values in the Matrix
void Set(struct Matrix* m, int i,
         int j, int x)
{
    if (i >= j)
        m->A[((m->size)*(j-1)-(((j-2)
              *(j-1))/2)+(i-j))] = x;
}
 
// Function to store the
// values in the Matrix
int Get(struct Matrix m, int i, int j)
{
    if (i >= j)
        return m.A[((m.size)*(j-1)-(((j-2)
                   *(j-1))/2)+(i-j))];
    else
        return 0;
}
 
// Function to display the
// elements of the matrix
void Display(struct Matrix m)
{
    // Traverse the matrix
    for (int i = 1; i <= m.size; i++)
    {
        for (int j = 1; j <= m.size; j++)
        {
            if (i >= j)
                cout<< m.A[((m.size)*(j-1)-(((j-2)
                       *(j-1))/2)+(i-j))] <<" ";
            else
                cout<<"0 ";
        }
        cout<<endl;
    }
}
 
 
// Function to generate an efficient matrix
struct Matrix createMat(int Mat[N][N])
{
    // Declare efficient Matrix
    struct Matrix mat;
   
    // Initialize the Matrix
    mat.size = N;
    mat.A = (int*)malloc(
        mat.size * (mat.size + 1) / 2
        * sizeof(int));
   
    // Set the values in matrix
    for (int i = 1; i <= mat.size; i++) {
   
        for (int j = 1; j <= mat.size; j++) {
   
            Set(&mat, i, j, Mat[i - 1][j - 1]);
        }
    }
   
    // Return the matrix
    return mat;
}
 
 
// Driver Code
int main()
{
   
    // Given Input
    int Mat[5][5] = { { 1, 0, 0, 0, 0 },
                      { 1, 2, 0, 0, 0 },
                      { 1, 2, 3, 0, 0 },
                      { 1, 2, 3, 4, 0 },
                      { 1, 2, 3, 4, 5 } };
     
    // Function call to create a memory
    // efficient matrix
    struct Matrix mat = createMat(Mat);
   
    // Function call to
      // print the Matrix
    Display(mat);
 
    return 0;
}
 
// This code is contributed by rrrtnx.

// C program for the above approach
#include <stdio.h>
#include <stdlib.h>
 
// Dimensions of the matrix
const int N = 5;
 
// Structure of a memory
// efficient matrix
struct Matrix {
    int* A;
    int size;
};
 
// Function to set the
// values in the Matrix
void Set(struct Matrix* m, int i,
         int j, int x)
{
    if (i >= j)
        m->A[((m->size)*(j-1)-(((j-2)
              *(j-1))/2)+(i-j))] = x;
}
 
// Function to store the
// values in the Matrix
int Get(struct Matrix m, int i, int j)
{
    if (i >= j)
        return m.A[((m.size)*(j-1)-(((j-2)
                   *(j-1))/2)+(i-j))];
    else
        return 0;
}
 
// Function to display the
// elements of the matrix
void Display(struct Matrix m)
{
    // Traverse the matrix
    for (int i = 1; i <= m.size; i++)
    {
        for (int j = 1; j <= m.size; j++)
        {
            if (i >= j)
                printf("%d ",
                       m.A[((m.size)*(j-1)-(((j-2)
                       *(j-1))/2)+(i-j))]);
            else
                printf("0 ");
        }
        printf("\n");
    }
}
 
 
// Function to generate an efficient matrix
struct Matrix createMat(int Mat[N][N])
{
    // Declare efficient Matrix
    struct Matrix mat;
   
    // Initialize the Matrix
    mat.size = N;
    mat.A = (int*)malloc(
        mat.size * (mat.size + 1) / 2
        * sizeof(int));
   
    // Set the values in matrix
    for (int i = 1; i <= mat.size; i++) {
   
        for (int j = 1; j <= mat.size; j++) {
   
            Set(&mat, i, j, Mat[i - 1][j - 1]);
        }
    }
   
    // Return the matrix
    return mat;
}
 
 
// Driver Code
int main()
{
    // Given Input
    int Mat[5][5] = { { 1, 0, 0, 0, 0 },
                      { 1, 2, 0, 0, 0 },
                      { 1, 2, 3, 0, 0 },
                      { 1, 2, 3, 4, 0 },
                      { 1, 2, 3, 4, 5 } };
     
    // Function call to create a memory
    // efficient matrix
    struct Matrix mat = createMat(Mat);
   
    // Function call to
      // print the Matrix
    Display(mat);
 
    return 0;
}

1 0 0 0 0 
1 2 0 0 0 
1 2 3 0 0 
1 2 3 4 0 
1 2 3 4 5 

Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N ² )