Structuri de date avansate
Prezentarea structurilor de date dinamice complexe și a operațiilor asociate acestora.
Bacalaureat
Alocarea dinamică și lista simplu înlănțuită
Spre deosebire de tablou, unde dimensiunea este fixată la declarare, structurile dinamice cresc și scad în timpul execuției: memoria se cere sistemului la nevoie (în C++ cu new) și se eliberează explicit (cu delete). Legătura dintre elemente se ține prin pointeri — variabile care memorează adrese.
O listă simplu înlănțuită este o succesiune de noduri; fiecare nod conține informația utilă și un pointer către nodul următor (urm). Lista este identificată prin pointerul către primul nod (prim), iar ultimul nod are urm = NULL — marcajul de sfârșit.
Operațiile de bază și costul lor — comparația cu tabloul este întrebare de teorie:
- inserarea la început: nodul nou primește urm = prim, apoi prim = nodul nou; timp O(1);
- inserarea după un nod p cunoscut: nou->urm = p->urm, apoi p->urm = nou — ordinea celor două atribuiri este critică; inversarea lor pierde restul listei, cea mai clasică greșeală de cod;
- ștergerea unui nod: predecesorul își mută legătura peste nodul șters, iar memoria nodului se eliberează; ștergerea primului nod mută pur și simplu prim;
- accesul la al k-lea element: necesită parcurgere de la început, O(n) — aici tabloul câștigă cu O(1).
Avantajul listei: inserări și ștergeri fără deplasarea elementelor, dimensiune limitată doar de memoria disponibilă. Dezavantaje: fără acces direct prin indice, memorie suplimentară pentru pointeri.
Capcană de parcurgere: condiția corectă este cât timp p != NULL; testarea lui p->urm în loc de p omite ultimul nod sau, mai rău, dereferențiază NULL.
Liste dublu înlănțuite și liste circulare
În lista dublu înlănțuită, fiecare nod are două legături: către succesor (urm) și către predecesor (prec). Primul nod are prec = NULL, ultimul are urm = NULL, iar lista se poate identifica prin pointeri către ambele capete.
Ce câștigăm față de lista simplă — argumentele cerute la comparație:
- parcurgere în ambele sensuri;
- ștergerea unui nod p cunoscut în O(1), fără căutarea predecesorului: p->prec->urm = p->urm și p->urm->prec = p->prec (cu tratarea atentă a capetelor, unde unul dintre vecini nu există);
- inserarea înaintea unui nod dat devine directă.
Prețul: memorie suplimentară pentru al doilea pointer și mai multe legături de actualizat la fiecare operație — la inserarea între două noduri se modifică patru legături, nu două. Uitarea uneia dintre cele patru (tipic: prec al nodului din dreapta) lasă lista coerentă la parcurgerea înainte, dar ruptă la parcurgerea înapoi — bug greu de văzut, cerut ca atare în probleme de verificare.
Lista circulară nu are NULL la capăt: ultimul nod se leagă de primul (iar în varianta dublu înlănțuită, primul se leagă înapoi de ultimul). Nu mai există „sfârșit”, deci parcurgerea se oprește când s-a revenit la nodul de plecare — condiția de oprire p != start după primul pas, nu p != NULL; folosirea condiției de la lista liniară duce la buclă infinită. Listele circulare modelează natural probleme de tip numărătoare în cerc (probleme de tip Josephus) și cozi circulare.
De reținut ca principiu general: la orice operație pe liste se tratează separat cazurile de margine — listă vidă, un singur nod, operare la capete. Majoritatea punctelor pierdute la subiectele cu liste vin din aceste cazuri, nu din cazul general.
Stiva — LIFO — și aplicațiile ei
Stiva este o structură de date cu acces restricționat: toate operațiile au loc la un singur capăt, numit vârful stivei. Disciplina este LIFO — Last In, First Out: ultimul element introdus este primul extras, ca la un teanc de farfurii.
Operațiile standard: push (adăugare în vârf), pop (extragere din vârf), top (consultarea vârfului fără extragere), test de stivă vidă — extragerea dintr-o stivă vidă este eroare și trebuie mereu precedată de test.
Implementare dinamică: stiva este o listă simplu înlănțuită în care atât inserarea, cât și ștergerea se fac la început — ambele O(1). Implementarea pe vector reține vârful printr-un indice.
Aplicațiile care se cer la examen:
- verificarea parantezărilor corecte: paranteza deschisă se pune pe stivă, cea închisă trebuie să se potrivească cu vârful; la final stiva trebuie să fie vidă;
- evaluarea expresiilor și conversia în forma poloneză postfixată;
- mecanismul apelurilor recursive: la fiecare apel, parametrii, variabilele locale și adresa de revenire se depun pe stiva de execuție a programului — de aceea recursivitatea fără caz de bază produce stack overflow, iar orice algoritm recursiv poate fi rescris iterativ cu o stivă explicită;
- parcurgerea DFS a grafurilor și inversarea ordinii unor elemente.
Exercițiul-tip de simulare: se dă o secvență de operații push/pop și se cere conținutul final sau ordinea extragerilor — se rezolvă disciplinat, desenând stiva pas cu pas. Greșeala tipică: tratarea extragerilor în ordinea introducerii (adică FIFO), confundând stiva cu coada.
Coada — FIFO — și coada circulară
Coada este structura complementară stivei: elementele se adaugă la un capăt (sfârșitul cozii) și se extrag de la celălalt (începutul cozii). Disciplina este FIFO — First In, First Out: primul venit este primul servit, ca la un ghișeu.
Implementarea dinamică folosește o listă simplu înlănțuită cu doi pointeri: prim (de unde se extrage) și ultim (unde se adaugă) — ambele operații devin O(1). Cazul de margine care se punctează: la extragerea ultimului element rămas, trebuie actualizat și ultim la NULL, nu doar prim; la adăugarea în coadă vidă se actualizează amândoi.
Pe vector, implementarea naivă (extragere de pe poziția 0 cu deplasarea celorlalte) este O(n) per operație. Soluția clasică este coada circulară: doi indici, prim și ultim, care avansează modulo dimensiunea vectorului — după ultima poziție se revine pe poziția 0. Astfel spațiul eliberat prin extrageri este refolosit, iar ambele operații rămân O(1). Subtilitatea cerută la teorie: cu n poziții, plin și gol arată la fel dacă se folosesc doar indicii, deci se ține fie un contor de elemente, fie se sacrifică o poziție.
Aplicații de examen:
- parcurgerea BFS a grafurilor — coada reține vârfurile în ordinea descoperirii;
- generarea în ordine a unor șiruri de numere (din fiecare element extras se produc succesorii, adăugați la coadă);
- simulări de tip fir de așteptare și planificarea proceselor.
Perechea de memorat, țintă frecventă de grilă: stiva — LIFO — DFS; coada — FIFO — BFS. Orice încrucișare a acestor asocieri este greșită.
Tabele de dispersie și cozi de priorități
Tabela de dispersie (hash table) stochează elementele astfel încât căutarea, inserarea și ștergerea să dureze, în medie, O(1). Ideea: o funcție de dispersie h transformă cheia într-un indice al unui tablou — tipic h(k) = k mod M, unde M este dimensiunea tabelei. Elementul cu cheia k se depune direct în „compartimentul” h(k).
Problema inevitabilă: coliziunile — două chei diferite cu același indice (h(k1) = h(k2)). Coliziunile nu pot fi eliminate complet când mulțimea cheilor posibile depășește numărul compartimentelor, ci doar gestionate:
- înlănțuire (chaining): fiecare compartiment ține o listă înlănțuită a elementelor care se dispersează acolo;
- adresare deschisă: la coliziune se caută, după o regulă fixă (de exemplu probare liniară — următoarea poziție liberă), un alt compartiment.
Calitatea funcției de dispersie decide totul: o funcție care distribuie uniform ține listele scurte; în cazul cel mai defavorabil (toate cheile în același compartiment) operațiile degradează la O(n). De aceea afirmația „hash-ul este întotdeauna O(1)” este falsă — corect este „O(1) în medie”. Alt sacrificiu, cerut la comparații: tabela de dispersie nu păstrează elementele în ordine, deci nu poate răspunde eficient la interogări de tip minim, maxim sau interval — acolo rămân utile ABC-ul sau vectorul sortat.
Coada de priorități este structura din care se extrage mereu elementul cu prioritatea maximă (sau minimă), nu cel mai vechi. Implementarea eficientă este heap-ul: inserare și extragere în O(log n), consultarea optimului în O(1). Comparația care se cere: cu vector nesortat, inserarea e O(1) dar extragerea O(n); cu vector sortat, invers; heap-ul le echilibrează pe amândouă. Aplicații: algoritmul lui Dijkstra, HeapSort, planificarea sarcinilor după urgență. Capcană: coada de priorități NU este FIFO — un element sosit ultimul, dar cu prioritate mare, iese primul.
De reținut
- listă simplu înlănțuită
- structură dinamică formată din noduri alocate la cerere, fiecare conținând informația utilă și un pointer către nodul următor; ultimul nod are legătura NULL
- listă dublu înlănțuită
- listă în care fiecare nod reține legături atât către succesor, cât și către predecesor, permițând parcurgerea în ambele sensuri și ștergerea unui nod cunoscut în O(1)
- listă circulară
- listă în care ultimul nod se leagă de primul, fără marcaj NULL de sfârșit; parcurgerea se oprește la revenirea în nodul de plecare
- stivă
- structură de date cu disciplina LIFO (Last In, First Out): inserarea și extragerea se fac la același capăt, numit vârful stivei, prin operațiile push și pop
- coadă
- structură de date cu disciplina FIFO (First In, First Out): elementele se adaugă la un capăt și se extrag de la celălalt
- coadă circulară
- implementare a cozii pe vector în care indicii de început și de sfârșit avansează modulo dimensiunea vectorului, refolosind pozițiile eliberate
- funcție de dispersie
- funcție care transformă cheia unui element în indicele compartimentului din tabela de dispersie, tipic prin restul împărțirii la dimensiunea tabelei
- coliziune
- situația în care două chei diferite primesc același indice de la funcția de dispersie; se rezolvă prin înlănțuire sau prin adresare deschisă
- coadă de priorități
- structură din care se extrage întotdeauna elementul cu prioritatea maximă (sau minimă); implementată eficient cu heap, cu inserare și extragere în O(log n)
- NULL
- valoare convențională a unui pointer care nu indică nicio adresă validă; marchează sfârșitul listelor liniare și absența legăturilor
Greșeli frecvente
Greșit: La inserarea unui nod după nodul p se scrie întâi p->urm = nou și abia apoi nou->urm = p->urm
Corect: Ordinea corectă este inversă: întâi nou->urm = p->urm (nodul nou preia continuarea listei), apoi p->urm = nou; altfel legătura către restul listei se pierde definitiv
Greșit: Parcurgerea unei liste circulare cu condiția p != NULL
Corect: Într-o listă circulară nu există NULL; parcurgerea pornește din nodul de start și se oprește când s-a revenit la el, altfel bucla devine infinită
Greșit: Se extrag elementele dintr-o stivă în ordinea în care au fost introduse
Corect: Stiva este LIFO: ultimul element introdus iese primul; ordinea introducerii este respectată la extragere doar de coadă (FIFO)
Greșit: La extragerea ultimului element dintr-o coadă dinamică se actualizează doar pointerul prim
Corect: Când coada rămâne vidă trebuie pus pe NULL și pointerul ultim; altfel el rămâne o adresă invalidă, iar următoarea adăugare corupe structura
Greșit: Se afirmă că într-o tabelă de dispersie căutarea este garantat O(1)
Corect: O(1) este costul mediu, condiționat de o funcție de dispersie care distribuie uniform; în cazul defavorabil, cu multe coliziuni în același compartiment, căutarea degradează la O(n)
Test — 6 întrebări ca la examen
1. Într-o listă simplu înlănțuită nevidă, identificată prin pointerul prim, inserarea unui nod nou la începutul listei se face prin:
- prim = nou; nou->urm = prim;
- nou->urm = prim; prim = nou;
- prim->urm = nou; nou->urm = NULL;
- nou->urm = prim->urm; prim = nou;
Vezi răspunsul
nou->urm = prim; prim = nou;. Nodul nou trebuie mai întâi să preia legătura către lista existentă și abia apoi să devină primul. Prima variantă — distractorul clasic — face atribuirile în ordine inversă: după prim = nou, vechea adresă a listei e pierdută și nou->urm = prim leagă nodul de el însuși.
2. Avantajul esențial al listei dublu înlănțuite față de cea simplu înlănțuită este:
- accesul direct la al k-lea element în O(1)
- ștergerea unui nod cunoscut fără parcurgerea listei pentru aflarea predecesorului
- consumul mai mic de memorie pe nod
- faptul că nu mai necesită pointer către primul nod
Vezi răspunsul
ștergerea unui nod cunoscut fără parcurgerea listei pentru aflarea predecesorului. Legătura prec dă acces imediat la predecesor, deci un nod cunoscut se poate scoate în O(1). Accesul prin indice rămâne O(n) la orice listă înlănțuită — distractorul tentant, pentru că acela este avantajul tabloului; memoria pe nod este mai mare, nu mai mică, din cauza celui de-al doilea pointer.
3. Într-o stivă inițial vidă se execută: push(3), push(7), pop(), push(5), push(9), pop(), pop(). Elementul rămas în stivă este:
- 3
- 5
- 7
- 9
Vezi răspunsul
3. Simulare: după push(3), push(7) stiva este 3,7; pop() scoate 7; push(5), push(9) dau 3,5,9; pop() scoate 9, pop() scoate 5 — rămâne 3. Cine răspunde 9 sau 5 a extras după disciplina FIFO a cozii, nu LIFO a stivei.
4. Structura de date adecvată pentru verificarea corectitudinii parantezelor dintr-o expresie este:
- coada
- stiva
- tabela de dispersie
- lista circulară
Vezi răspunsul
stiva. Fiecare paranteză închisă trebuie să se potrivească cu cea mai recentă paranteză deschisă încă neînchisă — exact vârful stivei; la final stiva trebuie să fie vidă. Coada e distractorul uzual, dar ea ar potrivi paranteza închisă cu cea mai veche deschidere, ceea ce validează greșit expresii de tip )( imbricate.
5. Într-o tabelă de dispersie cu M = 10 compartimente și funcția h(k) = k mod 10, se inserează cheile 23, 42, 13, 7, 33. Care chei intră în coliziune?
- 23 și 42
- 42 și 7
- 23, 13 și 33
- nicio pereche, cheile fiind distincte
Vezi răspunsul
23, 13 și 33. h(23) = h(13) = h(33) = 3, deci toate trei cad în compartimentul 3 — coliziune triplă; 42 merge la 2, iar 7 la 7. Ultima variantă surprinde confuzia esențială: coliziunea privește egalitatea valorilor funcției de dispersie, nu egalitatea cheilor — chei distincte pot avea același indice.
6. Într-o coadă de priorități de tip max, implementată cu heap, sosesc pe rând elementele cu prioritățile 4, 9, 2, 9, 5. Se fac apoi două extrageri. Prioritățile extrase sunt, în ordine:
- 4, 9 — în ordinea sosirii
- 9, 9 — de fiecare dată maximul curent
- 2, 4 — de fiecare dată minimul curent
- 5, 9 — ultimul sosit, apoi maximul
Vezi răspunsul
9, 9 — de fiecare dată maximul curent. Coada de priorități max extrage mereu elementul cu prioritatea cea mai mare din structură: prima extragere dă un 9, a doua dă celălalt 9 — dublurile sunt permise. Prima variantă aplică disciplina FIFO a cozii obișnuite, exact confuzia pe care o testează de regulă grila.