Genere una array a partir de una array dispersa dada usando una lista enlazada y reconstruya la array dispersa

Dada una array dispersa mat[][] de dimensiones N*M , la tarea es construir y representar la array original utilizando una lista enlazada y reconstruir la array dispersa dada .

Ejemplos:

Entrada: mat[][] = {{0, 1, 0, 0, 0}, {0, 1, 0, 0, 0}, {0, 0, 2, 0, 0}, {0, 3, 0, 0, 4}, {0, 0, 5, 0, 0}}
Salida:
Representación de lista enlazada: (4, 2, 5) → (3, 4, 4) → (3, 1, 3) → ( 2, 2, 2) → (1, 1, 1) → (0, 1, 1) → NULL
Array original:
{{0, 1, 0, 0, 0}, 
{0, 1, 0, 0, 0 }, 
{0, 0, 2, 0, 0}, 
{0, 3, 0, 0, 4}
{0, 0, 5, 0, 0}}

Entrada: mat[][] = {{0, 0, 0, 4, 0}, {0, 1, 0, 0, 0}}
Salida:
Representación de lista enlazada: (1, 1, 1) → (0, 3, 4) → NULL
Array original:
{{0, 0, 0, 4, 0}, 
{0, 1, 0, 0, 0}}

Enfoque: el problema dado se puede resolver almacenando el índice de fila, el índice de columna , su valor y el siguiente puntero de todos los elementos distintos de cero en el Node de la lista vinculada. Siga los pasos a continuación para resolver el problema: 

• Para la construcción de la array dispersa utilizando una lista enlazada, recorra la array y, para cada elemento distinto de cero, cree un nuevo Node e inserte este Node recién creado al comienzo de la lista .
• Para la reconstrucción, cree una array 2D auxiliar de dimensiones N*M con todas las entradas como 0 , luego recorra la lista vinculada y actualice todos los elementos distintos de cero en esta array recién creada.

A continuación se muestra la implementación del enfoque anterior:

// C program for the above approach
 
#include <stdio.h>
#include <stdlib.h>
 
// Store the size of sparse matrix
#define R 5
#define C 5
 
// Linked list node
typedef struct SNode {
    int data;
    int Col;
    int Row;
    struct SNode* next;
} SparseNode;
 
// Store the head pointer of the linked
// list and the size of the matrix
typedef struct MNode {
    int Matrix[2];
    SparseNode* SNPTR;
} MatrixNode;
 
// Function to initialize the head of
// the linked list
MatrixNode* ConstructMNhead(
    MatrixNode* MNhead, SparseNode* SNhead)
{
 
    MNhead = (MatrixNode*)malloc(sizeof(MNhead));
 
    // Update the number of rows and
    // columns and update head pointer
    MNhead->Matrix[0] = R;
    MNhead->Matrix[1] = C;
    MNhead->SNPTR = SNhead;
 
    return MNhead;
}
 
// Function to create a new node
SparseNode* CreateList(int Row, int Col,
                       int data)
{
 
    // Create a new node
    SparseNode* New
        = (SparseNode*)malloc(sizeof(SparseNode));
 
    // Update the value and the row
    // and column index and set the
    // next pointer to NULL
    New->data = data;
    New->Col = Col;
    New->Row = Row;
    New->next = NULL;
 
    return New;
}
 
// Function to insert a node at the
// beginning of the  linked list
MatrixNode* AddInList(
    MatrixNode* MNhead, int Row,
    int Col, int data)
{
    MatrixNode* Mptr = MNhead;
 
    // Create a new node
    SparseNode* New = CreateList(
        Row, Col, data);
 
    // If the head is NULL, point it
    // to the newly created node
    if (Mptr->SNPTR == NULL) {
        Mptr->SNPTR = New;
        return MNhead;
    }
 
    // Insert this node at beginning
    New->next = Mptr->SNPTR;
 
    // Update the head pointer
    Mptr->SNPTR = New;
 
    return MNhead;
}
 
// Function to construct the sparse
// matrix using linked list
MatrixNode* ConstructSparseMatrix(
    MatrixNode* MNhead, int Matrix[R][C],
    SparseNode* SNhead)
{
    int i, j;
    MatrixNode* Mptr = MNhead;
 
    // If the head pointer is NULL
    if (MNhead == NULL) {
        MNhead = ConstructMNhead(
            MNhead, SNhead);
    }
 
    Mptr = MNhead;
 
    // Traverse the matrix, row-wise
    for (i = 0;
         i < Mptr->Matrix[0]; i++) {
        for (j = 0;
             j < Mptr->Matrix[1]; j++) {
 
            // For all non-zero values,
            // push them in linked list
            if (Matrix[i][j])
                MNhead = AddInList(
                    MNhead, i, j,
                    Matrix[i][j]);
        }
    }
 
    return MNhead;
}
 
// Function to reconstruct the sparse
// matrix using linked list
void ReConstructArray(MatrixNode* MNhead)
{
    int i, j;
    SparseNode* Sptr = MNhead->SNPTR;
 
    // Create a 2D array
    int** OriginalMatrix
 
        = (int**)malloc(sizeof(int*)
                        * MNhead->Matrix[0]);
 
    for (i = 0;
         i < MNhead->Matrix[0]; i++) {
        OriginalMatrix[i]
            = (int*)malloc(sizeof(int)
                           * MNhead->Matrix[1]);
    }
 
    // Initialize all the elements
    // in the original matrix as 0
    for (i = 0;
         i < MNhead->Matrix[0]; i++) {
 
        for (j = 0;
             j < MNhead->Matrix[1]; j++) {
            OriginalMatrix[i][j] = 0;
        }
    }
 
    // Print the linked list
    printf("Linked list represe"
           "ntation:\n");
 
    // Iterate while sptr pointer is not NULL
    while (Sptr != NULL) {
 
        // Update the element in the
        // original matrix and print
        // the current node
        OriginalMatrix[Sptr->Row][Sptr->Col]
            = Sptr->data;
 
        printf("(%d, %d, %d)->",
               Sptr->Row, Sptr->Col,
               OriginalMatrix[Sptr->Row][Sptr->Col]);
 
        // Move to the next node
        Sptr = Sptr->next;
    }
    printf("NULL\n");
 
    // Print the reconstructed matrix
    printf("Original Matrix Re"
           "-Construction:\n");
 
    for (i = 0; i < R; i++) {
        for (j = 0; j < C; j++) {
            printf("%d, ", OriginalMatrix[i][j]);
        }
        printf("\n");
    }
}
 
// Create a head of the linked list
MatrixNode* MNhead = NULL;
SparseNode* SNhead = NULL;
 
// Driver Code
int main()
{
    int Matrix[R][C] = { { 0, 1, 0, 0, 0 },
                         { 0, 1, 0, 0, 0 },
                         { 0, 0, 2, 0, 0 },
                         { 0, 3, 0, 0, 4 },
                         { 0, 0, 5, 0, 0 } };
    int** OriginalMatrix;
 
    // Sparse matrix Construction
    MNhead = ConstructSparseMatrix(
        MNhead, Matrix, SNhead);
 
    // Sparse matrix Re-Construction
    ReConstructArray(MNhead);
 
    return 0;
}

# python code for above approach
R = 5
C = 5
 
# linked list node
class SparseNode:
   
    # Function to initialize the node object
    def __init__(self, data, Col, Row):
        self.data = data  # Assign data
        self.Col = Col  # Assign Column
        self.Row = Row  # Assign Row
        self.next = None  # Initialize
        # next as null
 
# Store the head pointer of the linked
# list and the size of the matrix
class MatrixNode:
   
    # Function to initialize the node object
    def __init__(self, Matrix, SNPTR):
        self.Matrix = Matrix  # Initialize matrix
        self.SNPTR = None  # Initialize
        # SNPTR as null
 
# Function to initialize the head of
# the linked list
def ConstructMNhead(MNhead, SNhead):
   
    # add the number of rows and
    # columns and add head pointer
    MNhead = MatrixNode([R, C], SNhead)
    return MNhead
 
# Function to create a new node
 
 
def CreateList(Row, Col, data):
    # Create a new node
    New = SparseNode(data, Col, Row)
    return New
 
# Function to insert a node at the
# beginning of the  linked list
def AddInList(MNhead, Row, Col, data):
    Mptr = MNhead
    # Create a new node
    New = CreateList(Row, Col, data)
 
    # If the head is NULL, point it
    # to the newly created node
    if (Mptr.SNPTR == None):
        Mptr.SNPTR = New
        return MNhead
 
    # Insert this node at beginning
    New.next = Mptr.SNPTR
 
    # Update the head pointer
    Mptr.SNPTR = New
 
    return MNhead
 
# Function to construct the sparse
# matrix using linked list
def ConstructSparseMatrix(MNhead, Matrix,
                          SNhead):
    Mptr = MNhead
 
    # If the head pointer is NULL
    if (MNhead == None):
        MNhead = ConstructMNhead(
            MNhead, SNhead)
 
    Mptr = MNhead
 
    # Traverse the matrix, row-wise
    for i in range(0, Mptr.Matrix[0]):
        for j in range(0, Mptr.Matrix[1]):
 
            # For all non-zero values,
            # push them in linked list
            if (Matrix[i][j]):
                MNhead = AddInList(
                    MNhead, i, j,
                    Matrix[i][j])
 
    return MNhead
 
# Function to reconstruct the sparse
# matrix using linked list
def ReConstructArray(MNhead):
    Sptr = MNhead.SNPTR
 
    # Create a 2D array
    OriginalMatrix = []
 
    # Initialize all the elements
    # in the original matrix as 0
    for i in range(0, MNhead.Matrix[0]):
        OriginalMatrix.append([])
        for j in range(0, MNhead.Matrix[1]):
            OriginalMatrix[i].append(0)
 
    # Print the linked list
    print("Linked list represe"
          "ntation:\n")
 
    # Iterate while sptr pointer is not NULL
    while (Sptr != None):
 
        # Update the element in the
        # original matrix and print
        # the current node
        OriginalMatrix[Sptr.Row][Sptr.Col] = Sptr.data
 
        print("(", Sptr.Row, ",", Sptr.Col, ",",
              OriginalMatrix[Sptr.Row][Sptr.Col], ")->", end=" ")
 
        # Move to the next node
        Sptr = Sptr.next
    print("None\n")
 
    # Print the reconstructed matrix
    print("Original Matrix Re"
          "-Construction:\n")
 
    for i in range(0, R):
        for j in range(0, C):
            print(OriginalMatrix[i][j], end=" ")
        print("\n")
 
 
# Create a head of the linked list
 
# Driver Code
Matrix = [[0, 1, 0, 0, 0],
          [0, 1, 0, 0, 0],
          [0, 0, 2, 0, 0],
          [0, 3, 0, 0, 4],
          [0, 0, 5, 0, 0]]
 
MNhead = None
SNhead = None
# Sparse matrix Construction
MNhead = ConstructSparseMatrix(MNhead, Matrix, SNhead)
 
# Sparse matrix Re-Construction
ReConstructArray(MNhead)
 
# This code is contributed by rj13to

Linked list representation:
(4, 2, 5)->(3, 4, 4)->(3, 1, 3)->(2, 2, 2)->(1, 1, 1)->(0, 1, 1)->NULL
Original Matrix Re-Construction:
0, 1, 0, 0, 0, 
0, 1, 0, 0, 0, 
0, 0, 2, 0, 0, 
0, 3, 0, 0, 4, 
0, 0, 5, 0, 0, 

Complejidad temporal: O(N*M) 
Espacio auxiliar: O(N*M)