MATRICE RARE
Matricea completa MC definita prin:
tip nume [NL][NC];
ocupa o zona de memorie LG(MC) = NL * NC * LG(tip element din matrice)
Matricea de dimensiuni mare este supusa unei analize de continutin care:
- se construieste stiva cu elementele diferite
- se calculeaza frecventele de aparitie a elementelor diferite.
In matricea:
{ 0, 0, 0, 0, 0, 0 , 1, 4, 0, 0},
{ 0, 0, 0, 0, 0, 0 , 0, 0, 0, 0},
{ 0, 0, 0, 3, 0, 0 , 0, 3, 0, 9},
{ 0, 0, 8, 0, 0, 0 , 0, 5, 0, 0},
{ 0, 0, 0, 0, 0, 0 , 1, 4, 0, 0},
{ 0, 1, 1, 0, 0, 1 , 1, 0, 0, 0},
{ 0, 0, 0, 0, 0, 0 , 1, 4, 0, 0},
{ 0, 4, 4, 0, 0, 0 , 4, 4, 0, 0},
{ 0, 0, 0, 0, 0, 0 , 7, 4, 0, 0},
{ 0, 0, 0, 7, 7, 0 , 0, 0, 0, 7}
};
valorile diferite sunt 0, 1, 3, 4, 5, 7, 8, 9
iar frecventele lor de aparitie sunt:
element
frecventa
0
f
1
f
3
f
4
f
5
f
7
f
8
f
9
f
Se vede din analiza de continut ca elementul 0 apare foarte frecvent, ceea ce inseamna ca matricea trebuie privita ca MATRICE RARA. Reprezentarea prin 3 vectori a matricei rare presupune:
- definirea unui vector V 1cu M componente pentru a memora pozitia pe linie a elementului nenul din matricea rara
- definirea unui vector V 2cu M componente pentru a memora pozitia pe coloana a elementului nenul din matricea rara
- definirea unui vector V 3cu M componente pentru a memora valoarea elementului nenul din matricea rara
- matricea rara are K elemente nenule. Reprezentarea prin lista simpla a matricei rare presupune:
- definirea a K elemente ce au informatia utila formata din pozitia liniei, pozitia coloanei unde se afla elementul nenul si valoarea acestuia
- definirea in element a variabilei pointer care asigura legatura cu elementul urmator din lista. Reprezentarea prin lista dubla a matricei rare presupune:
- definirea a K elemente ce au informatia utila formata din pozitia liniei, pozitia coloanei unde se afla elementul nenul si valoarea acestuia
- definirea in element a variabilei pointer care asigura legatura cu elementul urmator din lista
- definirea in element a variabilei pointer care asigura legatura cu elementul precedent din lista dubla din lista. Reprezentarea prin liste de liste a matricei rare presupune:
- definirea unei liste de baza cu atatea elemente cate linii cu elemente nenule are matricea; se noteaza H numarul liniilor care au elemente nenule
- liste derivate, avand atatea elemente cate elemente nenule se afla pe cate o linie
- un element al listei de baza contine: linia cu elemente nenule, pointer care refera primul element din lista derivata si pointer care permite referirea urmatorului element al listei de baza
- un element al listei derivate contine pozitia coloanei pe care se afla un element nenul, valoarea elementului si un pointer care leaga elementele fiecarei liste derivate.
Pentru fiecare reprezentare se determina:
- lungimi de zone de memorie
- conditii necesare ca respectivele reprezentari sa fie eficiente.
proceduri necesare a fi scrise:
- procedura pentru initializarea de la tastatura a unei matrice complete
- procedura pentru initializarea matricei rare prin introducerea numai a elementelor nenule, specificand linia, coloana si valoarea
- procedura pentru transformarea unei matrice complete in matrice rara reprezentata prin 3 vectori
- procedura pentru transformarea unei matrice complete in matrice rara reprezentata prin lista simpla
- procedura pentru transformarea unei matrice complete in matrice rara reprezentata prin lista dubla
- procedura pentru transformarea unei matrice complete in matrice rara reprezentata prin lista de liste
- procedura pentru normatizarea matricei reprezentate prin 3 vectori
- procedura pentru normatizarea matricei reprezentate prin lista simpla
- procedura pentru normatizarea matricei reprezentate prin lista dubla
- procedura pentru normatizarea matricei reprezentate prin lista de liste
- proceduri pentru efectuarea de calcule matriceale .
Gasiti detalii la www.ionivan.ro->teaching->bachelor->data structures->curricula ->matrice rare