Tablouri

Tablouri

Un tablou este o secventa de componente de acelasi tip. Acest tip poate fi un tip primitiv sau un tip referinta (putem lucra cu tablouri de obiecte).

Un tablou a poate fi declarat folosind una dintre urmatoarele modalitati:

tip[] a;

tip a[];

unde tip este tipul componentelor tabloului (!!nu se specifica un numar de elemente).

Declararea unui tablou nu are drept consecinta crearea sa (alocarea memoriei necesare). Crearea (instantierea) tabloului a declarat mai sus trebuie facuta explicit, prin:

a = new tip[n];

unde n poate fi o constanta sau o variabila intreaga ce a primit o valoare strict pozitiva.

Un tablou este un tip referinta. Prin creare se obtine un obiect de tip tablou (obiect numit prin abuz de limbaj tot tablou).

Componentele tabloului pot fi referite prin a[i], cu i luand valori in intervalul 0..n-1; daca i nu este in acest interval, va fi semnalata o eroare la executare (exceptia IndexOutOfBoundsException). Lungimea tabloului poate fi referita prin a.length.

Declararea si crearea pot fi facute si simultan prin:

tip[] a = new tip[n];

sau printr-o initializare efectiva, ca de exemplu:

int[] a =

prin care, evident, a.length devine 5.

Campul length al unui (obiect de tip) tablou este un camp constant (cu modificatorii public si final) de tip int; deci, odata creat, un obiect tablou nu isi poate schimba dimensiunea (numarul de componente).

Copierea elementelor unui vector a intr-un alt vector b se poate face fie

element cu element, fie cu ajutorul metodei System.arraycopy, ca in exemplele

de mai jos (!! b trebuie sa fie deja alocat). System.arraycopy primeste ca parametrii vectorul sursa, indicele de la care incepe copierea, vectorul destinatie, indicele din vectorul destinatie incepand de la care sunt puse elementele copiate si numarul de elemente copiate.

O atribuire de genul b = a are alta semnificatie decat copierea elementelor lui a in b si nu poate fi folosita in acest scop. Este o atribuire de referinte, in urma acestei atribuiri variabilele b si a vor referi acelasi obiect (vector). Daca modificam un element al lui a se modifica si b si invers, cele doua variabile referind, asa cum precizam, acelasi vector.

int a[] = ;

int b[] = new int[4];

// Varianta 1

for(int i=0; i<a.length; i++)

b[i] = a[i];

// Varianta 2

System.arraycopy(a, 0, b, 0, a.length);

// Nu are efectul dorit

b = a;

System.out.println(a[0]+' '+b[0]);

b[0] = 5;

System.out.println(a[0]+' '+b[0]);

a[0] = 6;

System.out.println(a[0]+' '+b[0]);

Tablourile multidimensionale trebuie gandite ca tablouri unidimensionale ale caror elemente sunt tablouri unidimensionale etc. De aceea referirea la un element al unui tablou multidimensional a se face prin:

a[indice1][indicen].

Este suficient sa reducem discutia la tablouri bidimensionale, generalizarea fiind imediata. Sa consideram urmatorul exemplu:

int[][] a = new int[3][];

a[0] = new int[3];

a[1] = new int[4];

a[2] = new int[2];

Ia nastere astfel un tablou de forma:

ceea ce arata ca in Java tablourile nu sunt neaparat dreptunghiulare; aceasta conduce desigur la economie de spatiu.

Evident, a[1].length=4.

La aceeasi structura se poate ajunge si printr-o initializare efectiva:

int[][] a = , , };

care in plus atribuie valori elementelor tabloului.

Daca in referirea la un element al unui tablou unul dintre indici nu este in intervalul corespunzator, va aparea exceptia IndexOutOfBoundsException.

O implementare a vectorilor cu numar variabil de elemente este oferita, de exemplu, de clasa Vector din pachetul java.util.

Exercitii:

1. Sa se creeze o clasa MatriceTriunghiulara care are doua campuri: un numar intreg n si un tablou bidimensional a de numere intregi, precum si doua metode:

- o metoda pentru citirea matricei inferior triunghiulara a de dimensiune n

- o metoda de afisare a acestei matrice.

Sa se scrie o clasa principala in care sa se creeze si sa se afiseze o matrice inferior triunghiulara, folosind clasa MatriceTriunghiulara

De exemplu:

n=4

a=

3

4 7

9 0 6

1 5 8 2

(matricea se va afisa sub aceasta forma triunghiulara)

2. Scrieti o clasa care sa reprezinte o structura de tip coada. Clasa va avea metode pentru inserarea unui element in coada, stergerea unui element din coada, testarea daca este vida, afisare. Folosind aceasta clasa scrieti o noua clasa pentru determinarea componentelor conexe ale unui graf folosind parcurgerea in latime (pentru reprezentarea grafului se vor folosi liste de vecini (de adiacenta)). Afisati, in plus, cate muchii sunt necesare sa adaugam grafului pentru a deveni conex.

Reamintim algoritmul pentru parcurgea pe latime a componentei conexe a lui i₀, folosind o coada C ; operatiile de introducere in coada si elimiare din coada sunt simbolizate prin T , respectiv

for i=1,n

vizitat(i) false

C ; i₀ T C; vizitat(i₀) true

while C

i C; vizit(i);

for toti j vecini ai lui i

if not vizitat(j)

then j T C; vizitat(j)true