Linked List 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 Using Arrays: 
|  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

3-Tuple Representation Of Sparse Matrix Using Linked List:
AH - Additional Header (sparseHead)

     AH                       chead-col 0          chead - col 1           chead - col 2                    
+---------------+       +----------------+      +----------------+     +----------------+
|   |  3 | 3 |   -|-> |      |  0   |    -|->  |      |  1   |    -|-> |      |  2   | N  |
+---------------+       +----------------+      +----------------+     +----------------+
   |                         |                            |
   v rhead -row 0       v  (node)                 +
+----------------+     +------------------+        |
|      |  0   |   -|-> |0row| 0col | 1  |        +
+----------------+     +------------------+        |
   |                      |  NULL  |  NULL|        +
   v rhead - row1    +------------------+        |
+----------------+                                      +
|      |  1   | N |                                     |
+----------------+                                      +
   |                                                        |
   v  rhead-row2                                       v    (node)
+----------------+                                   +--------------------+ 
| N   |  2   |    -|-------------------------->| 2row | 1col | 4  |
+----------------+                                   +--------------------+
                                                         |  NULL     |  NULL|
                                                         +---------------------+

See Also:

C Program To Merge Two Arrays
C Program For Array Representation Of Sparse Matrix
C Program To Perform Insertion, Deletion, Searching & Traversal In Singly Linked List
C Program To Perform Insertion, Deletion, Sorting In Doubly Linked List - (Simple)
C Program To Sort A Doubly Linked List (Descending Order)

C Program To Merge Two Linked Lists

C Program To Reverse Linked List
C Program To Implement Circular Singly Linked List
C Program To Implement Circular Doubly Linked List
C Program For Polynomial Multiplication Using Linked List 
C Program For Polynomial Addition Using Linked List
C Program For Linked List Representation Of Sparse Matrix
C Program To Concatenate Two Linked Lists
C Program To Perform Recursion On Linked List

Insertion, Deletion, Traversal, Reversal And Search Operation on Arrays
Doubly Linked List - Insertion, Traversal, Searching, Delete Node, Delete List

C Program For 3-Tuple Representation 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  %d  %d\n", n->row, n->col, n->val);

                                n =  n->right;

                        }

                        if (n->row == i) {

                                printf("%d  %d  %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("3-Tuple representation of the given sparse matrix:\n");

        printf("%d  %d  %d\n", output.smatrix[0].rowCount,

                output.smatrix[0].colCount, count);

        displayList(output);

        return 0;

  }

  Output: (C Program For Linked List Representation of Sparse Matrix)

  jp@jp-VirtualBox:~/$ ./a.out
  Enter the rows and 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
  Input Sparse Matrix:
    1 0 0 
    0 0 0 
    0 4 0 
  
  3-Tuple representation of the given sparse matrix:
    3  3  2
    0  0  1
    2  1  4