Home » Data Structure

Sparse matrix for 3-tuple method using Array

In this article, we are going to learn how to implement a sparse matrix for 3-tuple method using an array in the data structure? Submitted by Manu Jemini, on December 19, 2017

A sparse matrix is a matrix in which most of the elements are zero. By contrast, if most of the elements are nonzero, then the matrix is considered dense. The number of zero-valued elements divided by the total number of elements is called the sparsity of the matrix (which is equal to 1 minus the density of the matrix).

Now to keep track of non-zero elements in a sparse matrix we have 3-tuple method using an array. Elements of the first row represent the number of rows, columns and non-zero values in the sparse matrix. Elements of the other rows give information about the location and value of non-zero elements.

Image source: http://btechsmartclass.com/DS/images/U1_T14_P1.png

The Below code first asks the user for the number of rows and columns. According to the input, the program asks for the inputs for the elements of the matrix.

The Program then creates a matrix which tells about the non-zero elements of the matrix which user have entered. This code will assume that you have entered a sparse matrix.

C program for Sparse Matrix implementation

#include <stdio.h>
#define srow 50
#define mrow 20
#define mcolumn 20

/*Begin of main*/
int main()
{
    int mat[mrow][mcolumn], sparse[srow][3];
    int i, j, nzero = 0, mr, mc, sr, s;

    //taking inputs
    printf("Enter number of rows : ");
    scanf("%d", &mr);
    printf("Enter number of columns : ");
    scanf("%d", &mc);

    for (i = 0; i < mr; i++)
        for (j = 0; j < mc; j++) {
            //taking inputs of rows and columns
            printf("Enter element for row %d,column %d : ", i + 1, j + 1);
            scanf("%d", &mat[i][j]);
        }

    //printing entered matrix
    printf("Entered matrix is : \n");
    for (i = 0; i < mr; i++) {
        for (j = 0; j < mc; j++) {
            printf("%6d", mat[i][j]);
            if (mat[i][j] != 0)
                nzero++;
        }
        printf("\n");
    }

    sr = nzero + 1;
    sparse[0][0] = mr;
    sparse[0][1] = mc;
    sparse[0][2] = nzero;
    s = 1;

    for (i = 0; i < mr; i++)
        for (j = 0; j < mc; j++) {
            if (mat[i][j] != 0) {
                sparse[s][0] = i + 1;
                sparse[s][1] = j + 1;
                sparse[s][2] = mat[i][j];
                s++;
            }
        }

    //printing sparse matrix
    printf("Sparse matrix is :\n");
    for (i = 0; i < sr; i++) {
        for (j = 0; j < 3; j++)
            printf("%5d", sparse[i][j]);
        printf("\n");
    }
}
/*End of main*/

Output