Sparse Matrix
• Most of the elements are zero.
• It wastes space.
Sparsity: the fraction of zero elements.
Basic matrix operations:
1. Creation
2. Addition
3. Multiplication
4. Transpose
Sparse Matrix
Data Structure
#define MAX_TERMS 101 • a[0].row: row index
typedef struct{
int col; • a[0].col: column index
int row;
int value; • a[0].value: number of items in
}term;
term a[MAX_TERMS];
the sparse matrix
Rows and columns are in
ascending order!
Sparse Matrix
Circular singly linked list representation
• To represent sparse matrix in circular singly linked list, we
need:
• For each column a circular linked list with a head node
• For each row a circular linked list with a head node
• Each node has a tag field to distinguish between head and entry
nodes
• Each head node has three fields, down , right, and next
• Down to link into column list
• Right to link into row list
• Next links head nodes
• The head node for rowi is also head node for columni
• Total number of head nodes is
max { number of rows, number of columns}
down head right down entry row col. right
next value
a) Head node
a) Entry node
entry i j
aij
a) Set up for aij
• Each head node is in three lists:
• A list of rows,
• A list of columns,
• A list of head nodes
• The list of head nodes also has a head node which is in
entry node structure and the row and column fields of this
node is used to store matrix dimensions
• Example: Given below a 4x4 sparse matrix
0 0 11 0
12 0 0 0
0 -4 0 0
0 0 0 -15
#define MAX_SIZE 50 /* size of largest matrix */
typedef enum {head, entry} tagfield;
typedef struct matrix_node * matrix_pointer;
typedef struct entry_node{
int col;
int row;
int value;
};
typedef struct matrix_node{
matrix_pointer down;
matrix_pointer right;
tagfield tag;
union {
matrix_pointer next;
entry_node entry;
}u;
};
matrix_pointer hdnode[MAX_SIZE];
Initializations
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 50 /* size of the largest matrix */
typedef enum {head, entry} tagfield;
typedef struct matrix_node * matrix_pointer;
typedef struct entry_node{
int col;
int row;
int value;
};
typedef struct matrix_node{
matrix_pointer down;
matrix_pointer right;
tagfield tag;
union {
matrix_pointer next;
entry_node entry;
}u;
};
matrix_pointer hdnode[MAX_SIZE];
void main()
{
matrix_pointer mread(void);
void mwrite(matrix_pointer);
matrix_pointer p;
p = mread();
mwrite(p);
}
Reading a sparse matrix
matrix_pointer mread(void)
{
int num_rows, num_cols, num_terms, num_heads, i;
int row, col, value, current_row;
matrix_pointer temp, last, node;
printf("Enter the number of rows, columns and number of nonzero terms:");
scanf("%d%d%d", &num_rows, &num_cols, &num_terms);
num_heads=(num_cols>num_rows)? num_cols : num_rows;
node = new_node();
node->tag=entry;
node->[Link]=num_rows;
node->[Link]=num_cols;
if(!num_heads) node->right = node;
else{ //initialize the head nodes
for(i=0;i<num_heads; i++){
temp=new_node();
hdnode[i]=temp; hdnode[i]->tag=head;
hdnode[i]->right=temp; hdnode[i]->[Link]=temp;
}
current_row=0;
last = hdnode[0];
for(i=0; i<num_terms; i++) {
printf("Enter row, column and values:");
scanf("%d%d%d", &row,&col,&value);
if(row>current_row){
last->right=hdnode(current_row);
current_row=row; last=hdnode[row];
}
temp=new_node();
temp->tag=entry; temp->[Link]=row;
temp->[Link]=col;
temp->[Link]=value;
last->right=temp; //link into row list
last=temp;
hdnode[col]->[Link]->down=temp;
hdnode[col]->[Link]=temp;
}
last->right=hdnode[current_row];
//close all column lists
for(i=0; i<num_cols; i++)
hdnode[i]->[Link]->down=hdnode[i];
//link all head nodes together
for(i=0; i<num_heads-1; i++)
hdnode[i]->[Link]=hdnode[i+1];
hdnode[num_heads-1]->[Link]=node;
node->right=hdnode[0];
}
return node;
}
Write out a sparse matrix
void mwrite(matrix_pointer node){
int i;
matrix_pointer temp, head=node->right;
printf("\n num_rows=%d, num_cols=%d \n", node->[Link], node-
>[Link]);
printf("The matrix by row, columnn and value: \n\n");
for(i=0; i<node->[Link]; i++){
for(temp=head->right; temp!=head; temp=temp->right)
printf("%5d%5d%5d\n", temp->[Link], temp->[Link],
temp->[Link]);
head=head->[Link];
}
}
Erase a sparse matrix
void merase(matrix_pointer *node)
{
matrix_pointer x,y,head=(*node)->right;
int i, num_heads;
for(i=0; i<(*node)->[Link]; i++){
y=head->right;
while(y!=head){
x=y;
y=y->right; free(x);
}
x=head; head=head->[Link]; free(x);
}
y=head;
while(y!=*node){
x=y;
y=y->[Link];
free(x)
}
free(*node); *node=NULL;
}
Multilist Structure
A file structure is given as follows:
What kind of a data structure can be used?
A possible data structure to be used: