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
- De ce avem nevoie de pointeri
- Pointeri: adresă și valoare
- Alocare dinamică: new și delete
- Lista simplu înlănțuită
- Inserare și ștergere: ordinea contează
- Inversarea listei
- Vector sau listă?
- Greșeli frecvente
- La BAC
- Exersează pe hârtie
- Mai departe (pentru cine vrea mai mult)
- Rezumat
- Fișa de lucru
- Probleme de lucru
- Temă
- Pentru cei care vor mai mult
- Grile din subiectele de BAC
- Citește și exersează în plus
- Răspunsuri
Fișiere PDF și de lucru
- Lecția în PDF
versiunea de printat
- Fișa de lucru: Stivă, coadă și liste înlănțuite
6 pagini · 120 min
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”.
| 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.
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
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
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 nouPe 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
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
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ă.newaloci,deleteeliberezi;nod *&primcând funcția trebuie să schimbe pointerul.- Lista: noduri
{info, urm},prim, uneoriultim; parcurgere:for (p = prim; p != NULL; p = p->urm). - La inserare: întâi
q->urm = p->urm, apoip->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.
- ușoară
fadaugarelalista#1168
https://www.pbinfo.ro/probleme/1168/fadaugarelalista
- ușoară
fafisarelista#1169
https://www.pbinfo.ro/probleme/1169/fafisarelista
- ușoară
https://www.pbinfo.ro/probleme/1170/fadaugareinaintelista
Temă
Rezolvă-le singur și bifează ce ai terminat. Bifele rămân salvate în acest browser.
- ușoară
https://www.pbinfo.ro/probleme/1171/fstergeprimuldinlista
- ușoară
flistanumarare#1172
https://www.pbinfo.ro/probleme/1172/flistanumarare
- ușoară
flistastergere#1176
https://www.pbinfo.ro/probleme/1176/flistastergere
- ușoară
flistainserare#1179
https://www.pbinfo.ro/probleme/1179/flistainserare
- ușoară
fsortare#1476
https://www.pbinfo.ro/probleme/1476/fsortare
- ușoară
flistaoglindire#3789
https://www.pbinfo.ro/probleme/3789/flistaoglindire
Pentru cei care vor mai mult
- ușoară
fadaugareinceputlldi#3743
Listă dublu înlănțuită.
https://www.pbinfo.ro/probleme/3743/fadaugareinceputlldi
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.
- #71listă simplu înlănțuită: ce rămâne după o secvență de instrucțiuni cu pointeri
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=71
- #75câmpul info al nodurilor: efectul unei secvențe pe listă
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=75
- #92listă cu numere întregi: ce afișează o parcurgere
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=92
- #114listă circulară: ce înseamnă parcurgerea
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=114
- #166valori date în ordine: ce se afișează după ștergere / inserare
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=166
- #187listă cu cel puțin 4 noduri: efectul operațiilor asupra legăturilor
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=187
- #196câmpul urm: ce se afișează la parcurgere
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=196
- #287listă dublu înlănțuită: câmpurile st și dr
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=287
Citește și exersează în plus
- Pointeri. Operații cu pointeri · pbinfo.ro
https://www.pbinfo.ro/articole/7659/pointeri-operatii-cu-pointeri
- Mecanismul alocării dinamice · pbinfo.ro
https://www.pbinfo.ro/articole/7662/mecanismul-alocarii-dinamice
- Liste liniare simplu înlănțuite alocate dinamic · pbinfo.ro
https://www.pbinfo.ro/articole/19576/liste-liniare-simplu-inlantuite-alocate-dinamic
- VisuAlgo — Linked List · visualgo.net
inserări și ștergeri pe liste, animate pas cu pas (engleză)
https://visualgo.net/en/list
- learncpp.com — Pointers · learncpp.com
pointeri explicați de la zero, cu imagini (engleză)
https://www.learncpp.com/cpp-tutorial/introduction-to-pointers/
- cppreference — std::list · en.cppreference.com
lista dublu înlănțuită din STL, gata făcută (engleză)
https://en.cppreference.com/w/cpp/container/list
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)).