Structuri de date avansate

Studiul structurilor de date dinamice și al modalităților de reprezentare și prelucrare a acestora.

Pointeri și alocare dinamică

Un pointer este o variabilă care memorează adresa altei variabile, nu valoarea ei. În C++, `int p;` declară un pointer către int, `&x` este adresa variabilei x, iar `p` (operatorul de dereferențiere) este valoarea de la adresa memorată în p. Confuzia care costă puncte: p este adresa, *p este valoarea — a le amesteca schimbă complet sensul unei atribuiri.

Memoria unui program are două zone cu comportament diferit:

• stiva de execuție — aici trăiesc variabilele locale; se eliberează automat la ieșirea din funcție;
• heap-ul (memoria liberă) — aici se face alocarea dinamică, la cerere, în timpul execuției: `p = new int;` sau `p = new int[n];` pentru un tablou a cărui dimensiune se află abia la rulare.

Ce se alocă cu `new` trebuie eliberat explicit cu `delete p;` respectiv `delete[] p;`. Neeliberarea produce scurgeri de memorie (memory leak): memoria rămâne ocupată deși nu mai e folosită. Alte două erori clasice: pointerul invalid (dangling) — folosirea unui pointer după ce zona lui a fost eliberată — și dereferențierea unui pointer nul (`NULL` sau `nullptr`), care oprește programul.

Alocarea dinamică este fundamentul tuturor structurilor din acest capitol: liste, stive, cozi și arbori cresc și scad în timpul execuției exact pentru că nodurile lor se creează cu new, pe măsură ce e nevoie.

Liste liniare înlănțuite

O listă simplu înlănțuită este o înșiruire de noduri alocate dinamic, fiecare nod conținând o informație utilă și un pointer către nodul următor. Primul nod se numește cap (prim), iar câmpul următor al ultimului nod este NULL — semnul de sfârșit.

Comparația cu vectorul, cerută frecvent:

• lista nu are dimensiune fixă și inserarea/ștergerea la o poziție cunoscută se face în O(1), doar prin mutarea a două legături, fără deplasarea celorlalte elemente;
• în schimb, lista nu are acces direct prin indice: pentru al k-lea element trebuie parcurse k noduri, deci accesul este O(n), iar căutarea binară este imposibilă.

Operațiile de bază și capcanele lor:

• inserarea la început: nodul nou arată spre vechiul cap, apoi capul devine nodul nou — în această ordine; invers, se pierde restul listei;
• ștergerea unui nod: legătura predecesorului se mută peste nodul șters, iar nodul se eliberează cu delete; ștergerea capului mută mai întâi capul pe al doilea nod;
• parcurgerea: un pointer de lucru pornește de la cap și avansează cu `p = p->urm` cât timp p nu e NULL.

Lista dublu înlănțuită adaugă fiecărui nod un pointer către predecesor, permițând parcurgerea în ambele sensuri și ștergerea unui nod fără căutarea predecesorului — cu prețul unei legături suplimentare de întreținut la fiecare operație. Lista circulară leagă ultimul nod înapoi la primul; la parcurgere, condiția de oprire nu mai este NULL, ci revenirea la nodul de start.

Stiva

Stiva (stack) este o structură de date de tip LIFO — Last In, First Out: ultimul element introdus este primul extras. Modelul intuitiv: un teanc de farfurii — pui și iei doar de deasupra.

Operațiile permise, singurele:

• push(x) — adaugă elementul x în vârful stivei;
• pop() — elimină elementul din vârf;
• top() — consultă elementul din vârf fără să-l elimine;
• testul de stivă vidă — obligatoriu înaintea oricărui pop sau top, altfel apare eroarea de subdepășire (underflow).

Esența restricției: nu ai acces decât la vârf. Nu poți citi sau scoate un element din mijlocul stivei fără să scoți mai întâi tot ce e deasupra lui. Grilele exploatează exact această regulă: dacă în stivă s-au introdus, în ordine, 1, 2, 3, extragerea le produce în ordinea 3, 2, 1.

Implementare: pe vector (cu o variabilă care reține indicele vârfului) sau pe listă înlănțuită (push și pop la începutul listei, ambele O(1)).

Aplicații de reținut pentru examen: inversarea unei secvențe, verificarea parantezărilor corecte (fiecare paranteză deschisă se pune pe stivă, fiecare închisă trebuie să se potrivească cu vârful), evaluarea expresiilor și, esențial, stiva de execuție a apelurilor recursive — motivul pentru care recursivitatea și stiva sunt două fețe ale aceluiași mecanism.

Coada

Coada (queue) este structura de tip FIFO — First In, First Out: primul element introdus este primul extras, exact ca la o coadă la casă. Este imaginea în oglindă a stivei, iar perechea LIFO/FIFO este verificată aproape garantat în teste.

Operațiile specifice:

• adăugarea se face întotdeauna la sfârșitul cozii;
• extragerea se face întotdeauna de la începutul cozii;
• consultarea primului element și testul de coadă vidă completează setul.

Dacă în coadă intră, în ordine, 1, 2, 3, ele ies în ordinea 1, 2, 3 — ordinea se păstrează, spre deosebire de stivă, care o inversează.

Implementarea pe vector are o subtilitate: extragerile de la început lasă spațiu nefolosit în față. Soluția standard este coada circulară, în care indicii de început și sfârșit înaintează modulo dimensiunea vectorului, reciclând pozițiile eliberate. Implementarea pe listă înlănțuită ține doi pointeri, către primul și către ultimul nod, ambele operații fiind O(1).

Aplicații: parcurgerea în lățime (BFS) a grafurilor și arborilor — coada este chiar inima algoritmului —, planificarea proceselor în sistemele de operare, tampoanele (buffer) de tipărire, simulările de fire de așteptare. Regula de alegere între cele două structuri: ai nevoie de revenire în ordine inversă → stivă; ai nevoie de servire în ordinea sosirii → coadă.

Arbori binari

Un arbore binar este o structură ierarhică formată din noduri, în care fiecare nod are cel mult doi descendenți: un fiu stâng și un fiu drept. Nodul din vârf, fără părinte, este rădăcina; nodurile fără niciun fiu sunt frunze. Înălțimea arborelui este numărul de niveluri (sau, în alte convenții, numărul de muchii pe cel mai lung drum de la rădăcină la o frunză — la examen se lucrează cu convenția din enunț).

Cele trei parcurgeri în adâncime, definite recursiv prin poziția rădăcinii:

• 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ă.

Trucul de memorare: prefixul spune unde e Rădăcina — pre = prima, in = la mijloc, post = ultima. Subarborele stâng vine mereu înaintea celui drept.

Arborele binar de căutare (ABC) adaugă regula de ordine: în subarborele stâng al oricărui nod stau doar valori mai mici, în cel drept doar valori mai mari. Consecința de aur, cerută la examen: parcurgerea în inordine a unui ABC produce valorile în ordine crescătoare. Căutarea unei valori coboară din rădăcină alegând stânga sau dreapta după comparație — în un arbore echilibrat, O(log n) pași; degenerat în „listă” (inserții în ordine crescătoare), O(n).

Reprezentarea în memorie folosește noduri alocate dinamic cu doi pointeri (stâng, drept), iar parcurgerile se implementează natural recursiv.

Grafuri: reprezentare și parcurgere

Un graf neorientat G = (V, E) este format dintr-o mulțime de vârfuri (noduri) și o mulțime de muchii — perechi neordonate de vârfuri. La graful orientat, legăturile sunt arce — perechi ordonate, cu sens. Gradul unui vârf este numărul de muchii incidente lui; suma gradelor tuturor vârfurilor este dublul numărului de muchii — identitate cerută des în grile.

Reprezentări:

• matricea de adiacență — matrice n×n cu a[i][j] = 1 dacă există muchie între i și j; pentru grafuri neorientate este simetrică; ocupă O(n²) memorie, dar răspunde în O(1) la întrebarea „există muchia (i, j)?”;
• listele de adiacență — pentru fiecare vârf, lista vecinilor săi; ocupă O(n + m) și e preferată la grafuri rare.

Un lanț (drum) este o succesiune de vârfuri legate prin muchii; un ciclu este un lanț care se întoarce în vârful de plecare. Un graf este conex dacă între oricare două vârfuri există un lanț; porțiunile conexe maximale se numesc componente conexe. Un arbore este exact un graf conex fără cicluri, cu n - 1 muchii.

Parcurgeri:

• BFS (în lățime) — folosește o coadă: vizitează întâi toate vârfurile la distanță 1 de start, apoi cele la distanța 2 etc.; găsește drumurile cu număr minim de muchii;
• DFS (în adâncime) — folosește stiva (sau recursivitatea): înaintează pe o ramură cât de departe se poate, apoi revine.

Ambele vizitează fiecare vârf o singură dată, cu ajutorul unui vector de marcaje vizitat; fără el, parcurgerea ciclează la nesfârșit pe grafuri cu cicluri. Asocierea de reținut: BFS ↔ coadă, DFS ↔ stivă — inversarea lor este greșeala standard.

Test — 6 întrebări ca la examen