0
3.9kviews
Discuss how memory allocation for a sparse matrix can be optimized using a linked list. Write a C-program for the same.
0
34views
• A matrix is a two-dimensional data object which contains m rows and n columns. The total number of values in a matrix is given by m*n.
• It can be visualized as a tabular representation of a collection of data.
• Matrix have a huge application in the field of computers wherein they are used to collect and store data in a proper, well-organized manner.
• Matrix comes in multi-dimensional format the most commonly used being the two-dimensional matrix represented as M[i][j] where the data resides at the ith row and jth column.
• Sparse Matrix: A matrix that has a large number of zero values is known as a Sparse Matrix. Implementing a sparse matrix by using a two dimensional array structure would lead to wastage of a significant amount of space.
• This problem can be solved by using the linked list data structure. We can store the non-zero elements and heir row, column positions and store them.
• They can be stored in a linear list. Now these list data can be arranged later based on the increasing row numbers and for common rows, based on increasing column numbers.

Each element can be represented using a node having four fields as

struct node {
int r_value,c_value,data;
struct node* next;
}


Over here next is a pointer to the next node in the linked list which also has a non-zero element from the sparse matrix.

/* Sparse Matrix representation using linked list */
#include <stdio.h>
#include <stdlib.h>
typedef struct list
{
int rows, cols, value;
struct list *next;
} list;
list *create()
{
list *temp = (list *)malloc(sizeof(list));
if (temp == NULL)
{
printf(“/nMemory Allocation Error!”);
exit(1);
}
return temp;
}
list *makenode(int r, int c, int val)
{
list *temp = create();
temp->rows = r;
temp->cols = c;
temp->value = val;
temp->next = NULL;
return temp;
}
list *insert(list *head, int r, int c, int val)
{
{
}
else
{
while (temp->next!= NULL)
temp = temp->next;
ptr = makenode(r, c, val);
temp->next = ptr;
}
}
{
list *temp;
{
Printf(“/nList is empty.”);
exit(1);
}
while (temp!= NULL)
{
printf(“( % d, % d, % d->)->”, temp->rows, temp->cols, temp->value);
temp = temp->next;
}
printf(“bb “);
}
int main()
{
int arr, i, j, m, n, ct = 0;
for (i = 0; i < 3; i++)
{
printf(“/nEnter the values for row % d?”, i + 1);
for (j = 0;j < 4;j++)
{
scanf(“ % d”, &arr[i][j]);
if (arr[i][j] != 0)
ct++;
}
}
for (i = 0;i < 3;i++)
{
for (j = 0;j < 4;j++)
{
if (arr[i][j] != 0)