How to: Implement a Sparse Matrix Data Structure in C++ Using Simple Linked List

1 comment - This post in romanian

The storage structures for sparse matrixes are presented at [...].
The simply linked list is a linear data structure, formed by elements called nodes. A node is composed by two categories of fields:

  • The field with the information necessary for processing;
  • The field with the information for connecting with the successor node in the simply linked list type structure; it is defined as a pointer to the structure of the node in order to retain the address of the next node in the simply linked list.


The function for insertion at the end allows the completion with triplets of the simply linked list for the sparse matrix storage.
On leaving the application, the function for deleting at the beginning is used to free the heap memory from the nodes of the storage list of the sparse matrix.
Extracting a node on a certain position is implemented in order to cross over the simply linked list by successive returns of the addresses of the nrEl nodes. The aim is to display the triplets stored in the simply linked list.
Particularities of the simply linked list type structure:

  • The connecting information for the last node is null: the 4 octets reserved in the memory contain null values;
  • The management of the structure is made by a pointer type variable towards the declared structure of the node; the address of the first node and fields with the linking information assure the reference and the usage of the nodes in the simply linked list;
  • The extensive usage of the heap memory for the storage of the nodes in the list.

In order to implement a data structure of sparse matrix type through a structure of simply linked list, the useful information of a node is given by the triplet >(index_line, index_colomn, notnull_value). The declaration of a node structure is:

struct ElementMR{
	unsigned int l,c;
	double val;
};
 
struct NodMR{
	ElementMR tuplu;
	NodMR *next;
};

As in the case of using an array, the conversion is started, similar to [...]. The conversion function is called ConversieToLSMatriceRara, having as a return type NodMR*, respectively the address of the first node in the simply linked list. As in the situation of using an array, the conversion is done if the weight of the matrix not null elements in the interval [0.0015; 0.03]. In case of conversion, the function calls another function by inserting at the end a node in a simply linked list. The conversion application developed in C++ is:

#include <iostream>
 
using namespace std;
 
struct ElementMR{
	unsigned int l,c;
	double val;
};
 
struct NodMR{
	ElementMR tuplu;
	NodMR *next;
};
 
NodMR* InserareSf(NodMR* l,ElementMR e){
	NodMR* nou=new NodMR;
	nou->tuplu=e;
	nou->next=NULL;
	if(!l)
		return nou;
	else{
		NodMR* temp=l;
		while(temp->next)
			temp=temp->next;
		temp->next=nou;
		return l;
	}
}
 
NodMR* ConversieToLSMatriceRara(double A[][100], unsigned int m, unsigned int n, \
char *err, unsigned int *nrEl){
	*nrEl=0;
	unsigned int i,j;
	NodMR *lstMR=NULL;
	for(i=0;i<m;i++)
		for(j=0;j<n;j++)
			if(A[i][j])
				(*nrEl)++;
	double pondere=*nrEl;
	pondere=pondere/(m*n);
	if(pondere>=0.0015 && pondere<=0.03){
		*err=1;
		for(i=0;i<m;i++)
			for(j=0;j<n;j++)
				if(A[i][j]){
					ElementMR t;
					t.l=i+1;
					t.c=j+1;
					t.val=A[i][j];
					lstMR=InserareSf(lstMR,t);
				}
		return lstMR;
	}
	else{
		*err=0;
		return 0;
	}
}
 
NodMR* StergereInc(NodMR* l){
	if(l){
		NodMR* temp=l;
		l=l->next;
		delete temp;
	}
	return l;
}
 
 
NodMR* ExtragereNodPoz(NodMR* l,unsigned int poz, unsigned int n){
	if(poz<1 || poz >n)
		return 0;
	else{
		NodMR *temp=l;
		unsigned int i;
		for(i=1;i<poz;i++)
			temp=temp->next;
		return temp;
	}
}
 
void main(){
	double Mat[25][100],val;
	unsigned int m, n, i, j;
	unsigned int nrEl;
	char err;
	m=25;
	n=100;
	NodMR *lstMatRara=NULL;
	for(i=0;i<m;i++)
		for(j=0;j<n;j++)
			Mat[i][j]=0;
 
	char opt='y';
	while(opt=='y'){
		do{
			cout<<"Give the row index of the not-null element: ";
			cin>>i;
		}
		while(i>25 || i==0);
		do{
			cout<<"Give the column index of the not-null element:";
			cin>>j;
		}
		while(j>100 || j==0);
		cout<<"Give the value of the not-null element: ";
		cin>>val;
		if(!Mat[i-1][j-1])
			Mat[i-1][j-1]=val;
		else{
			cout<<"Give the position containing the not-null \
element! Overwrite the element?(y/n): ";
			cin>>opt;
			if(opt=='y')
				Mat[i-1][j-1]=val;
		}
		cout<<"Continue?(y/n): ";
		cin>>opt;
	}
 
	lstMatRara=ConversieToLSMatriceRara(Mat,m,n,&err,&nrEl);
 
	if(err){
		cout<<"Structure of type Sparse Matrix is:"<<endl;
		//displaying the linked list
		for(i=1;i<=nrEl;i++){
			NodMR *t;
			t=ExtragereNodPoz(lstMatRara,i,nrEl);
			if(t){
				cout<<t->tuplu.l<<"\t"<<t->tuplu.c<<"\t" \
<<t->tuplu.val<<endl;
			}
		}
 
		//deleting the linked list
		while(lstMatRara)
			lstMatRara=StergereInc(lstMatRara);
	}
	else
		cout<<"The two-dimensional array does not meet \
the criteria to be sparse matrix!"<<endl;
}

Together with the conversion function, within the application were developed two more functions for:

  • Inserting a node at the end of the simply linked list with a new triplet taken from the two-dimensional array: InserareSf;
  • Erasing a new node at the beginning of the simply linked list: StergereInc;
  • Extraction of the address of the node situated on a given position: ExtragereInfNodPoz.

, , , ,