Tipuri abstracte de date (TAD – multimi, dictionare) si implementare

Tipurile abstracte de date (TAD) reprezintă o modalitate de a modela datele prin specificarea operațiilor permise asupra lor, fără a dezvălui detaliile interne de implementare. În cadrul acestei lecții, ne concentrăm pe două TAD-uri fundamentale: mulțimile (set) și dicționarele (map). O mulțime este o colecție de elemente distincte, fără o ordine particulară, care suportă operații precum adăugarea, ștergerea, căutarea, reunirea, intersecția și diferența.

În contextul Bacalaureatului, se pune accent pe implementarea eficientă a mulțimilor folosind vectori de frecvență (pentru mulțimi de numere mici), tabele hash sau arbori binari de căutare. De exemplu, pentru a verifica dacă un element aparține mulțimii, un vector de frecvență oferă complexitate O(1) la căutare, dar este limitat la un interval cunoscut de valori. Pe de altă parte, un dicționar asociază chei unice cu valori, implementat uzual prin tabele hash, care oferă operații de inserare, ștergere și căutare în medie O(1).

În implementări C/C++ la bac, se folosesc fie vectori paraleli (unul pentru chei și unul pentru valori) cu căutare liniară, fie funcții hash simple. O aplicație clasică este contorizarea frecvenței cuvintelor dintr-un text. Este important ca elevii să înțeleagă diferența dintre specificația abstractă (ce face TAD-ul) și implementarea concretă (cum face).

La bacalaureat, se testează atât cunoașterea operațiilor și proprietăților, cât și capacitatea de a scrie algoritmi de implementare, de exemplu pentru reuniunea a două mulțimi stocate ca vectori sortați (algoritm de interclasare). De asemenea, se discută compromisul între memorie și timp: un vector de frecvență consumă multă memorie dacă domeniul valorilor este mare, dar oferă operații rapide, în timp ce un arbore binar echilibrat consumă mai puțină memorie dar are complexitate logaritmică.

Exemple

• Exemplul 1: Implementarea unei mulțimi de numere întregi mici (0..1000) folosind un vector de frecvență. Se declară un array de 1001 elemente, inițializat cu 0. Adăugarea unui element x: frecv[x] = 1; ștergerea: frecv[x] = 0; căutarea: if(frecv[x]==1). Această metodă este eficientă când domeniul valorilor este cunoscut și restrâns.
• Exemplul 2: Implementarea unui dicționar cu asociere nume-notă (string -> int) folosind o tabelă hash simplă. Cheia (numele) este convertită la un hash (suma codurilor ASCII modulo dimensiunea tabelei). Coliziunile se rezolvă prin înlănțuire (liste simplu înlănțuite). Operațiile: inserare (se calculează hash, se adaugă în lista corespunzătoare), căutare (parcurge lista după hash, compară cheile). Este util pentru a înțelege principiul hashing-ului.
• Exemplul 3: Reuniunea a două mulțimi stocate în vectori sortați. Se consideră A și B, fiecare sortat. Algoritmul: i=0, j=0; cât timp i<n și j<m, se compară A[i] și B[j]; se adaugă elementul mai mic în mulțimea rezultat, incrementând indicele corespunzător; dacă sunt egale, se adaugă o singură dată și se incrementează ambii indici. La final, se adaugă elementele rămase. Complexitate O(n+m).

Concepte cheie: TAD (Tip Abstract de Date) – separarea specificației de implementare, Mulțime – colecție de elemente distincte, operații: adăugare, ștergere, căutare, reuniune, intersecție, diferență, Dicționar – asociere cheie–valoare, operații: inserare, căutare după cheie, ștergere, Implementare cu vector de frecvență – O(1) la căutare, memorie mare pentru domenii largi, Implementare cu tabelă hash – O(1) mediu, gestionarea coliziunilor (înlănțuire), Reuniunea a două mulțimi sortate prin interclasare – O(n+m)