'How to represent sparse matrix (including zero elements) in C using linked list?
I want a code that represents a sparse matrix including zero elements using linked list, I basically want the output to be like this:
1 0 0 0
0 6 1 0
I already have a code that does the representation but it only gives as an output the non-Zero elements like so :
input :
2 0 0
0 0 0
0 0 0
output :
row : 1 col : 1 value : 2
Here is the code :
// C program for Sparse Matrix Representation
// using Linked Lists
#include<stdio.h>
#include<stdlib.h>
// Node to represent sparse matrix
struct Node
{
int value;
int row_position;
int column_postion;
struct Node *next;
};
// Function to create new node
void create_new_node(struct Node** start, int non_zero_element,
int row_index, int column_index )
{
struct Node *temp, *r;
temp = *start;
if (temp == NULL)
{
// Create new node dynamically
temp = (struct Node *) malloc (sizeof(struct Node));
temp->value = non_zero_element;
temp->row_position = row_index;
temp->column_postion = column_index;
temp->next = NULL;
*start = temp;
}
else
{
while (temp->next != NULL)
temp = temp->next;
// Create new node dynamically
r = (struct Node *) malloc (sizeof(struct Node));
r->value = non_zero_element;
r->row_position = row_index;
r->column_postion = column_index;
r->next = NULL;
temp->next = r;
}
}
// This function prints contents of linked list
// starting from start
void PrintList(struct Node* start)
{
struct Node *temp, *r, *s;
temp = r = s = start;
printf("row_position: ");
while(temp != NULL)
{
printf("%d ", temp->row_position);
temp = temp->next;
}
printf("\n");
printf("column_postion: ");
while(r != NULL)
{
printf("%d ", r->column_postion);
r = r->next;
}
printf("\n");
printf("Value: ");
while(s != NULL)
{
printf("%d ", s->value);
s = s->next;
}
printf("\n");
}
Solution 1:[1]
Your code was incomplete.
It could/should do the insertion of a new node in row/column sorted order. But, it appears it just appended to the end of the list. This makes the ordered printing of the matrix difficult. And, it does not allow for [true] random access (e.g. the same node is updated more than once).
So, I had to refactor the code.
It's no more extra time to scan the list and look for an insertion point that is in sorted order. That's because the function that inserts a new node must check for an already existing node to make the sparse matrix work like a real matrix.
I've included some other scan/match functions and created a matrix "pretty" print function.
The print code could be rewritten as it makes many calls to a nodefind function. The print could be rewritten to just loop through all nodes and print them in their correct columns.
The code is annotated:
#include <stdio.h>
#include <stdlib.h>
// node control
typedef struct node {
int node_row;
int node_col;
int node_val;
struct node *node_next;
} node_t;
// matrix control
typedef struct {
node_t *mtx_head; // head of list
// insertion temporaries
node_t *mtx_bef; // node before node to insert
node_t *mtx_aft; // node after node to insert
// printing temporaries
int mtx_rowmin; // minumum row
int mtx_rowmax; // maximum row
int mtx_colmin; // minumum column
int mtx_colmax; // maximum column
int mtx_valmax; // maximum matrix value
} mtx_t;
#define MAXOF(_lhs,_rhs) \
if (_rhs > _lhs) \
_lhs = _rhs
#define MINOF(_lhs,_rhs) \
if (_rhs < _lhs) \
_lhs = _rhs
#define SEPOUT(_sep) \
for (int idx = 0; idx < xwid; ++idx) \
fputc(_sep,stdout)
// colscan -- scan a given row for column insertion point
// RETURNS: add pointer (or NULL)
node_t *
colscan(mtx_t *mtx,node_t *cur,node_t *add)
{
for (; cur != NULL; cur = cur->node_next) {
// stop if row changes -- we are beyond the insertion point
if (cur->node_row > add->node_row) {
mtx->mtx_aft = cur;
break;
}
// duplicate node -- just update existing value and release new node
if (cur->node_col == add->node_col) {
cur->node_val = add->node_val;
free(add);
add = NULL;
break;
}
// point to node _after_ insertion point
mtx->mtx_aft = cur;
// stop if column becomes higher
if (cur->node_col > add->node_col)
break;
// point to node _before_ insertion point
mtx->mtx_bef = cur;
}
return add;
}
// nodenew -- add new node to matrix
void
nodenew(mtx_t *mtx,int row,int col,int val)
{
// get new node to insert
node_t *add = calloc(1,sizeof(*add));
add->node_row = row;
add->node_col = col;
add->node_val = val;
mtx->mtx_bef = NULL;
mtx->mtx_aft = NULL;
// scan all nodes looking for place to insert row
for (node_t *cur = mtx->mtx_head; cur != NULL; cur = cur->node_next) {
// found start of matching row -- scan for matching column
if (cur->node_row == add->node_row) {
add = colscan(mtx,cur,add);
break;
}
// went beyond row -- stop -- we insert before this node
if (cur->node_row > add->node_row) {
mtx->mtx_aft = cur;
break;
}
// remember node that is lower than the one to insert
mtx->mtx_bef = cur;
}
// insert new node
do {
// node is a duplicate -- value has already been updated (by colscan)
if (add == NULL)
break;
node_t *prev = mtx->mtx_bef;
// insert/append the new node
if (prev != NULL) {
add->node_next = prev->node_next;
prev->node_next = add;
break;
}
// add to empty list or before start of existing list
add->node_next = mtx->mtx_aft;
mtx->mtx_head = add;
} while (0);
}
// nodefind -- find existing node
node_t *
nodefind(mtx_t *mtx,int row,int col)
{
node_t *cur = mtx->mtx_head;
for (; cur != NULL; cur = cur->node_next) {
if ((cur->node_row == row) && (cur->node_col == col))
break;
}
return cur;
}
// nodedel -- delete existing node
// RETURNS: 1=found, 0=no match
int
nodedel(mtx_t *mtx,int row,int col)
{
node_t *cur = mtx->mtx_head;
node_t *prev = NULL;
node_t *next;
int match = 0;
for (; cur != NULL; prev = cur, cur = next) {
next = cur->node_next;
if ((cur->node_row == row) && (cur->node_col == col)) {
if (prev != NULL)
prev->node_next = next;
else
mtx->mtx_head = next;
free(cur);
match = 1;
break;
}
}
return match;
}
// mtxdimset -- get matrix dimensions
void
mtxdimset(mtx_t *mtx)
{
node_t *cur = mtx->mtx_head;
// NOTE: with some effort, nodenew/nodedel could keep the dimensions up to
// date (but, currently, they don't)
do {
// empty matrix
if (cur == NULL) {
mtx->mtx_rowmin = -1;
mtx->mtx_rowmax = -2;
mtx->mtx_colmin = -1;
mtx->mtx_colmax = -2;
mtx->mtx_valmax = 0;
break;
}
mtx->mtx_rowmin = cur->node_row;
mtx->mtx_rowmax = cur->node_row;
mtx->mtx_colmin = cur->node_col;
mtx->mtx_colmax = cur->node_col;
mtx->mtx_valmax = cur->node_val;
cur = cur->node_next;
for (; cur != NULL; cur = cur->node_next) {
MAXOF(mtx->mtx_valmax,cur->node_val);
MINOF(mtx->mtx_rowmin,cur->node_row);
MAXOF(mtx->mtx_rowmax,cur->node_row);
MINOF(mtx->mtx_colmin,cur->node_col);
MAXOF(mtx->mtx_colmax,cur->node_col);
}
} while (0);
}
// mtxprint -- print matrix
void
mtxprint(mtx_t *mtx,const char *who)
{
node_t *cur = mtx->mtx_head;
char fmt[100];
// get row/column/value ranges
mtxdimset(mtx);
// get maximum number size (pretty print)
int xwid = 0;
int rwid = sprintf(fmt,"%d",mtx->mtx_rowmax);
int cwid = sprintf(fmt,"%d",mtx->mtx_colmax);
int vwid = sprintf(fmt,"%d",mtx->mtx_valmax);
MAXOF(xwid,rwid);
MAXOF(xwid,cwid);
MAXOF(xwid,vwid);
// get the format for printing
sprintf(fmt," %%%dd",xwid);
if (who != NULL)
printf("MATRIX R:%d-%d C:%d-%d (from %s)\n",
mtx->mtx_rowmin,mtx->mtx_rowmax,
mtx->mtx_colmin,mtx->mtx_colmax,
who);
// output column headers
printf(" ");
SEPOUT(' ');
for (int col = mtx->mtx_colmin; col <= mtx->mtx_colmax; ++col)
printf(fmt,col);
printf("\n");
// output all rows
for (int row = mtx->mtx_rowmin; row <= mtx->mtx_rowmax; ++row) {
// output row number
printf(fmt,row);
// output all rows in the column
// NOTE: this is very slow due to the repeated calls to nodefind
for (int col = mtx->mtx_colmin; col <= mtx->mtx_colmax; ++col) {
cur = nodefind(mtx,row,col);
if (cur != NULL) {
printf(fmt,cur->node_val);
continue;
}
SEPOUT(' ');
fputc('*',stdout);
}
printf("\n");
}
}
// mtxdump -- dump out matrix nodes in linear order
void
mtxdump(mtx_t *mtx)
{
for (node_t *cur = mtx->mtx_head; cur != NULL; cur = cur->node_next)
printf("DMP: [%d,%d] = %d\n",
cur->node_row,cur->node_col,cur->node_val);
}
int
main(void)
{
mtx_t *mtx = calloc(1,sizeof(*mtx));
enum {
ROWMAX = 20,
COLMAX = 7
};
// ordinary matrix (for cross check)
int arr[ROWMAX][COLMAX];
for (int rowcur = 0; rowcur < ROWMAX; ++rowcur) {
for (int colcur = 0; colcur < COLMAX; ++colcur)
arr[rowcur][colcur] = -1;
}
// add random row/column/data
for (int idx = 0; idx < (ROWMAX * COLMAX) / 2; ++idx) {
int rowcur = rand() % ROWMAX;
int colcur = rand() % COLMAX;
int valcur = rand() % (COLMAX * ROWMAX);
#if DEBUG
printf("\n");
#endif
int valold = arr[rowcur][colcur];
printf("%s: [%d,%d] = %d\n",
(valold < 0) ? "ADD" : "UPD",rowcur,colcur,valcur);
arr[rowcur][colcur] = valcur;
nodenew(mtx,rowcur,colcur,valcur);
#if DEBUG
mtxdump(mtx);
#endif
}
printf("\n");
mtxprint(mtx,"FIN");
// cross check
printf("\n");
printf("cross check ...\n");
int miss = 0;
for (int rowcur = 0; rowcur < ROWMAX; ++rowcur) {
for (int colcur = 0; colcur < COLMAX; ++colcur) {
int valexp = arr[rowcur][colcur];
node_t *cur = nodefind(mtx,rowcur,colcur);
int valact;
if (cur != NULL)
valact = cur->node_val;
else
valact = -1;
if (valact != valexp) {
printf("DIF: [%d,%d] = %d/%d\n",rowcur,colcur,valexp,valact);
miss = 1;
}
}
}
if (! miss)
printf("all values match\n");
return 0;
}
Here is the program output:
ADD: [3,4] = 37
ADD: [15,1] = 115
ADD: [6,2] = 29
ADD: [1,2] = 47
ADD: [10,4] = 83
ADD: [6,3] = 106
ADD: [12,2] = 31
ADD: [8,5] = 9
ADD: [2,5] = 82
ADD: [3,1] = 75
ADD: [9,0] = 122
ADD: [18,3] = 107
ADD: [13,0] = 51
ADD: [2,1] = 53
ADD: [1,0] = 104
ADD: [17,6] = 44
UPD: [15,1] = 73
ADD: [6,0] = 120
ADD: [16,2] = 102
ADD: [10,1] = 101
ADD: [5,6] = 4
ADD: [7,3] = 5
ADD: [6,4] = 73
ADD: [17,5] = 115
ADD: [2,3] = 94
ADD: [7,4] = 84
ADD: [3,0] = 7
UPD: [8,5] = 98
ADD: [8,4] = 63
ADD: [11,1] = 99
ADD: [12,4] = 96
ADD: [8,0] = 92
ADD: [6,6] = 74
ADD: [19,4] = 70
ADD: [14,0] = 127
UPD: [1,0] = 62
ADD: [17,0] = 132
ADD: [16,4] = 100
UPD: [6,6] = 105
ADD: [9,6] = 99
ADD: [0,3] = 31
ADD: [17,3] = 11
ADD: [1,5] = 29
UPD: [7,4] = 136
UPD: [17,5] = 106
ADD: [5,1] = 43
ADD: [19,5] = 28
ADD: [11,4] = 109
UPD: [3,4] = 10
ADD: [8,3] = 115
ADD: [0,2] = 116
UPD: [3,4] = 5
ADD: [6,5] = 81
ADD: [15,4] = 8
ADD: [4,0] = 41
ADD: [10,0] = 20
ADD: [14,2] = 4
ADD: [14,3] = 36
UPD: [3,0] = 87
ADD: [5,3] = 56
UPD: [12,4] = 77
ADD: [8,2] = 107
ADD: [14,1] = 98
ADD: [15,0] = 137
ADD: [15,2] = 38
UPD: [8,5] = 31
ADD: [8,1] = 76
ADD: [4,4] = 23
ADD: [13,2] = 126
ADD: [0,4] = 58
MATRIX R:0-19 C:0-6 (from FIN)
0 1 2 3 4 5 6
0 * * 116 31 58 * *
1 62 * 47 * * 29 *
2 * 53 * 94 * 82 *
3 87 75 * * 5 * *
4 41 * * * 23 * *
5 * 43 * 56 * * 4
6 120 * 29 106 73 81 105
7 * * * 5 136 * *
8 92 76 107 115 63 31 *
9 122 * * * * * 99
10 20 101 * * 83 * *
11 * 99 * * 109 * *
12 * * 31 * 77 * *
13 51 * 126 * * * *
14 127 98 4 36 * * *
15 137 73 38 * 8 * *
16 * * 102 * 100 * *
17 132 * * 11 * 106 44
18 * * * 107 * * *
19 * * * * 70 28 *
cross check ...
all values match
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 |