Structuri de Date Dinamice

Breviar teoretic și practic: liste liniare simplu înlănțuite

Informatică - Clasa a 11-a

1. Introducere Teoretică

De ce avem nevoie de liste alocate dinamic?

În programarea clasică (statică), folosim vectori pentru a stoca mulțimi de date. Totuși, vectorii au o limitare majoră: dimensiunea fixă (trebuie să știm de la început câte elemente vom avea, ex: int v[100]). Dacă folosim mai puține, risipim memorie; dacă avem nevoie de mai multe, programul nu le poate gestiona.

Listele liniare alocate dinamic rezolvă această problemă. Ele nu ocupă o zonă contiguă de memorie. Fiecare element (nod) este creat exact atunci când avem nevoie de el și este șters când nu mai este necesar.

Alocarea dinamică înseamnă rezervarea memoriei în timpul execuției (run-time), într-o zonă numită Heap. În C/C++, folosim malloc pentru alocare și free pentru eliberare.

struct nod {
    int info;    // Informația utilă
    nod *urm;    // Adresa următorului nod
};

// Variabila globală care ține minte începutul listei
nod *prim = NULL;

2. Adăugarea la Început

Această operație inserează un nou nod în fața listei existente. Este o operație foarte rapidă, cu complexitate O(1).

Pas cu Pas:
  1. Alocăm memorie pentru noul nod folosind malloc.
  2. Scriem informația utilă în nod (nou->info).
  3. Facem legătura: noul nod va arăta spre vechiul început al listei (nou->urm = prim).
  4. Actualizăm capul listei: prim devine noul nod.
NOU
10
→
↬
PRIM (Vechi)
5
→
→
8
NULL
void adaugareInceput() {
    nod *nou = (nod*)malloc(sizeof(nod));
    cout << "Valoare: ";
    cin >> nou->info;
    
    nou->urm = prim; // Legătura cu restul listei
    prim = nou;      // Actualizare cap de listă
}

3. Adăugarea la Sfârșit

Dacă nu avem un pointer special pentru ultimul element, trebuie să parcurgem toată lista pentru a ajunge la capăt.

Pas cu Pas:
  1. Alocăm nodul și setăm nou->urm = NULL (va fi ultimul).
  2. Cazul listei vide: Dacă prim == NULL, noul nod devine primul (prim = nou).
  3. Cazul general: Parcurgem lista cu un pointer temporar p până la ultimul nod (while p->urm != NULL).
  4. Legăm ultimul nod găsit de noul nod: p->urm = nou.
PRIM
5
→
→
p (Ultimul Curent)
8
→
↬
NOU
12
NULL
void adaugareSfarsit() {
    nod *nou = (nod*)malloc(sizeof(nod));
    cin >> nou->info;
    nou->urm = NULL; 

    if (prim == NULL) {
        prim = nou;
    } else {
        nod *p = prim;
        while (p->urm != NULL) {
            p = p->urm; // Avansăm până la ultimul
        }
        p->urm = nou; // Facem legătura
    }
}

4. Ștergerea unui Element

Căutăm o valoare și o eliminăm, refăcând legăturile pentru a nu rupe lista.

Pas cu Pas (Ștergere din interior):
  1. Folosim un pointer temp pentru a ne opri înaintea nodului de șters.
  2. Verificăm dacă nodul următor (temp->urm) conține valoarea căutată.
  3. Salvăm adresa nodului de șters în pointerul auxiliar p.
  4. Sărim peste nodul de șters: temp->urm = p->urm.
  5. Eliberăm memoria ocupată de p folosind free(p).
temp
5
→
→
p (De Șters)
8
→
→
12
NULL
// Fragment pentru ștergere din interior
nod *temp = prim;
while (temp->urm != NULL && temp->urm->info != valoare) {
    temp = temp->urm;
}
if (temp->urm != NULL) {
    nod *p = temp->urm;      // Identificăm victima
    temp->urm = p->urm;      // Sărim peste ea
    free(p);                 // Eliberăm memoria
}

Stiva (Stack) - Principiul LIFO

LIFO = Last In, First Out (Ultimul venit, Primul plecat). Gândește-te la un teanc de farfurii: pui o farfurie doar deasupra și iei o farfurie tot de deasupra.

  • Accesul se face doar la un singur capăt (Vârf / Top).
  • În implementarea cu liste, "Vârful" este pointerul prim.

Operația PUSH (Adăugare)

Este identică cu funcția adaugareInceput. Noul element vine "peste" celelalte.

NOU (Vârf)
30
↓
→
20
↓
→
10
NULL
void push(int valoare) {
    nod *nou = (nod*)malloc(sizeof(nod));
    nou->info = valoare;
    nou->urm = prim; // Noul nod indică spre vechiul vârf
    prim = nou;      // Vârful devine noul nod
}

Operația POP (Scoatere)

Este similară cu ștergerea primului element. Scoatem elementul din vârf (prim).

Pas cu Pas:
  1. Verificăm dacă stiva e goală (Underflow).
  2. Salvăm vârful actual într-un pointer temporar temp.
  3. Mutăm vârful la următorul element: prim = prim->urm.
  4. Eliberăm memoria: free(temp).
void pop() {
    if (prim == NULL) return;
    
    nod *temp = prim;
    prim = prim->urm; // Coborâm în stivă
    free(temp);
}

Coada (Queue) - Principiul FIFO

FIFO = First In, First Out (Primul venit, Primul servit). Exact ca la o coadă la magazin.

Pentru eficiență, avem nevoie de doi pointeri:

  • prim: începutul cozii (de unde scoatem).
  • ultim: sfârșitul cozii (unde adăugăm), ca să nu parcurgem lista la fiecare inserare.

Operația ENQUEUE (Adăugare)

Adăugăm mereu după pointerul ultim.

PRIM
1
→
→
ULTIM (Vechi)
2
→
→
NOU (Ultim)
3
NULL
void enqueue(int val) {
    nod *nou = (nod*)malloc(sizeof(nod));
    nou->info = val;
    nou->urm = NULL;

    if (prim == NULL) {
        // Coada goală: noul nod e și primul și ultimul
        prim = nou;
        ultim = nou;
    } else {
        ultim->urm = nou; // Legăm fostul ultim de noul nod
        ultim = nou;      // Actualizăm pointerul ultim
    }
}

Operația DEQUEUE (Scoatere)

Scoatem mereu de la prim. Dacă lista se golește, trebuie să setăm și ultim la NULL.

void dequeue() {
    if (prim == NULL) return;

    nod *temp = prim;
    prim = prim->urm;

    if (prim == NULL) {
        ultim = NULL; // Resetăm ultimul dacă coada devine goală
    }
    free(temp);
}

✎ Testează-ți cunoștințele

Completează răspunsurile corecte sau instrucțiunile lipsă din cod.

1. Alocare dinamică

Ce funcție din C folosim pentru a rezerva memorie în Heap?

Indiciu: Începe cu 'm' și este prescurtarea de la Memory Allocation.

2. Eliberare memorie

Ce funcție folosim pentru a șterge un nod și a evita Memory Leaks?

Indiciu: Traducerea în engleză pentru "liber".

3. Accesare membru

Dacă avem un pointer nod *p, cum accesăm câmpul info?

int x =
Indiciu: Pentru pointeri folosim operatorul săgeată.

4. Stivă (LIFO)

Ce înseamnă acronimul LIFO?

Indiciu: Gândește-te la farfuriile spălate.

5. Cod: Adăugare la început

Completează linia lipsă pentru a lega noul nod de restul listei:

nou->urm = ;
prim = nou;
Indiciu: Noul nod trebuie să arate spre fostul cap al listei.

6. Coadă (Structură)

Câți pointeri folosim de obicei pentru a gestiona eficient o coadă?

Indiciu: Unul pentru început și unul pentru sfârșit.

7. Terminarea listei

Care este valoarea pointerului urm pentru ultimul nod dintr-o listă?

Indiciu: Se scrie cu majuscule în C++, dar aici acceptăm și litere mici.

8. Cod: Parcurgere

Cum treci la următorul nod într-o buclă while?

temp = ;
Indiciu: Atribuim lui temp adresa nodului următor.

9. Cod: Adăugare la Sfârșit

După ce am parcurs lista și p a ajuns pe ultimul nod, cum îl legăm de nou?

while (p->urm != NULL) p = p->urm;
p->urm = ;
Indiciu: Ultimul nod trebuie să arate acum spre nodul nou creat.

10. Cod: Ștergere din interior

Am găsit nodul de șters (p) care se află după temp. Cum refacem legătura pentru a sări peste p?

nod *p = temp->urm;
temp->urm = ;
free(p);
Indiciu: Legătura trebuie să sară peste p și să ajungă la următorul nod după p.

11. Cod: Coadă (Enqueue)

După ce am adăugat un element la finalul cozii, trebuie să actualizăm pointerul ultim.

ultim->urm = nou;
ultim = ;
Indiciu: Cine este acum noul "ultim" element al cozii?

12. Cod: Stivă (Pop)

Când scoatem un element din stivă, cum mutăm pointerul prim la următorul element?

nod *temp = prim;
prim = ;
free(temp);
Indiciu: Noul vârf este cel care era sub vârful actual.

Gestionarea Dinamică a Datelor – Aplicații Practice

Această temă este structurată pe 3 niveluri de dificultate. Alegeți nivelul potrivit împreună cu profesorul.

Nivel 1: Consolidare

Calcul Sumă și Numărare Noduri

Cerință: Pornind de la codul prezentat în lecție, implementează următoarele două funcții noi:

  1. int sumaElemente(): Parcurge lista, calculează suma tuturor numerelor din noduri și o returnează.
  2. int numarNoduri(): Numără câte noduri există în listă și afișează rezultatul.

Exemplu: Pentru 5 -> 10 -> 2, suma este 17 și numărul de noduri este 3.

Nivel 2: Logică Algoritmică

Căutare Poziție

Cerință: Scrie o funcție numită cautarePozitie(int valoare) care caută o valoare citită de la tastatură în listă.

  • Dacă o găsește, afișează: "Valoarea X se află pe poziția Y".
  • Dacă nu o găsește, afișează: "Valoarea X nu există în listă".

Indiciu: Folosește o variabilă contor care crește pe măsură ce avansezi cu pointerul temp.

Nivel 3: Avansat / Creativ

Mini-Proiect "Playlist Muzical"

Cerință: Implementează o funcționalitate de "Play Queue" folosind o Coadă (FIFO).

  1. Modifică structura nod pentru a reține: id_melodie (int) și rating (int, 1-5).
  2. Implementează un meniu cu opțiunile:
    • Adaugă melodie: Citește ID și Rating, adaugă la final (Enqueue).
    • Redă melodie: Afișează și elimină prima melodie din coadă (Dequeue).