Sparse Matrix and its representations | Set 1 (Using Arrays and Linked Lists)

link 0

A matrix is a two-dimensional data object made of m rows and n columns, therefore having total m x n values. If most of the elements of the matrix have 0 value, then it is called a sparse matrix.

Why to use Sparse Matrix instead of simple matrix ?

  • Storage: There are lesser non-zero elements than zeros and thus lesser memory can be used to store only those elements.
  • Computing time: Computing time can be saved by logically designing a data structure traversing only non-zero elements..

Example:

0 0 3 0 4            
0 0 5 7 0
0 0 0 0 0
0 2 6 0 0

Representing a sparse matrix by a 2D array leads to wastage of lots of memory as zeroes in the matrix are of no use in most of the cases. So, instead of storing zeroes with non-zero elements, we only store non-zero elements. This means storing non-zero elements with triples- (Row, Column, value).

Sparse Matrix Representations can be done in many ways following are two common representations:

  1. Array representation
  2. Linked list representation

Method 1: Using Arrays

2D array is used to represent a sparse matrix in which there are three rows named as

  • Row: Index of row, where non-zero element is located
  • Column: Index of column, where non-zero element is located
  • Value: Value of the non zero element located at index – (row,column)

Sparse Matrix Array Representation

// C program for Sparse Matrix Representation
// using Linked Lists
#include<stdio.h>
int main()
{
    // Assume 4x5 sparse matrix
    int sparseMatrix[4][5] =
    {
        {0 , 0 , 3 , 0 , 4 },
        {0 , 0 , 5 , 7 , 0 },
        {0 , 0 , 0 , 0 , 0 },
        {0 , 2 , 6 , 0 , 0 }
    };
    int size = 0;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 5; j++)
            if (sparseMatrix[i][j] != 0)
                size++;
    // number of columns in compactMatrix (size) must be
    // equal to number of non - zero elements in
    // sparseMatrix
    int compactMatrix[3][size];
    // Making of new matrix
    int k
    for (i = 0; i < 4; i++)
        for (j = 0; j < 5; j++)
            if (sparseMatrix[i][j] != 0)
            {
                compactMatrix[0][k] = i;
                compactMatrix[1][k] = j;
                compactMatrix[2][k] = sparseMatrix[i][j];
                k++;
            }
    for (i=0; i<3; i++)
    {
        for (j=0; j<size; j++)
            printf("%d ", compactMatrix[i][j]);
        printf("\n");
    }
    return 0;
}

Output:

0 0 1 1 3 3 
2 4 2 3 1 2 
3 4 5 7 2 6 

 

Method 2: Using Linked Lists

In linked list, each node has four fields. These four fields are defined as:

  • Row: Index of row, where non-zero element is located
  • Column: Index of column, where non-zero element is located
  • Value: Value of the non zero element located at index – (row,column)
  • Next node: Address of the next node

Sparse-Matrix-Linked-List 2

// C program for Sparse Matrix Representation
// using Linked Lists
#include<stdio.h>
#include<stdlib.h>
// Node to represent sparse matrix
struct Node
{
    int value;
    int row_position;
    int column_postion;
    struct Node *next;
};
// Function to create new node
void create_new_node(struct Node** start, int non_zero_element,
                     int row_index, int column_index )
{
    struct Node *temp, *r;
    temp = *start;
    if (temp == NULL)
    {
        // Create new node dynamically
        temp = (struct Node *) malloc (sizeof(struct Node));
        temp->value = non_zero_element;
        temp->row_position = row_index;
        temp->column_postion = column_index;
        temp->next = NULL;
        *start = temp;
    }
    else
    {
        while (temp->next != NULL)
            temp = temp->next;
        // Create new node dynamically
        r = (struct Node *) malloc (sizeof(struct Node));
        r->value = non_zero_element;
        r->row_position = row_index;
        r->column_postion = column_index;
        r->next = NULL;
        temp->next = r;
    }
}
// This function prints contents of linked list
// starting from start
void PrintList(struct Node* start)
{
    struct Node *temp, *r, *s;
    temp = r = s = start;
    printf("row_position: ");
    while(temp != NULL)
    {
        printf("%d ", temp->row_position);
        temp = temp->next;
    }
    printf("\n");
    printf("column_postion: ");
    while(r != NULL)
    {
        printf("%d ", r->column_postion);
        r = r->next;
    }
    printf("\n");
    printf("Value: ");
    while(s != NULL)
    {
        printf("%d ", s->value);
        s = s->next;
    }
    printf("\n");
}
// Driver of the program
int main()
{
   // Assume 4x5 sparse matrix
    int sparseMatric[4][5] =
    {
        {0 , 0 , 3 , 0 , 4 },
        {0 , 0 , 5 , 7 , 0 },
        {0 , 0 , 0 , 0 , 0 },
        {0 , 2 , 6 , 0 , 0 }
    };
    /* Start with the empty list */
    struct Node* start = NULL;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 5; j++)
            // Pass only those values which are non - zero
            if (sparseMatric[i][j] != 0)
                create_new_node(&start, sparseMatric[i][j], i, j);
    PrintList(start);
    return 0;
}

Output:

row_position: 0 0 1 1 3 3 
column_postion: 2 4 2 3 1 2 
Value: 3 4 5 7 2 6              



Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

rakesh

Leave a Reply

Your email address will not be published. Required fields are marked *

Skip to toolbar