«
»

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

1 comment - This post in english

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 <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='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;
	}
 
	lstMatRara=ConversieToLSMatriceRara(Mat,m,n,&err,&nrEl);
 
	if(err){
		cout<<"Structura de tip Matrice Rara este:"<<endl;
		//afisare lista simpla
		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;
			}
		}
 
		//stergere lista simpla
		while(lstMatRara)
			lstMatRara=StergereInc(lstMatRara);
	}
	else
		cout<<"Masivul bidimensional nu indeplineste criteriile \
de matrice rara!"<<endl;
}

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.

, , , ,

This entry was posted on sâmbãtã, octombrie 31, 2009 and is filed under C++, Data Structures. You can follow any responses to this entry through RSS 2.0. You can leave a response, or trackback from your own site.


  1. No comments yet.
(will not be published)