Array Representation Of Sparse Matrix

If most of the elements in a matrix have the value 0, then the matrix is called spare matrix.

Example For 3 X 3 Sparse Matrix:
|  1   0   0 |
|  0   0   0 |
|  0   4   0 |

3-Tuple Representation Of Sparse Matrix: 
|  3   3   2 |
|  0   0   1 |
|  2   1   4 |

Elements in the first row represents the number of rows, columns and non-zero values in sparse matrix.
First Row  -  |  3   3   2 |
3 - rows
3 - columns
2 - non- zero values

Elements in the other rows gives information about the location and value of non-zero elements.
|  0   0   1 | ( Second Row) - represents value 1 at 0th Row, 0th column
|  2   1   4 | (Third Row)     - represents value 4 at 2nd Row, 1st column

Example Program for 3-Tuple Representation of Sparse Matrix Using Arrays(in C):

---

  #include <stdio.h>
  #include <stdlib.h>

  int count;

  int main() {
        int *data, *tuple, row, col, tot, i, j, k =0, x = 0, y = 0;

        printf("Enter the no of rows & columns:");
        scanf("%d%d", &row, &col);

        tot = row * col;
        data = (int *) malloc(sizeof (int) * tot);
        for (i = 0; i < tot; i++) {
                if (y % col == 0 && y != 0) {
                        y = 0;
                        x++;
                }
                printf("data[%d][%d]:", x, y);
                scanf("%d", &data[i]);
                if (data[i])
                        count++;
                y++;
        }

        tuple = (int *) malloc(sizeof (int) * (count + 1) * 3);

        /* store row, column & count in 3-tuple array - in 1st row */
        tuple[k++] = row;
        tuple[k++] = col;
        tuple[k++] = count;
        x = y = 0;
        for (i = 0; i < tot; i++) {
                if (y % col == 0 && y != 0) {
                        y = 0;
                        x++;
                }

                /* store row, column and non-zero val in 3 tuple */

                if (data[i] != 0) {

                        tuple[k++] = x;

                        tuple[k++] = y;

                        tuple[k++] = data[i];

                }

                y++;

        }

        printf("Given Sparse Matrix has %d non-zero elements\n", count);

        x = y = 0;

        /* printing given sparse matrix */

        for (i = 0; i < tot; i++) {

                if (y % col == 0 && y != 0) {

                        y = 0;

                        x++;

                        printf("\n");

                }

                printf("%d ", data[i]);

                y++;

        }

        printf("\n\n");

        /* 3-tuple represenation of sparse matrix */

        printf("3-Tuple representation of Sparse Matrix:\n");

        for (i = 0; i < (count + 1) * 3; i++) {

                if (i % 3 == 0)

                        printf("\n");

                printf("%d ", tuple[i]);

        }

        printf("\n\n");

        return 0;

  }

 

Output: (C Program For Array Representation Of Sparse Matrix)

  Enter the no of rows & columns:3 3
  data[0][0]:1
  data[0][1]:0
  data[0][2]:0
  data[1][0]:0
  data[1][1]:0
  data[1][2]:0
  data[2][0]:0
  data[2][1]:4
  data[2][2]:0

  Given Sparse Matrix has 2 non-zero elements
    1 0 0 
    0 0 0 
    0 4 0 

  3-Tuple representation of Sparse Matrix:
    3 3 2 
    0 0 1 
    2 1 4