Structuri de date

Studiul structurilor de date liniare și nelineare utilizate în programare.

Tablouri: alocare statică și acces direct

Un tablou este o structură de date care păstrează un număr fix de elemente de același tip, așezate contiguu în memorie. Din contiguitate rezultă proprietatea lui esențială: accesul direct — poți citi `v[i]` instantaneu, în timp O(1), pentru că adresa elementului se calculează aritmetic din adresa de start.

• Tablou unidimensional (vector): `int v[100];` — indicii merg în C++ de la 0 la 99. Confuzia clasică: mulți elevi cred că `v[100]` este ultimul element; de fapt este în afara tabloului, iar accesarea lui e o eroare care nu e semnalată de compilator.
• Tablou bidimensional (matrice): `int a[50][50];` — primul indice e linia, al doilea e coloana. La matrice pătratică de ordin n, diagonala principală are elementele cu `i == j`, iar diagonala secundară pe cele cu `i + j == n - 1` (cu indexare de la 0).

Costul flexibilității lipsă: inserarea sau ștergerea unui element în interiorul unui vector cere deplasarea tuturor elementelor de după el — operație O(n). Exact acest cost îl elimină listele înlănțuite, cu prețul pierderii accesului direct. La examen se cere să știi când alegi tabloul: număr cunoscut (sau mărginit) de elemente și acces frecvent după poziție.

Liste liniare simplu și dublu înlănțuite

O listă înlănțuită este o colecție de noduri alocate dinamic, în care fiecare nod conține informația utilă și adresa nodului următor. Nodurile NU sunt vecine în memorie — legătura e dată exclusiv de pointeri.

• Lista simplu înlănțuită: fiecare nod are un singur pointer, `urm` (către succesor). Se poate parcurge doar înainte, pornind de la primul nod (capul listei). Ultimul nod are `urm == NULL`.
• Lista dublu înlănțuită: fiecare nod are doi pointeri, `urm` și `prec`. Se poate parcurge în ambele sensuri, iar ștergerea unui nod cunoscut se face fără să cauți predecesorul.

Operațiile de bază și costurile lor, comparate cu vectorul:

• inserare/ștergere la o poziție cunoscută: O(1) — doar se rearanjează pointerii, nimic nu se deplasează;
• accesul la al k-lea element: O(k) — trebuie parcursă lista de la cap; NU există acces direct.

Greșeala de punctaj cea mai frecventă: la ștergerea unui nod, elevii eliberează memoria înainte de a salva adresa succesorului — după `delete p` nu mai ai voie să citești `p->urm`. Ordinea corectă: salvezi legătura, refaci înlănțuirea, abia apoi eliberezi nodul. La inserarea în față nu uita să actualizezi capul listei.

Stiva (LIFO) și coada (FIFO)

Stiva și coada sunt liste cu acces restricționat — nu structuri complet noi, ci liste la care ai voie să lucrezi doar la capete.

• Stiva funcționează pe principiul LIFO (Last In, First Out — ultimul intrat, primul ieșit). Operații: push (adaugă în vârf), pop (scoate din vârf), top (consultă vârful fără scoatere). Toate se fac la același capăt, numit vârful stivei.
• Coada funcționează pe principiul FIFO (First In, First Out — primul intrat, primul ieșit). Adaugi la un capăt (spate) și scoți de la celălalt (față).

Aplicații care apar constant în subiecte:

• stiva: apelurile de subprograme și recursivitatea (stiva de execuție), verificarea parantezării corecte, conversia numerelor între baze, parcurgerea DFS;
• coada: gestionarea cererilor în ordinea sosirii, parcurgerea BFS a grafurilor, simularea firelor de așteptare.

Confuzia clasică de examen: la o stivă în care se introduc pe rând 1, 2, 3, elementele ies în ordinea 3, 2, 1; la coadă ies exact în ordinea 1, 2, 3. Dacă un subiect cere conținutul structurii după o secvență amestecată de introduceri și extrageri, lucrează pe hârtie pas cu pas — orice sărit de pas se plătește.

Arbori binari: terminologie și parcurgeri

Un arbore binar este o structură ierarhică în care fiecare nod are cel mult doi descendenți: un fiu stâng și un fiu drept. Termenii care se cer la examen:

• rădăcina — nodul fără părinte (unic);
• frunză — nod fără niciun descendent;
• înălțimea — lungimea celui mai lung drum de la rădăcină la o frunză;
• nivelul unui nod — distanța lui față de rădăcină (rădăcina e pe nivelul 0 sau 1, după convenția din enunț — citește enunțul!).

Cele trei parcurgeri în adâncime, definite prin poziția rădăcinii (R) față de subarbori (S = stâng, D = drept):

• preordine (RSD): rădăcină, subarbore stâng, subarbore drept;
• inordine (SRD): subarbore stâng, rădăcină, subarbore drept;
• postordine (SDR): subarbore stâng, subarbore drept, rădăcină.

Proprietate care rezolvă multe grile: într-un arbore binar de căutare (fiecare nod e mai mare decât tot subarborele stâng și mai mic decât tot subarborele drept), parcurgerea inordine produce elementele în ordine crescătoare. Capcană frecventă: parcurgerile diferă doar prin momentul vizitării rădăcinii, ordinea subarborilor stâng-drept rămâne aceeași; cine inversează S cu D pierde toate valorile din listă.

Grafuri: reprezentare și parcurgere

Un graf G = (V, M) este format dintr-o mulțime de vârfuri (noduri) și o mulțime de muchii (la graf neorientat) sau arce (la graf orientat). Noțiuni cerute la examen:

• gradul unui vârf — numărul de muchii incidente lui; într-un graf neorientat, suma gradelor = 2 × numărul de muchii (fiecare muchie contribuie la două grade);
• la graf orientat se separă gradul intern (arce care intră) și gradul extern (arce care ies);
• lanț/drum, ciclu/circuit, graf conex (există lanț între oricare două vârfuri), componentă conexă.

Reprezentări:

• matricea de adiacență a[i][j] = 1 dacă există muchie de la i la j, altfel 0; pentru graf neorientat matricea este simetrică și are 0 pe diagonala principală; ocupă O(n²) indiferent de numărul de muchii;
• listele de adiacență — pentru fiecare vârf, lista vecinilor; economice la grafuri rare.

Parcurgeri: BFS (în lățime) vizitează vârfurile în ordinea distanței față de sursă și folosește o coadă; DFS (în adâncime) merge cât poate pe o ramură și revine, folosind o stivă (sau recursivitatea, care e tot o stivă). Grilă clasică: BFS ↔ coadă, DFS ↔ stivă — cine le inversează cade exact în distractorul pregătit.

Heap-ul: arbore binar cu proprietate de ordine

Un heap (max-heap) este un arbore binar complet în care fiecare nod este mai mare sau egal decât fiii săi. Din definiție rezultă imediat: maximul se află în rădăcină. La min-heap relația e inversă și rădăcina conține minimul.

Două precizări care despart nota mare de nota mică:

• complet înseamnă că toate nivelurile sunt pline, cu excepția eventual a ultimului, care e completat de la stânga la dreapta — de aceea heap-ul se memorează eficient într-un vector, fără pointeri: pentru nodul de pe poziția i (indexare de la 1), fiii sunt pe pozițiile 2i și 2i+1, iar părintele pe poziția [i/2];
• heap-ul NU este arbore binar de căutare: între fiul stâng și fiul drept nu există nicio relație de ordine — se compară doar părintele cu fiii. Confuzia heap ↔ ABC e capcana standard de grilă.

Operații și costuri:

• inserare: pui elementul pe prima poziție liberă și îl urci cât timp e mai mare decât părintele — O(log n);
• extragerea maximului: scoți rădăcina, muți ultimul element în vârf și îl cobori spre fiul mai mare — O(log n).

Aplicații: HeapSort (sortare în O(n log n)) și cozile de priorități, unde nu contează ordinea sosirii, ci prioritatea.

Test — 6 întrebări ca la examen