Implementarea structurii de date Matrice Rara in C++ utilizand lista simplu inlantuita

Structurile de stocare a matricelor rare sunt prezentate la […].
Lista simpla este o structura de date liniara, formata din elemente denumite noduri. Un nod este compus din doua categorii de campuri:

  • Campul cu informatia necesara prelucrarii;
  • Campul cu informatia de legatura cu nodul succesor in cadrul structurii de tip lista simpla; se defineste sub forma de pointer catre structura nodului pentru a retine adresa nodului care urmeaza in cadrul listei simple.


Particularitati ale structurii de tip lista simpla:

  • Informatia de legatura a ultimului nod este nula: cei 4 octeti rezervati in memorie contin valori nule;
  • Gestionarea structurii se realizeaza printr-o variabila de tip pointer spre structura declarata a nodului; adresa primului nod si campurile cu informatiile de legatura asigura referirea si utilizarea nodurilor din lista simpla;
  • Utilizarea extensiva a memoriei heap pentru stocarea nodurilor listei.

Pentru a implementa o structura de date de tip matrice rara printr-o structura de tip lista simpla, informatia utila a unui nod este data de tuplul (index_linie, index_coloana, valoare_nenula). Declararea structurii unui nod este:

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

struct NodMR{
	ElementMR tuplu;
	NodMR *next;
};

Ca si in cazul utilizarii vectorului, se procedeaza la conversie, similar […]. Functia de conversie are denumirea ConversieToLSMatriceRara, avand ca tip de return NodMR*, respectiv adresa primului nod din lista simpla. Ca si in situatia utilizarii unui vector, conversia se realizeaza daca ponderea elementelor nenule in cadrul matricei se afla in intervalul [0,0015; 0,03]. In cazul realizarii conversiei, functia apeleaza o alta functie de inserare la sfarsit a unui nod intr-o lista simpla. Aplicatia de conversie realizata in C++ este:

#include 

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;" 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;" 0;="" nodmr*="" stergereinc(nodmr*="" l){="" if(l){="" 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;
	}
}

Alaturi de functia de conversie, in cadrul aplicatiei au fost dezvoltate inca doua functii pentru:

  • Inserarea unui nod la sfaristul listei simple cu un nou tuplu preluat din masivul bidimensional: InserareSf;
  • Stergerea unui nod la inceputul listei simple: StergereInc;
  • Extragerea adresei nodului aflat pe o pozitie data: ExtragereInfNodPoz.

Functia de inserare la sfarsit permite popularea cu tupluri a listei simple in vederea stocarii matricei rare.
La iesirea din aplicatie, functia de stergere la inceput este utilizata pentru a dezaloca memoria heap de nodurile listei de stocare a matricei rare.
Extragerea nodului de pe o anumita pozitie este implementata pentru a putea traversa lista simpla prin returnari succesive ale adreselor celor nrEl noduri. Scopul este de a afisa tuplurile stocate in lista simpla.