0

4.0kviews

Discuss how memory allocation for a sparse matrix can be optimized using a linked list. Write a C-program for the same.

**1 Answer**

0

4.0kviews

Discuss how memory allocation for a sparse matrix can be optimized using a linked list. Write a C-program for the same.

0

35views

written 7.8 years ago by |

- 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) { list *ptr, *temp = head; if (head == NULL) { head = makenode(r, c, val); } else { while (temp->next!= NULL) temp = temp->next; ptr = makenode(r, c, val); temp->next = ptr; } return head; } void display(list *head) { list *temp; if (head == NULL) { Printf(“/nList is empty.”); exit(1); } temp = head; while (temp!= NULL) { printf(“( % d, % d, % d->)->”, temp->rows, temp->cols, temp->value); temp = temp->next; } printf(“bb “); } int main() { int arr[3][4], i, j, m, n, ct = 0; list *head = NULL; 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++; } } head = makenode(3, 4, ct); for (i = 0;i < 3;i++) { for (j = 0;j < 4;j++) { if (arr[i][j] != 0) head = insert(head, i, j, arr[i][j]); } } printf(“/nList representation of Sparse Matrix is: n”); display(head); getch(); }`

ADD COMMENT
EDIT

Please log in to add an answer.