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.