Sparse Matrix in Data Structure
Sparse Matrix
The sparse matrix is a two-dimensional data object which is made by m rows and n columns, so we can say the number of data values in sparse matrix are m x n. In any matrix, the elements have 0 value are more than the others elements called a sparse matrix.
Uses of Sparse Matrix
- Execution time: The execution time of sparse matrix is less because it’s a logically designed data structure traversing only non-zero elements.
- Storage: The sparse matrix takes less memory because in this, non-zero elements are lesser than the zeros elements so we store only non-zero elements.
Representation of Sparse Matrix
- Array representation: -
For array representation of sparse matrix, we use 2-D array in which there are three columns as follows:
- Row: In this, index is row, where the non-zero element is placed in matrix
- Column: This is index of column, where the non-zero element is placed in matrix.
- Data value: This is value of the non-zero element placed at Index (row, column)
C- program of sparse matrix using Arrays
#include <stdio.h> #define MAX 20 void read_matrix(int a[10][10], int row, int column); void print_sparse(int b[MAX][3]); void create_sparse(int a[10][10], int row, int column, int b[MAX][3]); // This is the driver function for the program int main() { int a[10][10], b[MAX][3], row, column; printf("\nEnter the size of matrix (rows, columns): "); scanf("%d%d", &row, &column); read_matrix(a, row, column); create_sparse(a, row, column, b); print_sparse(b); return 0; } // Function for read the value for sparse matrix void read_matrix(int a[10][10], int row, int column) { int i, j; printf("\nEnter elements of matrix\n"); for (i = 0; i < row; i++) { for (j = 0; j < column; j++) { printf("[%d][%d]: ", i, j); scanf("%d", &a[i][j]); } } } // Function for creating the sparse matrix void create_sparse(int a[10][10], int row, int column, int b[MAX][3]) { int i, j, k; k = 1; b[0][0] = row; b[0][1] = column; for (i = 0; i < row; i++) { for (j = 0; j < column; j++) { if (a[i][j] != 0) { b[k][0] = i; b[k][1] = j; b[k][2] = a[i][j]; k++; } } b[0][2] = k - 1; } } // Function of display the element of sparse matrix void print_sparse(int b[MAX][3]) { int i, column; column = b[0][2]; printf("\nSparse form:\n\n"); Printf("Row\tColumn\tValue\n"); for (i = 0; i <= column; i++) { printf("%d\t%d\t%d\n", b[i][0], b[i][1], b[i][2]); } }
Output
- Linked List representation
In linked list, we define that each node has four fields are follows:
- Row: In this, index is row, where the non-zero element is placed in matrix
- Column: This is index of column, where the non-zero element is placed in matrix.
- Data value: This is value of the non-zero element placed at Index (row, column)
- Next node: Address of the next node
C- program of sparse matrix using Linked List
#include <stdio.h> #include <stdlib.h> /* structure to store data */ struct node { int row, col, val; struct node *right, *down; }; /* structure of column head */ struct chead { int col; struct chead *next; struct node *down; }; /* structure of row head */ struct rhead { int row; struct rhead *next; struct node *right; }; /* structure of additional head */ struct sparsehead { int rowCount, colCount; struct rhead *frow; struct chead *fcol; }; /* main node */ struct sparse { int row, *data; struct node *nodePtr; struct sparsehead *smatrix; struct rhead **rowPtr; struct chead **colPtr; }; int count = 0; /* Establish row and column links */ void initialize(struct sparse *sPtr, int row, int col) { int i; sPtr->rowPtr = (struct rhead **) calloc(1, (sizeof (struct rhead) * row)); sPtr->colPtr = (struct chead **) calloc(1, (sizeof (struct chead) * col)); for (i = 0; i < row; i++) sPtr->rowPtr[i] = (struct rhead *) calloc(1, sizeof (struct rhead)); for (i = 0; i < row - 1; i++) { sPtr->rowPtr[i]->row = i; sPtr->rowPtr[i]->next = sPtr->rowPtr[i + 1]; } for (i = 0; i < col; i++) sPtr->colPtr[i] = (struct chead *) calloc(1, sizeof (struct chead)); for (i = 0; i < col - 1; i++) { sPtr->colPtr[i]->col = i; sPtr->colPtr[i]->next = sPtr->colPtr[i + 1]; } /* update additional head information */ sPtr->smatrix = (struct sparsehead *) calloc(1, sizeof (struct sparsehead)); sPtr->smatrix->rowCount = row; sPtr->smatrix->colCount = col; sPtr->smatrix->frow = sPtr->rowPtr[0]; sPtr->smatrix->fcol = sPtr->colPtr[0]; return; } /* input sparse matrix */ void inputMatrix(struct sparse *sPtr, int row, int col) { int i, n, x = 0, y = 0; n = row * col; sPtr->data = (int *) malloc(sizeof (int) * n); for (i = 0; i < n; i++) { if (y != 0 && y % col == 0) { x++; y = 0; } printf("data[%d][%d] : ", x, y); scanf("%d", &(sPtr->data[i])); if (sPtr->data[i]) count++; y++; } return; } /* display sparse matrix */ void displayInputMatrix(struct sparse s, int row, int col) { int i; for (i = 0; i < row * col; i++) { if (i % col == 0) printf("\n"); printf("%d ", s.data[i]); } printf("\n"); return; } /* create 3-tuple array from input sparse matrix */ void createThreeTuple(struct sparse *sPtr, struct sparse s, int row, int col) { int i, j = 0, x = 0, y = 0, l = 0; sPtr->row = count; sPtr->data = (int *) malloc(sizeof (int) * (sPtr->row * 3)); for (i = 0; i < row * col; i++) { if (y % col == 0 && y != 0) { x++; y = 0; } if (s.data[i] != 0) { sPtr->data[l++] = x; sPtr->data[l++] = y; sPtr->data[l++] = s.data[i]; } y++; } return; } /* insert element to the list */ void insert(struct sparse *sPtr, int row, int col, int val) { struct rhead *rPtr; struct chead *cPtr; struct node *n1, *n2; struct sparsehead *smat = sPtr->smatrix; int i, j; /* update node values */ sPtr->nodePtr = (struct node *) malloc(sizeof (struct node)); sPtr->nodePtr->row = row; sPtr->nodePtr->col = col; sPtr->nodePtr->val = val; /* get the row headnode */ rPtr = smat->frow; /* move to corresponding row */ for (i = 0; i < row; i++) rPtr = rPtr->next; /* traverse the nodes in current and locate new node */ n1 = rPtr->right; if (!n1) { rPtr->right = sPtr->nodePtr; sPtr->nodePtr->right = NULL; } else { while (n1 && n1->col < col) { n2 = n1; n1 = n1->right; } n2->right = sPtr->nodePtr; sPtr->nodePtr->right = NULL; } /* get the column head node */ cPtr = sPtr->smatrix->fcol; /* move to corresponding column (1/2/3..) */ for (i = 0; i < col; i++) cPtr = cPtr->next; /* * traverse the node in current column and locate * new node in appropriate position */ n1 = cPtr->down; if (!n1) { cPtr->down = sPtr->nodePtr; sPtr->nodePtr->down = NULL; } else { while (n1 && n1->row < row) { n2 = n1; n1 = n1->down; } n2->down = sPtr->nodePtr; sPtr->nodePtr->down = NULL; } return; } /* create list for 3-Tuple representation */ void createList(struct sparse *sPtr) { int i, j = 0; for (i = 0; i < sPtr->row; i++) { insert(sPtr, sPtr->data[j], sPtr->data[j + 1], sPtr->data[j + 2]); j = j + 3; } return; } /* Display data from linked list of 3-Tuple*/ void displayList(struct sparse s) { struct node *n; int row = s.smatrix->rowCount, i; for (i = 0; i < row; i++) { n = s.rowPtr[i]->right; if (n) { while (n->right) { printf("%d\t%d\t%d\n", n->row, n->col, n->val); n = n->right; } if (n->row == i) { printf("%d\t%d\t%d\n", n->row, n->col, n->val); } } } printf("\n"); } int main() { struct sparse input, output; int row, col; printf("Enter the rows and columns:"); scanf("%d%d", &row, &col); initialize(&input, row, col); initialize(&output, row, col); inputMatrix(&input, row, col); printf("Given Sparse Matrix has %d non-zero elements\n", count); printf("Input Sparse Matrix:\n"); displayInputMatrix(input, row, col); printf("\n\n"); createThreeTuple(&output, input, row, col); createList(&output); printf("Row\tColumn\tValue\n");; printf("%d\t%d\t%d\n", output.smatrix[0].rowCount, output.smatrix[0].colCount, count); displayList(output); return 0; }
Output