Matricea rara reprezinta in tip special de masiv dimensional format dintr-un numar foarte mare de elemente din care o pondere foarte mare o ocupa elementele nule. Astfel, declararea clasica a unui masiv bidimensional in limbajul C++ conduce la utilizarea inutila a memoriei prin stocarea valorilor nule si a capacitatii de procesare.

Declararea unei structuri de date de tip matrice rara se bazeaza pe urmatoarele elemente:

• Valori nenule;
• Pozitia valorilor nenule in cadrul masivului bidimensional.

Avantaje ale utilizarii matricelor rare:

• Reducerea cerintelor de utilizare a memoriei;
• Reducerea timpului de procesare prin eliminarea operatiilor inutile cu valori nule.

Dezavantaje ale utilizarii matricelor rare:

• Spatiu de memorie necesar stocarii matricei rare mult mai mare daca numarul de valori nenule nu este mult mai mic de numarul de valori nule;
• Implementare mai dificila a operatiilor la nivel de matrice datorita modului de acces indirect prin structura de date definita pentru stocarea matricei rare.

Structuri de stocare a matricelor rare:

• Trei vectori pentru stocarea valorilor indicelui de linie, indicelui de coloana si a valorii nenule; in forma liniarizata, primii doi vectori se inlocuiesc cu indexul liniarizat;
• Structura de tip articol cu urmatoarele campuri: indice de linie, indice de coloana si valoarea nenula; articolele sunt stocate intr-un vector sau lista liniara;
• Vector pe biti pentru marcarea pozitiei elementului nenul in matricea liniarizata si un vector pentru stocarea valorilor nenule.

Masivele bidimensionale cu un numar foarte mare de valori nule sunt stocate sub forma de matrice rare daca valorile nule ocupa intre 0,15% si 3% din numarul total de elemente al matricei.
In exemplul urmator, varianta de stocare a matricei rare este structura de tip articol pentru retinerea indicelui de linie, indicelui de coloana si a valorii nenule.

struct ElementMR{
	unsigned int i,j;
	double val;
};

Articolele sunt memorate intr-un vector alocat in memoria heap. Numarul elementelor vectorului este dat de numarul de elemente nenule ale masivului bidimensional.
In programul urmator, se defineste o matrice in mod clasic, fara a fi alocata in memoria heap. Se verifica conditia de existenta a matricei rare. In cazul in care aceasta conditie este indeplinita, se procedeaza la conversia masivului bidimensional in structura de tip matrice rara, stocata sub forma de vector de articole, prezentat mai sus. Conversia se realizeaza prin intermediul functiei ConversieToMatriceRara(double [][100],unsigned int,unsigned int,char*,unsigned int*).

#include 

using namespace std;

struct ElementMR{
	unsigned int l,c;
	double val;
};

ElementMR* ConversieToMatriceRara(double A[][100], unsigned int m, unsigned int n, \
char *err, unsigned int *nrEl){
	*nrEl=0;
	unsigned int i,j;
	ElementMR *pTuplu;
	for(i=0;i<m;i++) for(j="0;j<n;j++)" if(a[i][j])="" (*nrel)++;="" double="" pondere="*nrEl;" if(pondere="">=0.0015 && pondere<=0.03){
		*err=1;
		pTuplu=new ElementMR[*nrEl];
		unsigned int k=0;
		for(i=0;i<m;i++) for(j="0;j<n;j++)" if(a[i][j]){="" ptuplu[k].l="i+1;" ptuplu[k].c="j+1;" ptuplu[k].val="A[i][j];" k++;="" }="" return="" ptuplu;="" else{="" *err="0;" 0;="" void="" main(){="" double="" mat[25][100],val;="" unsigned="" int="" m,="" n,="" i,="" j;="" nrel;="" char="" err;="" m="25;" n="100;" elementmr="" *pmatrara="NULL;" for(i="0;i<m;i++)" mat[i][j]="0;" opt="d" ;="" while(opt="='d'){" do{="" cout<<"introduceti="" indexul="" de="" linie="" a="" elementului="" nenul:="" ";="" cin="">>i;
		}
		while(i>25 || i==0);
		do{
			cout<<"Introduceti indexul de coloana a elementului \
nenul: ";
			cin>>j;
		}
		while(j>100 || j==0);
		cout<<"Introduceti valoarea elementului nenul: ";
		cin>>val;
		if(!Mat[i-1][j-1])
			Mat[i-1][j-1]=val;
		else{
			cout<<"Pozitia indicata contine un element de valoare \
nenula! Rescrieti elementul?(d/n): ";
			cin>>opt;
			if(opt=='d')
				Mat[i-1][j-1]=val;

		}
		cout<<"Continuati?(d/n): ";
		cin>>opt;
	}

	pMatRara=ConversieToMatriceRara(Mat,m,n,&err,&nrEl);

	if(err){
		cout<<"Structura de tip Matrice Rara este:"<<endl; for(i="0;i<nrEl;i++)" cout<<pmatrara[i].l<<"\t"<<pmatrara[i].c<<"\t"<<="" \="" pmatrara[i].val<<endl;="" delete="" []="" pmatrara;="" }="" else="" cout<<"masivul="" bidimensional="" nu="" indeplineste="" criteriile="" de="" matrice="" rara!"<<endl;="" }<="" pre="">

Semnificatiile variabilelor definite in functia main() sunt:

• Mat: masivul bidiomensional stocat in format clasic;
• m: numarul de linii al masivului Mat;
• n: numarul de coloane al masivului Mat;
• i: index de linie a masivului Mat;
• j: index de coloana a masivului Mat;
• nrEl: numarul de elemente nenule ale masivului Mat; numarul de elemente a vectorului pMatRara alocat in memoria heap;
• pMatRara: adresa zonei de memorie de lungime nrEl unde sunt stocate elementele structurii matrice rara;
• err: indicator de eroare privind efectuarea conversiei din masivul Mat in structura gestionata prin pMatRara.

Aplicatia de mai sus realizeaza initializarea intregului masiv Mat cu valori nule, validari ale datelor introduse de la tastatura, modificarea valorilor nule cu valori nenule pentru pozitiile specificate de la tastatura, conversia masivului Mat in structura matrice rara cu conditia asigurarii limitelor inferioara si superioara a ponderii elementelor nenule.