SISergiu Ilincameditații informatică
Meniu

clasa a XI-a · Structuri de date · lecția 18

Pointeri, alocare dinamică și liste simplu înlănțuite

60 minintensiv informaticăintensiv

Înainte de lecția asta: X.12 Structuri de date neomogene: struct (înregistrări), XI.2 Subprograme (2): parametri prin referință și subprograme cu tablouri

Ce vei ști după lecție

  • Înțelegi ce este un pointer: o variabilă care memorează o adresă.
  • Aloci și eliberezi memorie dinamic cu new și delete.
  • Construiești o listă simplu înlănțuită: adăugare la început / la sfârșit, parcurgere, ștergere, inserare.

Lecția are și o fișă de lucru, de rezolvat după ce o citești. Mergi la fișă ↓

Clasa a XI-aLecția 18 din 21 · mai sunt 3Urmează: XI.19 · Grafuri cu costuri: Dijkstra, Roy-Floyd, arbori parțiali de cost minim (Prim, Kruskal)Vezi toate lecțiile
Cuprins

Fișiere PDF și de lucru

1. De ce avem nevoie de pointeri

Până acum, memoria programului a fost alcătuită din variabile cu nume (x, v[100]). Uneori nu știi dinainte câte date vor veni: un vector v[100] e prea mic sau prea mare. Soluția: ceri memorie în timpul rulării, exact cât ai nevoie. Pentru a ajunge la această memorie, folosești adrese, iar o variabilă care păstrează o adresă se numește pointer.

2. Pointeri: adresă și valoare

Fiecare variabilă stă la o adresă în memorie, ca o casă la o stradă. Un pointer este un „bilet cu adresa casei”.

Pointer

Scriere Se citește Exemplu
int *p; p este pointer spre int
&x adresa lui x p = &x;
*p valoarea de la adresa din p cout << *p; → 5
*p = 10; schimbă valoarea de la adresă acum x == 10
NULL (sau nullptr) „nu arată nicăieri” p = NULL;

Prima utilizare practică: o funcție care modifică argumentele (cum făcea & în lecția XI.2).

#include <iostream>
using namespace std;

void schimba(int *a, int *b)
{
    int t = *a;       // valoarea de la adresa a
    *a = *b;
    *b = t;
}

int main()
{
    int x, y;
    cin >> x >> y;
    schimba(&x, &y);  // dăm adresele lui x și y
    cout << x << ' ' << y;
    return 0;
}

De ce așa?

De ce &x la apel? Funcția are nevoie de adresa variabilelor, ca să poată modifica originalele. Dacă am transmite x prin valoare, schimba ar lucra pe o copie și x, y ar rămâne neschimbate (exact ca la parametri prin valoare, lecția XI.2).

3. Alocare dinamică: new și delete

int *q = new int;       // o variabilă nouă (fără nume), accesibilă doar prin q
*q = 7;
delete q;               // o eliberăm când nu mai e necesară

int *v = new int[n];    // un vector de n elemente, n aflat la rulare
delete[] v;             // eliberare pentru vectori
#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int *v = new int[n];                // exact n elemente
    int suma = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        suma += v[i];
    }
    cout << suma;
    delete[] v;                         // dăm memoria înapoi
    return 0;
}

De ce așa?

De ce delete[]? Memoria cerută cu new nu se eliberează singură cât timp programul rulează; dacă uiți delete, memoria „se scurge” (memory leak). La programele mici nu se vede, la servere care rulează luni de zile devine problemă gravă. De ce v[i] merge pe un pointer? v[i] înseamnă „elementul de la adresa v + i”; vectorii și pointerii sunt strâns legați.

4. Lista simplu înlănțuită

O listă este o înșiruire de noduri. Fiecare nod conține informația și adresa nodului următor. Ultimul nod are urm = NULL. Ținem minte doar adresa primului nod (prim); de acolo ajungem la toate celelalte.

Lista

struct nod
{
    int info;       // valoarea
    nod *urm;       // adresa nodului următor
};
nod *prim = NULL;   // lista goală

Pe un exemplu cu adrese inventate:

Nod Adresa info urm
#1 100 3 120
#2 120 5 140
#3 140 8 NULL

prim conține 100. Dacă p = prim, atunci p->info este 3 (prescurtare pentru (*p).info), iar p = p->urm mută p pe nodul 2.

Adăugare la început

Adăugare la început

void adaugaInceput(nod *&prim, int x)
{
    nod *p = new nod;
    p->info = x;
    p->urm = prim;      // nodul nou arată spre vechiul prim
    prim = p;           // nodul nou devine primul
}

Adăugare la sfârșit și parcurgere

Pentru adăugarea la sfârșit ținem și un pointer ultim.

#include <iostream>
using namespace std;

struct nod
{
    int info;
    nod *urm;
};

void adaugaInceput(nod *&prim, int x)
{
    nod *p = new nod;
    p->info = x;
    p->urm = prim;
    prim = p;
}

void adaugaSfarsit(nod *&prim, nod *&ultim, int x)
{
    nod *p = new nod;
    p->info = x;
    p->urm = NULL;
    if (prim == NULL) prim = ultim = p;      // prima valoare
    else { ultim->urm = p; ultim = p; }
}

void afisare(nod *prim)
{
    for (nod *p = prim; p != NULL; p = p->urm)
        cout << p->info << ' ';
    cout << '\n';
}

void elibereaza(nod *&prim)
{
    while (prim != NULL)
    {
        nod *q = prim;
        prim = prim->urm;
        delete q;
    }
}

int main()
{
    int n, x;
    cin >> n;
    nod *L1 = NULL, *ultim = NULL, *L2 = NULL;
    for (int i = 1; i <= n; i++)
    {
        cin >> x;
        adaugaSfarsit(L1, ultim, x);
        adaugaInceput(L2, x);
    }
    afisare(L1);
    afisare(L2);
    elibereaza(L1);
    elibereaza(L2);
    return 0;
}

De ce așa?

De ce nod *&prim (pointer prin referință)? Funcția trebuie să poată schimba pointerul prim din main (când lista era goală, prim devine nodul nou). Fără &, funcția ar modifica o copie a pointerului și lista din main ar rămâne goală. De ce p = p->urm în for? Este „pasul” pe listă: p trece pe nodul următor; când ajunge la NULL, am terminat. De ce elibereaza salvează q înainte de prim = prim->urm? După delete q nodul dispare; trebuie să știm unde era următorul.

De știut

Prima listă (L1) păstrează ordinea citirii (adăugare la sfârșit), a doua (L2) o inversează (adăugare la început): același cod pentru stivă, deoarece o stivă implementată cu listă adaugă și scoate la început.

5. Inserare și ștergere: ordinea contează

Inserarea unui nod după p

Inserare

nod *q = new nod;
q->info = x;
q->urm = p->urm;    // 1) nodul nou arată spre restul listei
p->urm = q;         // 2) p arată spre nodul nou

Pe adresele din tabel, inserăm 7 după nodul 5 (p = 120, q alocat la 160):

Pas Instrucțiune Efect
1 q->info = 7 nodul 160: info = 7
2 q->urm = p->urm nodul 160: urm = 140 (continuă cu 8)
3 p->urm = q nodul 120: urm = 160

Atenție — greșeli frecvente

Dacă faci întâi p->urm = q, pierzi adresa 140 (nodul 8): nu mai există nicio variabilă care să o rețină, iar restul listei devine inaccesibil.

Ștergerea nodului de după p

Ștergere

nod *q = p->urm;    // nodul de șters
p->urm = q->urm;    // îl ocolim
delete q;           // eliberăm memoria

Ștergerea primei apariții a valorii x

Trei cazuri: lista goală, ștergi chiar primul nod, ștergi din interior.

#include <iostream>
using namespace std;

struct nod { int info; nod *urm; };

void adaugaSfarsit(nod *&prim, nod *&ultim, int x)
{
    nod *p = new nod;
    p->info = x; p->urm = NULL;
    if (prim == NULL) prim = ultim = p;
    else { ultim->urm = p; ultim = p; }
}

void stergeValoare(nod *&prim, int x)
{
    if (prim == NULL) return;
    if (prim->info == x)                    // cazul 1: primul nod
    {
        nod *q = prim;
        prim = prim->urm;
        delete q;
        return;
    }
    for (nod *p = prim; p->urm != NULL; p = p->urm)
        if (p->urm->info == x)              // cazul 2: nodul de după p
        {
            nod *q = p->urm;
            p->urm = q->urm;
            delete q;
            return;
        }
}

int main()
{
    int n, x, v;
    cin >> n;
    nod *prim = NULL, *ultim = NULL;
    for (int i = 1; i <= n; i++) { cin >> x; adaugaSfarsit(prim, ultim, x); }
    cin >> v;
    stergeValoare(prim, v);
    for (nod *p = prim; p != NULL; p = p->urm) cout << p->info << ' ';
    return 0;
}

De ce așa?

De ce primul nod e caz aparte? Pentru a șterge un nod trebuie să modifici urm al predecesorului; primul nod nu are predecesor, deci modifici prim. De ce p->urm != NULL în buclă? Ne oprim la penultimul nod ca să putem privi p->urm->info fără să accesăm NULL.

Inserare după valoarea y

#include <iostream>
using namespace std;

struct nod { int info; nod *urm; };

int main()
{
    int n, x, y, v;
    cin >> n;
    nod *prim = NULL, *ultim = NULL;
    for (int i = 1; i <= n; i++)
    {
        cin >> x;
        nod *p = new nod;
        p->info = x; p->urm = NULL;
        if (prim == NULL) prim = ultim = p;
        else { ultim->urm = p; ultim = p; }
    }
    cin >> y >> v;                          // inserăm v după prima apariție a lui y
    for (nod *p = prim; p != NULL; p = p->urm)
        if (p->info == y)
        {
            nod *q = new nod;
            q->info = v;
            q->urm = p->urm;
            p->urm = q;
            break;
        }
    for (nod *p = prim; p != NULL; p = p->urm) cout << p->info << ' ';
    return 0;
}

6. Inversarea listei

Inversare

Trei pointeri: anterior (inițial NULL), curent (pornește de la prim), urmator. La fiecare pas: reținem următorul, întoarcem legătura curentă, avansăm.

Iterația curent urmator curent->urm devine anterior după pas
1 1 2 NULL 1
2 2 3 1 2
3 3 4 2 3
4 4 NULL 3 4

La final prim = anterior (nodul 4).

#include <iostream>
using namespace std;

struct nod { int info; nod *urm; };

int main()
{
    int n, x;
    cin >> n;
    nod *prim = NULL, *ultim = NULL;
    for (int i = 1; i <= n; i++)
    {
        cin >> x;
        nod *p = new nod;
        p->info = x; p->urm = NULL;
        if (prim == NULL) prim = ultim = p;
        else { ultim->urm = p; ultim = p; }
    }
    nod *anterior = NULL, *curent = prim;
    while (curent != NULL)
    {
        nod *urmator = curent->urm;     // 1) reținem restul
        curent->urm = anterior;         // 2) întoarcem legătura
        anterior = curent;              // 3) avansăm
        curent = urmator;
    }
    prim = anterior;
    for (nod *p = prim; p != NULL; p = p->urm) cout << p->info << ' ';
    return 0;
}

De ce așa?

De ce reținem urmator înainte să schimbăm curent->urm? După schimbare, legătura spre restul listei dispare; fără urmator am pierde restul (aceeași idee ca la inserare).

7. Vector sau listă?

Operație Vector Listă
acces la elementul k O(1) O(k) (parcurgi de la început)
inserare / ștergere în mijloc, având pointerul O(n) (deplasări) O(1)
adăugare la sfârșit O(1) O(1) cu pointer ultim
memorie fixă, declarată dinainte exact cât e nevoie, plus câte un pointer pe nod
căutare O(n) O(n)

8. Greșeli frecvente

Greșeala Efect Corect
uiți NULL la ultimul nod parcurgerea nu se oprește p->urm = NULL la creare
p->urm = q înainte de q->urm = p->urm pierzi restul listei întâi q, apoi p
delete q înainte să salvezi q->urm folosești memorie eliberată salvezi întâi
funcție care schimbă prim fără *& lista din main nu se schimbă nod *&prim
acces p->info cu p == NULL blocare (segmentation fault) verifici p != NULL
uiți delete scurgere de memorie eliberezi ce ai alocat

9. La BAC

La BAC

Grilele cu liste (clasa a X-a / a XI-a) dau o listă cu valori și o secvență de instrucțiuni cu pointeri („p = prim->urm; p->urm = p->urm->urm;”) și întreabă ce se afișează sau ce valoare are un nod. Metoda sigură: desenează lista, notează numele pointerilor sub nodurile pe care arată și execută instrucțiunile una câte una, mutând săgețile.

10. Exersează pe hârtie

1. Desenează lista după operațiile: adaugaInceput 3, adaugaInceput 5, adaugaSfarsit 8, ștergerea primului nod. Ce valori conține?

2. Lista este 2 → 4 → 6 → 8. Ce se afișează după p = prim; p = p->urm; p->urm = p->urm->urm; urmată de parcurgere?

3. Care este valoarea lui p->info după p = prim->urm->urm; pe lista 7 → 1 → 9 → 4?

4. Scrie o funcție care numără nodurile cu informație pară.

5. Scrie o funcție care returnează adresa ultimului nod (sau NULL pentru lista goală).

6. Cum ștergi ultimul nod al unei liste? (Atenție la lista cu un singur nod.)

7. Scrie o funcție care inserează x într-o listă sortată crescător, păstrând ordinea.

8. (BAC) Pe lista 1 → 2 → 3 → 4 → 5 se execută q = prim; while (q->urm->urm != NULL) q = q->urm;. Pe ce nod arată q la final?

9. De ce nu poți accesa direct elementul k într-o listă ca într-un vector? Câți pași faci pentru elementul 100?

10. Dă un exemplu de problemă în care lista este mai bună decât vectorul și unul în care vectorul este mai bun.

11. Mai departe (pentru cine vrea mai mult)

Lista dublu înlănțuită. Fiecare nod are și pred (nodul anterior): poți merge în ambele sensuri și ștergi un nod fără să cauți predecesorul. STL are std::list gata făcută.

Lista circulară. Ultimul nod arată spre primul; folosită la „elevii în cerc” (Josephus) fără copiere.

Detectarea ciclului (Floyd, „broasca și iepurele”). Doi pointeri, unul avansează 1 pas, altul 2; dacă se întâlnesc, lista are ciclu.

Stiva și coada cu liste. Stiva: adaugi și scoți la început; coada: adaugi la sfârșit (ultim) și scoți de la început. Merge mai bine decât vectorul când nu știi câte elemente vor fi.

Pointeri inteligenți (C++ modern). unique_ptr și shared_ptr eliberează memoria automat; în programele reale se evită new/delete direct.

Rezumat

  • &x = adresa, *p = valoarea de la adresă, p->camp = câmpul nodului, NULL = fără adresă.
  • new aloci, delete eliberezi; nod *&prim când funcția trebuie să schimbe pointerul.
  • Lista: noduri {info, urm}, prim, uneori ultim; parcurgere: for (p = prim; p != NULL; p = p->urm).
  • La inserare: întâi q->urm = p->urm, apoi p->urm = q. La ștergere: salvezi, ocolești, delete.

Fișa de lucru

Ai citit lecția? Printează fișa sau deschide-o pe ecran și rezolvă exercițiile în ordine.

Fișă de lucru · 6 pagini · 120 min

Stivă, coadă și liste înlănțuite

  • Simulezi pe hârtie stive, cozi și liste înlănțuite, inclusiv secvențe de tip BAC cu pointeri.
  • Găsești greșelile clasice: vârful greșit, ordinea legăturilor la inserare, pointer transmis fără &.
  • Alegi structura potrivită (stivă, coadă, listă) pentru o problemă nouă și o implementezi.

Fișa acoperă și: XI.17

Te-ai blocat la un exercițiu?

Probleme de lucru

Începe cu acestea, în ordine. Problemele se deschid pe pbinfo.ro, unde trimiți soluția și primești punctajul.

  • fadaugarelalista#1168

    ușoară
  • fafisarelista#1169

    ușoară
  • fadaugareinaintelista#1170

    ușoară

Temă

Rezolvă-le singur și bifează ce ai terminat. Bifele rămân salvate în acest browser.

  • fstergeprimuldinlista#1171

    ușoară
  • flistanumarare#1172

    ușoară
  • flistastergere#1176

    ușoară
  • flistainserare#1179

    ușoară
  • fsortare#1476

    ușoară
  • flistaoglindire#3789

    ușoară

Pentru cei care vor mai mult

  • fadaugareinceputlldi#3743

    Listă dublu înlănțuită.

    ușoară

Grile din subiectele de BAC

Exerciții de tip grilă din variantele de Bacalaureat. Se rezolvă pe pbinfo.ro, care îți verifică imediat răspunsul.

Citește și exersează în plus

Te-ai blocat la lecția asta?

Scrie-mi ce nu iese și vedem împreună de unde se blochează.

Răspunsuri

Exersează pe hârtie

1. adaugaInceput 3 → 3; adaugaInceput 5 → 5, 3; adaugaSfarsit 8 → 5, 3, 8; ștergerea primului → 3, 8.

2. p = prim (nodul 2); p = p->urm (nodul 4); p->urm = p->urm->urm (4 arată acum spre 8, nodul 6 este ocolit). Se afișează 2 4 8.

3. prim->urm este nodul 1, prim->urm->urm este nodul 9: p->info = 9.

4. int nrPare(nod *prim) { int c = 0; for (nod *p = prim; p != NULL; p = p->urm) if (p->info % 2 == 0) c++; return c; }

5. nod *ultimNod(nod *prim) { if (prim == NULL) return NULL; nod *p = prim; while (p->urm != NULL) p = p->urm; return p; }

6. Dacă lista are un singur nod: delete prim; prim = NULL;. Altfel, cauți penultimul nod (p->urm->urm == NULL), faci delete p->urm; p->urm = NULL;.

7. Dacă lista e goală sau x <= prim->info, adaugi la început. Altfel avansezi p cât timp p->urm != NULL && p->urm->info < x, apoi inserezi după p.

8. Condiția q->urm->urm != NULL oprește bucla când după q mai este un singur nod. Pe lista cu 5 noduri, q ajunge pe nodul 4 (penultimul).

9. Nodurile nu sunt consecutive în memorie; ajungi la elementul k doar urmând legăturile, deci pentru al 100-lea faci 99 de pași (p = p->urm de 99 ori).

10. Lista e mai bună: o coadă de așteptare la care se adaugă și se elimină mereu la capete, număr necunoscut de elemente. Vectorul e mai bun: o listă de note la care accesezi des elementul k (acces direct, O(1)).