Structuri de Date Liniare Implementate Dinamic – Liste Circulare Simplu Înlanțuite 8
1. Obiectivele lecției:
- Să înțeleagă conceptul de listă circulară simplu înlănțuită.
- Să învețe cum să implementeze o astfel de listă dinamic.
- Să implementeze operații comune: adăugare, ștergere, parcurgere.
2. Ce este o listă circulară simplu înlănțuită?
- Definiție:
O listă circulară simplu înlănțuită este o structură de date în care:- Fiecare nod conține o valoare și un pointer către următorul nod.
- Ultimul nod din listă indică înapoi către primul nod, creând astfel o structură circulară.
- Caracteristici:
- Lista nu are început și sfârșit clar definite.
- Se poate parcurge în mod continuu.
- Primul nod este gestionat printr-un pointer numit head.
3. Avantaje și dezavantaje
| Avantaje | Dezavantaje |
| Permite parcurgerea continuă a listei. | Mai dificil de implementat decât listele simple. |
| Eficientă pentru aplicații circulare (ex.: bucle). | Gestionarea pointerilor poate fi complicată. |
| Inserarea și ștergerea nodurilor sunt rapide. | Este necesară atenție pentru a menține lista circulară. |
4. Structura unui nod
struct Nod {
int valoare; // Informația stocată în nod
Nod* urmator; // Pointer către următorul nod
};
5. Operații comune pe liste circulare 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);
if (head == nullptr) {
nod->urmator = nod;
head = nod;
} else {
Nod* temp = head;
while (temp->urmator != head) {
temp = temp->urmator;
}
nod->urmator = head;
temp->urmator = nod;
head = nod;
}
}
- Adăugare la sfârșit:
void adaugaSfarsit(Nod*& head, int valoare) {
Nod* nod = creeazaNod(valoare);
if (head == nullptr) {
nod->urmator = nod;
head = nod;
} else {
Nod* temp = head;
while (temp->urmator != head) {
temp = temp->urmator;
}
temp->urmator = nod;
nod->urmator = head;
}
}
3. Ștergerea unui element
- Ștergere de la început:
void stergeInceput(Nod*& head) {
if (head == nullptr) return;
if (head->urmator == head) { // Lista are un singur nod
delete head;
head = nullptr;
return;
}
Nod* temp = head;
Nod* ultim = head;
while (ultim->urmator != head) {
ultim = ultim->urmator;
}
head = head->urmator;
ultim->urmator = head;
delete temp;
}
- Ștergere de la sfârșit:
void stergeSfarsit(Nod*& head) {
if (head == nullptr) return;
if (head->urmator == head) { // Lista are un singur nod
delete head;
head = nullptr;
return;
}
Nod* temp = head;
while (temp->urmator->urmator != head) {
temp = temp->urmator;
}
delete temp->urmator;
temp->urmator = head;
}
- Ștergerea unui nod cu o valoare specificată:
void stergeValoare(Nod*& head, int valoare) {
if (head == nullptr) return;
if (head->valoare == valoare) {
stergeInceput(head);
return;
}
Nod* temp = head;
while (temp->urmator != head && temp->urmator->valoare != valoare) {
temp = temp->urmator;
}
if (temp->urmator == head) return;
Nod* deSters = temp->urmator;
temp->urmator = deSters->urmator;
delete deSters;
}
4. Parcurgerea listei
void parcurgeLista(Nod* head) {
if (head == nullptr) return;
Nod* temp = head;
do {
cout << temp->valoare << ” „;
temp = temp->urmator;
} while (temp != head);
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);
if (head == nullptr) {
nod->urmator = nod;
head = nod;
} else {
Nod* temp = head;
while (temp->urmator != head) {
temp = temp->urmator;
}
nod->urmator = head;
temp->urmator = nod;
head = nod;
}
}
void adaugaSfarsit(Nod*& head, int valoare) {
Nod* nod = creeazaNod(valoare);
if (head == nullptr) {
nod->urmator = nod;
head = nod;
} else {
Nod* temp = head;
while (temp->urmator != head) {
temp = temp->urmator;
}
temp->urmator = nod;
nod->urmator = head;
}
}
void parcurgeLista(Nod* head) {
if (head == nullptr) return;
Nod* temp = head;
do {
cout << temp->valoare << ” „;
temp = temp->urmator;
} while (temp != head);
cout << endl;
}
void stergeInceput(Nod*& head) {
if (head == nullptr) return;
if (head->urmator == head) {
delete head;
head = nullptr;
return;
}
Nod* temp = head;
Nod* ultim = head;
while (ultim->urmator != head) {
ultim = ultim->urmator;
}
head = head->urmator;
ultim->urmator = head;
delete temp;
}
int main() {
Nod* lista = nullptr;
adaugaInceput(lista, 10);
adaugaInceput(lista, 20);
adaugaSfarsit(lista, 30);
cout << „Lista după adăugări: „;
parcurgeLista(lista);
stergeInceput(lista);
cout << „Lista după ștergerea primului element: „;
parcurgeLista(lista);
return 0;
}
7. Activități practice pentru elevi
- Implementați o funcție care determină lungimea unei liste circulare.
- 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ă.
8. 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.
9. Concluzie
- Listele circulare simplu înlănțuite sunt utile în aplicații care necesită parcurgere continuă, precum sistemele circulare de priorități.
- Implementarea necesită gestionarea atentă a pointerilor pentru a menține circularitatea listei.
- Practica este esențială pentru a stăpâni implementarea și utilizarea acestor liste.