0
7.5kviews
What do you mean by Sparse matrix? How one can implement sparse matrix using Linked list? Support your answer with an example.
0
123views
1. A matrix containing a large number of zero values are compared to the non-zero values is called a sparse matrix. It can be represented using array or linked list.
2. In linked list representation, there exists a node consisting of four fields: row, col, num and first. The reo and col fields contain the total number of rows and columns in the matrix, respectively. The num field contains the total number of non-zero elements in the matrix and the first field contains a pointer to the first row containing at least one non-zero element.
3. Figure below shows the structure of head node.
4. Figure below shows the structure of row header node.
5. Figure below shows the structure of col header node.

1. Consider a sparse matrix A of order 6x6 and havind seven non-zero elements.Figure below shows the linked representation of matrix A.

2. The structure definations of the nodes col_node, rowheader and header in C language will be as follows:

a)

struct col_node
{
int colno;
int val;
struct col_node *next;
};


b)

struct rowheader
{
int rowno;
};


c)

struct col_node
{
Int row;
int col;
int nonzero;
};


Program to implement 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 */
int col;
struct node *down;
};

/* structure of row head */
int row;
struct node *right;
};

int rowCount, colCount;
};

/* main node */
struct sparse {
int row, *data;
struct node *nodePtr;
};

int count = 0;

/* Establish row and column links */
void initialize(struct sparse *sPtr, int row, int col) {
int i;
for (i = 0; i < row; i++)

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++)

for (i = 0; i < col - 1; i++) {
sPtr->colPtr[i]->col = i;
sPtr->colPtr[i]->next = sPtr->colPtr[i + 1];
}

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 node *n1, *n2;
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:

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: $\begin{matrix} \ 1 & 0 & 0 \\ \ 0 & 0 & 0 \\ \ 0 & 4 & 0 \\ \end{matrix}$

3-Tuple representation of the given sparse matrix: $\begin{matrix} \ 3 & 3 & 2 \\ \ 0 & 0 & 1 \\ \ 2 & 1 & 4 \\ \end{matrix}$