Structuri de Date Liniare Implementate Dinamic – Liste Liniare Simplu Înlanțuite 6
1. Obiectivele lecției:
- Să înțeleagă conceptul de listă liniară simplu înlănțuită.
- Să învețe cum să implementeze o listă simplu înlănțuită dinamic.
- Să utilizeze operații comune: adăugare, ștergere, parcurgere.
2. Ce este o listă liniară simplu înlănțuită?
- Definiție:
O listă simplu înlănțuită este o structură de date compusă din noduri, unde fiecare nod conține:- O valoare (informație utilă).
- Un pointer către următorul nod din listă.
- Caracteristici:
- Alocarea memoriei este dinamică.
- Dimensiunea listei poate varia în timpul execuției.
- Primul nod este identificat de un pointer numit head.
- Ultimul nod indică sfârșitul listei printr-un pointer nullptr.
3. Avantaje și dezavantaje
| Avantaje | Dezavantaje |
| Dimensiunea listei este dinamică. | Accesul la un element necesită parcurgere secvențială. |
| Inserarea și ștergerea elementelor sunt eficiente. | Consumul de memorie suplimentară pentru pointere. |
| Nu este necesară alocarea unui bloc mare de memorie. | Mai dificil de implementat comparativ cu vectorii. |
4. Structura unui nod
- Structura nodului:
struct Nod {
int valoare;
Nod* urmator;
};
- Explicație:
- valoare: Stochează informația utilă.
- urmator: Pointer către următorul nod din listă.
5. Operații comune pe liste simplu înlănțuite
1. Crearea unui nod
Nod* creeazaNod(int valoare) {
Nod* nod = new Nod();
nod->valoare = valoare;
nod->urmator = nullptr;
return nod;
}
2. Adăugarea unui element
- Adăugare la început:
void adaugaInceput(Nod*& head, int valoare) {
Nod* nod = creeazaNod(valoare);
nod->urmator = head;
head = nod;
}
- Adăugare la sfârșit:
void adaugaSfarsit(Nod*& head, int valoare) {
Nod* nod = creeazaNod(valoare);
if (head == nullptr) {
head = nod;
} else {
Nod* temp = head;
while (temp->urmator != nullptr) {
temp = temp->urmator;
}
temp->urmator = nod;
}
}
3. Ștergerea unui element
- Ștergere de la început:
void stergeInceput(Nod*& head) {
if (head == nullptr) return;
Nod* temp = head;
head = head->urmator;
delete temp;
}
- Ștergere de la sfârșit:
void stergeSfarsit(Nod*& head) {
if (head == nullptr) return;
if (head->urmator == nullptr) {
delete head;
head = nullptr;
return;
}
Nod* temp = head;
while (temp->urmator->urmator != nullptr) {
temp = temp->urmator;
}
delete temp->urmator;
temp->urmator = nullptr;
}
- Ștergerea unui nod cu o anumită valoare:
void stergeValoare(Nod*& head, int valoare) {
if (head == nullptr) return;
if (head->valoare == valoare) {
Nod* temp = head;
head = head->urmator;
delete temp;
return;
}
Nod* temp = head;
while (temp->urmator != nullptr && temp->urmator->valoare != valoare) {
temp = temp->urmator;
}
if (temp->urmator != nullptr) {
Nod* deSters = temp->urmator;
temp->urmator = temp->urmator->urmator;
delete deSters;
}
}
4. Parcurgerea listei
void parcurgeLista(Nod* head) {
Nod* temp = head;
while (temp != nullptr) {
cout << temp->valoare << ” „;
temp = temp->urmator;
}
cout << endl;
}
6. Exemplu complet
#include <iostream>
using namespace std;
struct Nod {
int valoare;
Nod* urmator;
};
Nod* creeazaNod(int valoare) {
Nod* nod = new Nod();
nod->valoare = valoare;
nod->urmator = nullptr;
return nod;
}
void adaugaInceput(Nod*& head, int valoare) {
Nod* nod = creeazaNod(valoare);
nod->urmator = head;
head = nod;
}
void adaugaSfarsit(Nod*& head, int valoare) {
Nod* nod = creeazaNod(valoare);
if (head == nullptr) {
head = nod;
} else {
Nod* temp = head;
while (temp->urmator != nullptr) {
temp = temp->urmator;
}
temp->urmator = nod;
}
}
void stergeInceput(Nod*& head) {
if (head == nullptr) return;
Nod* temp = head;
head = head->urmator;
delete temp;
}
void stergeSfarsit(Nod*& head) {
if (head == nullptr) return;
if (head->urmator == nullptr) {
delete head;
head = nullptr;
return;
}
Nod* temp = head;
while (temp->urmator->urmator != nullptr) {
temp = temp->urmator;
}
delete temp->urmator;
temp->urmator = nullptr;
}
void parcurgeLista(Nod* head) {
Nod* temp = head;
while (temp != nullptr) {
cout << temp->valoare << ” „;
temp = temp->urmator;
}
cout << endl;
}
int main() {
Nod* lista = nullptr;
adaugaInceput(lista, 10);
adaugaInceput(lista, 20);
adaugaSfarsit(lista, 30);
parcurgeLista(lista);
stergeInceput(lista);
parcurgeLista(lista);
stergeSfarsit(lista);
parcurgeLista(lista);
return 0;
}
7. Activități practice pentru elevi
- Implementați o funcție care determină lungimea unei liste simplu înlănțuite.
- Scrieți o funcție care inserează un nod după un alt nod cu o valoare specificată.
- Realizați o funcție care inversează o listă simplu înlănțuită.
8. Scheme logice
- Adăugare:
- Creează nod -> Leagă nodul la început/sfârșit -> Actualizează pointerul head.
- Ștergere:
- Verifică dacă lista este goală -> Găsește nodul de șters -> Actualizează legăturile -> Eliberează memoria.
9. Concluzie
- Listele simplu înlănțuite sunt structuri flexibile și eficiente pentru gestionarea datelor.
- Implementarea necesită gestionarea atentă a pointerilor pentru a evita scurgerile de memorie.
- Practica este esențială pentru a înțelege pe deplin cum funcționează aceste structuri.