Structuri de Date Liniare Implementate Dinamic – Liste Circulare Dublu Înlanțuite 9
1. Obiectivele lecției:
- Să înțeleagă conceptul de listă circulară dublu înlănțuită.
- Să învețe cum să implementeze această structură dinamic.
- Să implementeze operații comune: adăugare, ștergere, parcurgere în ambele sensuri.
2. Ce este o listă circulară dublu înlănțuită?
- Definiție:
O listă circulară dublu înlănțuită este o structură de date în care:- Fiecare nod conține o valoare, un pointer către nodul următor și un pointer către nodul anterior.
- Primul nod este legat de ultimul nod, iar ultimul nod este legat de primul, creând o structură circulară.
- Caracteristici:
- Permite parcurgerea listei în ambele sensuri.
- Este circulară, astfel încât lista poate fi parcursă continuu fără punct final.
- Structura nodului:
struct Nod {
int valoare;
Nod* urmator; // Pointer către următorul nod
Nod* anterior; // Pointer către nodul anterior
};
3. Avantaje și dezavantaje
Avantaje | Dezavantaje |
Parcurgere bidirecțională continuă. | Gestionarea pointerilor este mai complexă. |
Eficientă pentru aplicații circulare (ex.: cozi). | Necesită mai multă memorie (doi pointeri/nod). |
Inserare și ștergere eficiente în orice poziție. | Poate apărea riscul de erori dacă pointerii nu sunt corect gestionați. |
4. Operații comune pe liste circulare dublu înlănțuite
1. Crearea unui nod
Nod* creeazaNod(int valoare) {
Nod* nod = new Nod();
nod->valoare = valoare;
nod->urmator = nullptr;
nod->anterior = nullptr;
return nod;
}
2. Adăugarea unui element
- Adăugare la început:
void adaugaInceput(Nod*& head, Nod*& tail, int valoare) {
Nod* nod = creeazaNod(valoare);
if (head == nullptr) {
head = tail = nod;
nod->urmator = nod->anterior = nod;
} else {
nod->urmator = head;
nod->anterior = tail;
head->anterior = nod;
tail->urmator = nod;
head = nod;
}
}
- Adăugare la sfârșit:
void adaugaSfarsit(Nod*& head, Nod*& tail, int valoare) {
Nod* nod = creeazaNod(valoare);
if (head == nullptr) {
head = tail = nod;
nod->urmator = nod->anterior = nod;
} else {
nod->anterior = tail;
nod->urmator = head;
tail->urmator = nod;
head->anterior = nod;
tail = nod;
}
}
3. Ștergerea unui element
- Ștergere de la început:
void stergeInceput(Nod*& head, Nod*& tail) {
if (head == nullptr) return;
if (head == tail) { // Lista are un singur nod
delete head;
head = tail = nullptr;
} else {
Nod* temp = head;
head = head->urmator;
head->anterior = tail;
tail->urmator = head;
delete temp;
}
}
- Ștergere de la sfârșit:
void stergeSfarsit(Nod*& head, Nod*& tail) {
if (tail == nullptr) return;
if (head == tail) { // Lista are un singur nod
delete tail;
head = tail = nullptr;
} else {
Nod* temp = tail;
tail = tail->anterior;
tail->urmator = head;
head->anterior = tail;
delete temp;
}
}
- Ștergerea unui nod cu o valoare specificată:
void stergeValoare(Nod*& head, Nod*& tail, int valoare) {
if (head == nullptr) return;
Nod* temp = head;
do {
if (temp->valoare == valoare) {
if (temp == head) {
stergeInceput(head, tail);
return;
} else if (temp == tail) {
stergeSfarsit(head, tail);
return;
} else {
temp->anterior->urmator = temp->urmator;
temp->urmator->anterior = temp->anterior;
delete temp;
return;
}
}
temp = temp->urmator;
} while (temp != head);
}
4. Parcurgerea listei
- Parcurgere de la început la sfârșit:
void parcurgeInainte(Nod* head) {
if (head == nullptr) return;
Nod* temp = head;
do {
cout << temp->valoare << ” „;
temp = temp->urmator;
} while (temp != head);
cout << endl;
}
- Parcurgere de la sfârșit la început:
void parcurgeInapoi(Nod* tail) {
if (tail == nullptr) return;
Nod* temp = tail;
do {
cout << temp->valoare << ” „;
temp = temp->anterior;
} while (temp != tail);
cout << endl;
}
5. Exemplu complet
#include <iostream>
using namespace std;
struct Nod {
int valoare;
Nod* urmator;
Nod* anterior;
};
Nod* creeazaNod(int valoare) {
Nod* nod = new Nod();
nod->valoare = valoare;
nod->urmator = nullptr;
nod->anterior = nullptr;
return nod;
}
void adaugaInceput(Nod*& head, Nod*& tail, int valoare) {
Nod* nod = creeazaNod(valoare);
if (head == nullptr) {
head = tail = nod;
nod->urmator = nod->anterior = nod;
} else {
nod->urmator = head;
nod->anterior = tail;
head->anterior = nod;
tail->urmator = nod;
head = nod;
}
}
void adaugaSfarsit(Nod*& head, Nod*& tail, int valoare) {
Nod* nod = creeazaNod(valoare);
if (head == nullptr) {
head = tail = nod;
nod->urmator = nod->anterior = nod;
} else {
nod->anterior = tail;
nod->urmator = head;
tail->urmator = nod;
head->anterior = nod;
tail = nod;
}
}
void parcurgeInainte(Nod* head) {
if (head == nullptr) return;
Nod* temp = head;
do {
cout << temp->valoare << ” „;
temp = temp->urmator;
} while (temp != head);
cout << endl;
}
void parcurgeInapoi(Nod* tail) {
if (tail == nullptr) return;
Nod* temp = tail;
do {
cout << temp->valoare << ” „;
temp = temp->anterior;
} while (temp != tail);
cout << endl;
}
int main() {
Nod* head = nullptr;
Nod* tail = nullptr;
adaugaInceput(head, tail, 10);
adaugaInceput(head, tail, 20);
adaugaSfarsit(head, tail, 30);
cout << „Parcurgere înainte: „;
parcurgeInainte(head);
cout << „Parcurgere înapoi: „;
parcurgeInapoi(tail);
return 0;
}
6. Activități practice pentru elevi
- Implementați o funcție care determină lungimea unei liste circulare dublu înlănțuite.
- Scrieți o funcție care inserează un nod după un alt nod specificat.
- Realizați o funcție care verifică dacă un element există în listă.
7. Scheme logice
- Adăugare:
- Creează nod -> Actualizează pointerii -> Asigură circularitatea listei.
- Ștergere:
- Verifică dacă lista este goală -> Găsește nodul de șters -> Actualizează pointerii -> Eliberează memoria.
8. Concluzie
- Listele circulare dublu înlănțuite sunt utile pentru aplicații care necesită parcurgere bidirecțională și acces circular.
- Implementarea lor necesită gestionarea atentă a pointerilor pentru a asigura integritatea listei.
- Practica este esențială pentru a stăpâni implementarea și utilizarea acestor liste.