Structuri de date

Studiul tablourilor unidimensionale și bidimensionale ca modalități de organizare a datelor în memorie.

Tablouri unidimensionale (vectori)

Un tablou unidimensional (vector) este o colecție de elemente de același tip, memorate contiguu (una lângă alta) în memorie și identificate printr-un singur nume plus un indice. În C++ declarația int v[100]; rezervă loc pentru 100 de întregi, iar elementele se accesează cu v[0], v[1], ..., v[99].

Două lucruri trebuie fixate de la început, pentru că generează cele mai multe erori:

• indexarea începe de la 0 în C++: primul element este v[0], iar ultimul dintr-un vector cu n elemente este v[n-1], NU v[n]. Accesarea lui v[n] iese din tablou și produce comportament imprevizibil;
• dimensiunea declarată este capacitatea maximă, iar numărul de elemente efectiv folosite (n, citit de la tastatură) este de obicei mai mic. Subiectele de examen lucrează mereu cu n, nu cu capacitatea.

În pseudocodul de bacalaureat vectorii apar deseori indexați de la 1 la n — citește cu atenție enunțul, pentru că un raționament corect cu indexare greșită dă rezultat greșit.

Avantajul esențial al vectorului: accesul la orice element se face direct, în timp constant, cunoscând doar indicele — spre deosebire de datele citite una câte una, pe care nu le mai poți revizita.

Parcurgerea și prelucrările elementare

Parcurgerea înseamnă vizitarea elementelor unui vector, de regulă de la primul la ultimul, cu o structură pentru: pentru i ← 0, n-1 execută prelucrează v[i]. Pe acest schelet se construiesc prelucrările standard:

• suma elementelor: s ← 0, apoi la fiecare pas s ← s + v[i]; inițializarea cu 0 înainte de buclă este obligatorie;
• numărarea elementelor cu o proprietate (pare, pozitive, divizibile cu k): contor inițializat cu 0, incrementat doar când condiția e îndeplinită;
• minimul și maximul: se inițializează min cu primul element al vectorului, apoi fiecare element îl compară și îl înlocuiește dacă e mai mic. Inițializarea cu 0 este o greșeală clasică: pentru un vector cu toate elementele pozitive, minimul ar rămâne 0 — o valoare care nici nu există în vector;
• căutarea secvențială: parcurgi elementele până găsești valoarea căutată sau până se termină vectorul; rezultatul util e de obicei poziția, nu doar răspunsul da/nu.

O idee care apare des în subiecte: parcurgerea simultană de la ambele capete (i de la început, j de la sfârșit) — de exemplu pentru a verifica dacă vectorul e palindrom sau pentru a-l inversa fără vector suplimentar, interschimbând v[i] cu v[j] cât timp i < j.

Sortarea unui vector

A sorta înseamnă a rearanja elementele în ordine crescătoare sau descrescătoare. Doi algoritmi elementari sunt de știut cu pașii lor:

• Sortarea prin selecție: la pasul i se caută minimul din porțiunea nesortată (de la i la n-1) și se interschimbă cu elementul de pe poziția i. După pasul i, primele i+1 elemente sunt definitiv la locul lor. Face mereu același număr de comparații, indiferent de datele de intrare.
• Sortarea prin interschimbare (bubble sort): se compară perechi de elemente vecine și se interschimbă cele în ordine greșită; parcurgerile se repetă până când o trecere completă nu mai face nicio interschimbare. Pe un vector deja sortat se oprește după o singură trecere — de aceea pe date aproape ordonate e mai rapid decât selecția.

Operația de bază a ambilor este interschimbarea (swap) a două elemente, care cere o variabilă auxiliară: aux ← a; a ← b; b ← aux. Scrierea a ← b; b ← a pierde valoarea inițială a lui a — ambele variabile rămân cu valoarea lui b.

De reținut și utilitatea sortării: într-un vector sortat, minimul și maximul sunt la capete, elementele egale devin vecine (utile la eliminarea duplicatelor), iar căutarea unei valori poate folosi metode mult mai rapide decât parcurgerea completă.

Tablouri bidimensionale (matrice)

Un tablou bidimensional (matrice) organizează datele pe linii și coloane: int a[10][10]; declară o matrice, iar a[i][j] este elementul de pe linia i, coloana j — în această ordine, mereu. Inversarea indicilor (coloană, linie) este una dintre cele mai frecvente erori de punctaj.

Parcurgerea completă folosește două bucle imbricate: cea exterioară pentru linii, cea interioară pentru coloane. Cu bucla exterioară pe i și cea interioară pe j, matricea se parcurge pe linii; inversând buclele, se parcurge pe coloane.

Pentru o matrice pătratică (același număr n de linii și coloane) se definesc zonele clasice:

• diagonala principală: elementele a[i][i], adică cele cu i = j — din colțul stânga-sus în colțul dreapta-jos;
• diagonala secundară: elementele cu i + j = n - 1 (la indexare de la 0) — din colțul dreapta-sus în colțul stânga-jos;
• deasupra diagonalei principale: i < j; sub ea: i > j.

Prelucrări tipice de examen: suma elementelor de pe o linie dată, maximul de pe fiecare coloană, suma elementelor de pe diagonale, verificarea simetriei față de diagonala principală (a[i][j] = a[j][i] pentru orice i și j).

Subprograme care prelucrează tablouri

Prelucrările pe tablouri se împachetează natural în subprograme: o funcție care întoarce suma elementelor unui vector, o procedură care citește o matrice, o funcție care caută o valoare și întoarce poziția ei.

Particularitatea esențială în C++: tablourile se transmit prin adresă, nu prin valoare. Când dai un vector ca parametru unei funcții, funcția NU primește o copie, ci lucrează direct pe elementele originale — orice modificare făcută în subprogram rămâne după revenirea din apel. La variabilele simple (int, double) e invers: implicit se transmite o copie, iar modificările se pierd.

Consecințe practice:

• o funcție de sortare primită ca cerință modifică vectorul chiar dacă nu returnează nimic;
• pe lângă tablou se transmite separat și numărul de elemente n, pentru că din interiorul funcției dimensiunea utilă nu se poate deduce;
• antetul tipic arată astfel: void sortare(int v[], int n) — parantezele drepte goale semnalează că v este tablou.

Descompunerea în subprograme nu e doar eleganță: subiectul III de la bacalaureat cere explicit definirea unor subprograme cu antet impus, deci exersarea scrierii lor corecte (tip returnat, parametri, apel) aduce puncte direct.

Test — 6 întrebări ca la examen