Matrice

MATRIX - BIDIMENSIONAL ARRAY

Matricea este un tablou bidimensional static. Fără a da specificaţia completă a TAD Matrice, putem enumera un
număr minim de operaţii ȋn interfața sa:

− creează(m, nrLin, nrCol) constructor - creează matricea nulă m având nrLin linii şi nrCol coloane
− nrLinii(m) returnează numărul de linii
− nrColoane(m) returnează numărul de coloane
− element(m, i, j, e) accesare element de pe linia i şi coloana j – e este elementul accesat
− modifică(m, i, j, e) înlocuirea cu e a elementului de pe linia i şi coloana j
în cazul în care elementul nu exista, îl adaugă

Alte operaţii posibile: căutare element şi returnarea (liniei, coloanei) pe care a fost găsit, iterator pentru accesare
elemente în ordinea liniilor, iterator pentru accesare elemente în ordinea coloanelor, etc.

Observații

1. Ȋn general, tablourile bidimensionale se memorează secvențial

2. Generalizare - tablouri bidimensionale dinamice.
3. În cazul în care multe elemente ale matricei sunt nule ( 0 TElement ) – matrice rară -, nu este eficientă
memorarea tuturor elementelor matricei, ci doar a elementelor nenule.

În continuare vom discuta posibilităţi de reprezentare/implementare a matricelor rare. Vom lua un exemplu
concret, matricea de mai jos

 0 −2 0 −7 0 
 
− 6 0 0 0 0 
 0 − 9 − 8 0 − 5
 
 0 0 − 2 
 0 0

A. Reprezentare prin triplete Linie, Coloana, Valoare (Valoare  0 TElement ), ordonate lexicografic crescător în
raport cu Linie, Coloana. Pentru exemplul de mai sus se vor memora următoarele triplete:

Linie 1 1 2 3 3 3 4
Coloana 2 4 1 2 3 5 5
 Valoare -2 -7 -6 -9 -8 -5 -2

Tripletele se pot memora folosind

− un vector (dinamic) ordonat - reprezentare secvenţială
− o listă înlănţuită ordonată (reprezentare înlănţuită)
▪ înlănţuirile reprezentate folosind alocare dinamică
▪ înlănţuirile reprezentate folosind alocare statică pe tablou
− un arbore binar de căutare/arbore AVL

B. Reprezentare condensată pe coloane. Se folosesc 3 vectori: Linie, Coloana, Valoare cu următoarea

semnificaţie: elementele de pe coloana j (j=1,2…,nrCol) se află pe liniile
LinieColoanaj, LinieColoanaj+1,…, LinieColoanaj+1-1
şi au valorile
ValoareColoanaj, ValoareColoanaj+1,…, ValoareColoanaj+1-1

Pentru exemplul de mai sus se vor memora următorii vectori:

− Coloana – avȃnd nrCol+1 elemente
− Linie, Valoare – a căror dimensiune=nr. de elemente nenule din matrice

indice 1 2 3 4 5 6
Coloana 1 2 4 5 6 8

indice 1 2 3 4 5 6 7
Linie 2 1 3 3 1 3 4
Valoare -6 -2 -9 -8 -7 -5 -2

C. Reprezentare condensată pe linii. Se folosesc 3 vectori: Coloana, Linie, Valoare cu următoarea

semnificaţie: elementele de pe linia i (i=1,2…,nrLin) se află pe liniile
ColoanaLiniei, ColoanaLiniei+1,…, ColoanaLiniei+1-1
şi au valorile
ValoareLiniei, ValoareLiniei+1,…, ValoareLiniei+1-1

Pentru exemplul de mai sus se vor memora următorii vectori:

− Linie – avȃnd nrLin+1 elemente
− Coloana, Valoare – a căror dimensiune=nr. de elemente nenule din matrice

indice 1 2 3 4 5
Linie 1 3 4 7 8

indice 1 2 3 4 5 6 7
Coloana 2 4 1 2 3 5 5
Valoare -2 -7 -6 -9 -8 -5 -2
D. Reprezentare înlănţuită folosind liste circulare
− Colecție de liste circulare interconectate

Exemplu
7 0 0 0 
 
5 9 0 6 
0 8 0 0 
 
7 
 0 0 0 