MyCodeSchool

Pasul 1 din 5

C++

Pasul 1 din 5 · Ce construiești

  • C++
  • Avansat
  • 15 minute

Liste înlănțuite în C++

Construiești o listă de numere care crește oricât, fără o dimensiune fixată dinainte. Adaugi pătratele de la 1 la 5, ștergi câteva, mai adaugi unul și afișezi lista.

lista.cpp, în consolă
1 4 9 16 25 
4 16 36 

Prima parte din trei despre structuri de date. Un vector ține elementele unul lângă altul; o listă înlănțuită le ține oriunde în memorie, legate prin pointeri, ca vagoanele unui tren.

Pasul 2 din 5

Rulează-l linie cu linie

Două noduri, adăugate la începutul listei, apoi afișate. În panou, „→ nodul 2” înseamnă un pointer spre nodul cu valoarea 2, iar lista arată lanțul întreg.

lista.cpp
#include <iostream>using namespace std;struct Nod {    int val;    Nod *urm;};int main() {    Nod *cap = nullptr;    for (int x = 2; x >= 1; x--) {        Nod *n = new Nod;        n->val = x;        n->urm = cap;        cap = n;    }    Nod *p = cap;    while (p != nullptr) {        cout << p->val << ' ';        p = p->urm;    }    return 0;}

Variabile

Ce apare pe ecran


      

  1. Linia 10. cap arată spre primul nod. Lista e goală, deci cap e nullptr: nu arată nicăieri.
  2. Linia 11. Prima tură, cu x = 2.
  3. Linia 12. new Nod rezervă memorie pentru un nod și îi dă adresa lui n.
  4. Linia 13. n->val e câmpul val al nodului spre care arată n. Primește 2.
  5. Linia 14. Nodul nou arată spre vechiul cap, adică spre nimic.
  6. Linia 15. Nodul nou devine capul listei.
  7. Linia 11. A doua tură, cu x = 1. Variabila n din tura trecută a dispărut, dar nodul ei rămâne în memorie, legat de cap.
  8. Linia 12. Încă un nod nou.
  9. Linia 13. Valoarea lui: 1.
  10. Linia 14. Nodul nou arată spre vechiul cap, nodul 2. Așa se leagă lanțul.
  11. Linia 15. Nodul 1 devine cap. Lista e 1 → 2.
  12. Linia 11. x = 0, condiția e falsă, bucla se termină.
  13. Linia 17. p pornește de la cap. cap rămâne pe loc, ca să nu pierdem începutul.
  14. Linia 18. p arată spre un nod, deci intră în buclă.
  15. Linia 19. Se afișează valoarea nodului curent.
  16. Linia 20. p sare la nodul următor.
  17. Linia 18. Mai e un nod.
  18. Linia 19. Se afișează 2.
  19. Linia 20. Nodul 2 era ultimul: urm e nullptr.
  20. Linia 18. p e nullptr, bucla se oprește.
  21. Linia 22. main se încheie.
  22. Gata. Adăugarea la început inversează ordinea: am adăugat 2, apoi 1, iar lista se citește 1, 2.

Prezice ieșirea

Schimbi bucla de la linia 11 în for (int x = 1; x <= 3; x++). Ce afișează programul?

Răspuns: „3 2 1”.

Fiecare nod nou intră în fața celorlalți. Ultimul adăugat, 3, ajunge primul. Pentru ordinea de adăugare îți trebuie inserarea la sfârșit, din cardul 2.

Pasul 3 din 5

Operațiile pe listă

Fragmentele stau în main, sub structura de mai jos. new Nod{x, cap} creează un nod și îi completează ambele câmpuri dintr-odată.

struct Nod
struct Nod {    int val;    Nod *urm;};

Noduri și pointeri

nod.cpp
Nod *a = new Nod;a->val = 7;a->urm = nullptr;Nod *b = new Nod;b->val = 9;b->urm = a;cout << b->val << ' ';cout << b->urm->val;delete a;delete b;

Ce apare pe ecran

9 7

a și b sunt pointeri: țin adrese, nu noduri. -> trece de la adresă la câmp. b->urm->val se citește „valoarea nodului de după b”. Fiecare new are nevoie, la final, de un delete.

Adăugare la sfârșit

sfarsit.cpp
Nod *cap = nullptr;Nod *ultim = nullptr;for (int x = 1; x <= 4; x++) {    Nod *n = new Nod;    n->val = x * 10;    n->urm = nullptr;    if (cap == nullptr)        cap = n;    else        ultim->urm = n;    ultim = n;}for (Nod *p = cap; p; p = p->urm)    cout << p->val << ' ';

Ce apare pe ecran

10 20 30 40 

Ca să nu parcurgi toată lista la fiecare adăugare, ții minte și ultimul nod. Primul nod e caz special: devine și cap, și ultim.

Parcurgere și căutare

cauta.cpp
int v[5] = {4, 8, 15, 16, 23};Nod *cap = nullptr;for (int i = 4; i >= 0; i--)    cap = new Nod{v[i], cap};int nr = 0, gasit = 0;for (Nod *p = cap; p; p = p->urm) {    nr++;    if (p->val == 15)        gasit = nr;}cout << nr << ' ' << gasit;

Ce apare pe ecran

5 3

Lista nu are indici: ca să ajungi la al treilea nod, treci prin primele două. Bucla numără nodurile și ține minte poziția lui 15. În for, condiția p înseamnă p != nullptr.

Ștergerea unui nod

sterge.cpp
Nod *cap = nullptr;for (int x = 4; x >= 1; x--)    cap = new Nod{x, cap};Nod *p = cap;while (p->urm->val != 3)    p = p->urm;Nod *de_sters = p->urm;p->urm = de_sters->urm;delete de_sters;for (p = cap; p; p = p->urm)    cout << p->val << ' ';

Ce apare pe ecran

1 2 4 

Ca să scoți nodul 3, te oprești pe nodul dinaintea lui. Îl legi direct de nodul de după, apoi eliberezi memoria cu delete. Ordinea contează: dacă ștergi întâi, pierzi adresa nodului următor.

Capcană: treci de capătul listei

Cauți 8 într-o listă care nu-l conține. După ultimul nod, p devine nullptr, iar p->val citește de la o adresă invalidă:

segfault.cpp
#include <iostream>using namespace std;struct Nod {    int val;    Nod *urm;};int main() {    Nod *cap = new Nod{5, nullptr};    Nod *p = cap;    while (p->val != 8)        p = p->urm;    cout << "găsit";    return 0;}

„găsit” nu apare. Programul se oprește brusc, cu codul de ieșire 139, iar în terminalul Linux scrie Segmentation fault.

Repară verificând întâi pointerul: while (p != nullptr && p->val != 8). && se oprește la prima parte falsă, deci p->val nu mai e citit.

Capcană: parcurgi cu cap

Parcurgerea mută chiar cap. După prima afișare, cap e nullptr, iar a doua afișare nu mai găsește nimic:

pierdut.cpp
#include <iostream>using namespace std;struct Nod {    int val;    Nod *urm;};int main() {    Nod *cap = nullptr;    for (int x = 3; x >= 1; x--)        cap = new Nod{x, cap};    while (cap != nullptr) {        cout << cap->val << ' ';        cap = cap->urm;    }    cout << "| ";    while (cap != nullptr) {        cout << cap->val << ' ';        cap = cap->urm;    }    return 0;}

Ce apare pe ecran

1 2 3 | 

Repară parcurgând cu un pointer separat, Nod *p = cap;. Nodurile nu s-au șters, dar nu mai ai cum să ajungi la ele.

Pasul 4 din 5

Verifică-te

Cinci întrebări noi. După fiecare răspuns vezi imediat de ce e așa.

1 din 5 · Prezice ieșirea

Ce afișează programul?

inceput.cpp
#include <iostream>using namespace std;struct Nod {    int val;    Nod *urm;};int main() {    Nod *cap = nullptr;    for (int x = 1; x <= 3; x++)        cap = new Nod{x * 2, cap};    Nod *p = cap;    while (p) {        cout << p->val;        p = p->urm;    }    return 0;}

Răspuns: „642”.

Valorile sunt 2, 4, 6, fiecare adăugată în fața listei. Ultima adăugată, 6, e prima.

2 din 5 · Alege varianta

Ce valoare are câmpul urm al ultimului nod?

Răspuns: nullptr.

nullptr marchează sfârșitul listei, iar parcurgerile se opresc la el. O listă în care ultimul nod arată spre primul se numește circulară și are nevoie de altă condiție de oprire.

3 din 5 · Alege varianta

Vrei al 1000-lea element. De ce e mai lent într-o listă înlănțuită decât într-un vector?

Răspuns: trebuie să treci prin nodurile dinainte.

Un vector calculează direct adresa elementului. O listă știe doar unde e primul nod; fiecare alt nod se află din cel de dinainte. Lista câștigă în schimb la inserări și ștergeri.

4 din 5 · Alege varianta

Ce face p = p->urm;?

Răspuns: mută p pe nodul următor.

Se schimbă doar pointerul p. Lista rămâne neatinsă. E pasul de bază din orice parcurgere.

5 din 5 · Prezice ieșirea

Ce afișează programul?

primul.cpp
#include <iostream>using namespace std;struct Nod {    int val;    Nod *urm;};int main() {    Nod *c = new Nod{3, nullptr};    c = new Nod{2, c};    c = new Nod{1, c};    Nod *vechi = c;    c = c->urm;    delete vechi;    for (Nod *p = c; p; p = p->urm)        cout << p->val;    return 0;}

Răspuns: „23”.

Lista e 1, 2, 3. Capul trece pe al doilea nod, iar primul e șters cu delete. Pointerul vechi a păstrat adresa lui, ca să poată fi eliberat.

Pasul 5 din 5

Ce ai învățat

Programul complet

Trei funcții: adauga la sfârșit, sterge după valoare, cu cazurile cap și ultim, și afiseaza. La final, bucla din main eliberează fiecare nod.

lista.cpp
#include <iostream>using namespace std;struct Nod {    int val;    Nod *urm;};Nod *cap = nullptr;Nod *ultim = nullptr;void adauga(int x) {    Nod *n = new Nod{x, nullptr};    if (cap == nullptr)        cap = n;    else        ultim->urm = n;    ultim = n;}void sterge(int x) {    Nod *ant = nullptr, *p = cap;    while (p && p->val != x) {        ant = p;        p = p->urm;    }    if (p == nullptr)        return;    if (ant == nullptr)        cap = p->urm;    else        ant->urm = p->urm;    if (p == ultim)        ultim = ant;    delete p;}void afiseaza() {    Nod *p = cap;    while (p) {        cout << p->val << ' ';        p = p->urm;    }    cout << '\n';}int main() {    for (int x = 1; x <= 5; x++)        adauga(x * x);    afiseaza();    sterge(1);    sterge(9);    sterge(25);    adauga(36);    afiseaza();    while (cap) {        Nod *p = cap;        cap = cap->urm;        delete p;    }    return 0;}

Ce apare pe ecran

1 4 9 16 25 
4 16 36 

Continuă cu