Structuri de Date Liniare Implementate Dinamic – Liste Liniare Simplu Înlanțuite
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.
Structuri de Date Liniare Implementate Dinamic – Liste Liniare Dublu Înlanțuite
1. Obiectivele lecției:
- Să înțeleagă conceptul de listă liniară dublu înlănțuită.
- Să învețe cum să implementeze o listă dublu înlănțuită dinamic.
- Să implementeze operații comune: adăugare, ștergere, parcurgere în ambele sensuri.
2. Ce este o listă liniară dublu înlănțuită?
- Definiție:
O listă dublu î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.
- Un pointer către nodul anterior.
- Caracteristici:
- Permite parcurgerea în ambele direcții.
- Primul nod al listei (denumit head) are pointerul către nodul anterior setat la nullptr.
- Ultimul nod al listei (denumit tail) are pointerul către următorul nod setat la nullptr.
- Structura nodului:
struct Nod {
int valoare;
Nod* urmator;
Nod* anterior;
};
3. Avantaje și dezavantaje
| Avantaje | Dezavantaje |
| Permite parcurgerea bidirecțională. | Necesită mai multă memorie pentru pointere suplimentare. |
| Operații de inserare și ștergere eficiente. | Mai complicat de implementat decât listele simplu înlănțuite. |
| Utilă pentru structuri precum deque sau liste circulare. | Mai greu de gestionat pentru noduri multiple. |
4. Structura nodului
struct Nod {
int valoare; // Informația stocată în nod
Nod* urmator; // Pointer către următorul nod
Nod* anterior; // Pointer către nodul anterior
};
5. Operații comune pe liste 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;
} else {
nod->urmator = head;
head->anterior = nod;
head = nod;
}
}
- Adăugare la sfârșit:
void adaugaSfarsit(Nod*& head, Nod*& tail, int valoare) {
Nod* nod = creeazaNod(valoare);
if (tail == nullptr) {
head = tail = nod;
} else {
nod->anterior = tail;
tail->urmator = nod;
tail = nod;
}
}
3. Ștergerea unui element
- Ștergere de la început:
void stergeInceput(Nod*& head, Nod*& tail) {
if (head == nullptr) return;
Nod* temp = head;
if (head == tail) {
head = tail = nullptr;
} else {
head = head->urmator;
head->anterior = nullptr;
}
delete temp;
}
- Ștergere de la sfârșit:
void stergeSfarsit(Nod*& head, Nod*& tail) {
if (tail == nullptr) return;
Nod* temp = tail;
if (head == tail) {
head = tail = nullptr;
} else {
tail = tail->anterior;
tail->urmator = nullptr;
}
delete temp;
}
- Ștergerea unui nod cu o valoare specificată:
void stergeValoare(Nod*& head, Nod*& tail, int valoare) {
if (head == nullptr) return;
Nod* temp = head;
while (temp != nullptr && temp->valoare != valoare) {
temp = temp->urmator;
}
if (temp == nullptr) return;
if (temp == head) {
stergeInceput(head, tail);
} else if (temp == tail) {
stergeSfarsit(head, tail);
} else {
temp->anterior->urmator = temp->urmator;
temp->urmator->anterior = temp->anterior;
delete temp;
}
}
4. Parcurgerea listei
- Parcurgere de la început la sfârșit:
void parcurgeInainte(Nod* head) {
Nod* temp = head;
while (temp != nullptr) {
cout << temp->valoare << ” „;
temp = temp->urmator;
}
cout << endl;
}
- Parcurgere de la sfârșit la început:
void parcurgeInapoi(Nod* tail) {
Nod* temp = tail;
while (temp != nullptr) {
cout << temp->valoare << ” „;
temp = temp->anterior;
}
cout << endl;
}
6. 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;
} else {
nod->urmator = head;
head->anterior = nod;
head = nod;
}
}
void adaugaSfarsit(Nod*& head, Nod*& tail, int valoare) {
Nod* nod = creeazaNod(valoare);
if (tail == nullptr) {
head = tail = nod;
} else {
nod->anterior = tail;
tail->urmator = nod;
tail = nod;
}
}
void parcurgeInainte(Nod* head) {
Nod* temp = head;
while (temp != nullptr) {
cout << temp->valoare << ” „;
temp = temp->urmator;
}
cout << endl;
}
void parcurgeInapoi(Nod* tail) {
Nod* temp = tail;
while (temp != nullptr) {
cout << temp->valoare << ” „;
temp = temp->anterior;
}
cout << endl;
}
void stergeInceput(Nod*& head, Nod*& tail) {
if (head == nullptr) return;
Nod* temp = head;
if (head == tail) {
head = tail = nullptr;
} else {
head = head->urmator;
head->anterior = nullptr;
}
delete temp;
}
void stergeSfarsit(Nod*& head, Nod*& tail) {
if (tail == nullptr) return;
Nod* temp = tail;
if (head == tail) {
head = tail = nullptr;
} else {
tail = tail->anterior;
tail->urmator = nullptr;
}
delete temp;
}
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);
stergeInceput(head, tail);
cout << „După ștergerea primului nod: „;
parcurgeInainte(head);
stergeSfarsit(head, tail);
cout << „După ștergerea ultimului nod: „;
parcurgeInainte(head);
return 0;
}
7. Activități practice pentru elevi
- Implementați o funcție care determină lungimea unei liste dublu înlănțuite.
- Scrieți o funcție care inserează un nod înainte de un nod specificat.
- Realizați o funcție care inversează o listă dublu înlănțuită.
8. Scheme logice
- Adăugare:
- Creează nod -> Actualizează legăturile -> Actualizează head sau tail.
- Ștergere:
- Verifică dacă lista este goală -> Actualizează legăturile -> Eliberează memoria.
9. Concluzie
- Listele dublu înlănțuite oferă flexibilitate și eficiență pentru operații bidirecționale.
- Sunt utile în aplicații care necesită acces rapid în ambele sensuri.
- Practica este esențială pentru a înțelege și a implementa corect această structură de date.
Structuri de Date Liniare Implementate Dinamic – Liste Circulare Simplu Înlanțuite
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.
Structuri de Date Liniare Implementate Dinamic – Liste Circulare Dublu Înlanțuite
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.
Structuri de Date Liniare Implementate Dinamic – Stiva
1. Obiectivele lecției:
- Să înțeleagă conceptul de stivă și utilizările sale.
- Să învețe cum să implementeze o stivă utilizând alocarea dinamică a memoriei.
- Să implementeze operații comune pe stive: push, pop, peek și isEmpty.
2. Ce este o stivă?
- Definiție:
O stivă este o structură de date liniară care urmează principiul LIFO (Last In, First Out), ceea ce înseamnă că ultimul element introdus este primul care se scoate. - Operații comune:
- Push: Adăugarea unui element în stivă.
- Pop: Eliminarea elementului de la vârful stivei.
- Peek: Accesarea elementului de la vârful stivei fără a-l elimina.
- isEmpty: Verificarea dacă stiva este goală.
3. Avantaje și dezavantaje
| Avantaje | Dezavantaje |
| Structură simplă și ușor de implementat. | Accesibilitate limitată (doar vârful stivei). |
| Eficientă pentru gestionarea problemelor LIFO. | Necesită mai multe operații pentru acces aleator. |
| Utilă în aplicații precum recursivitatea sau backtracking. |
4. Implementarea unei stive folosind liste simplu înlănțuite
Structura unui nod
- Structura nodului pentru stivă:
struct Nod {
int valoare; // Informația stocată
Nod* urmator; // Pointer către următorul nod
};
- Pointerul către vârful stivei:
Nod* top = nullptr;
1. Crearea unui nod
Nod* creeazaNod(int valoare) {
Nod* nod = new Nod();
nod->valoare = valoare;
nod->urmator = nullptr;
return nod;
}
2. Operații comune pe stivă
- Push (Adăugarea unui element):
void push(Nod*& top, int valoare) {
Nod* nod = creeazaNod(valoare);
nod->urmator = top;
top = nod;
}
- Pop (Eliminarea elementului de la vârf):
void pop(Nod*& top) {
if (top == nullptr) {
cout << „Stiva este goală. Nu se poate elimina elementul.” << endl;
return;
}
Nod* temp = top;
top = top->urmator;
delete temp;
}
- Peek (Accesarea elementului de la vârf):
int peek(Nod* top) {
if (top == nullptr) {
cout << „Stiva este goală.” << endl;
return -1; // Valoare simbolică pentru eroare
}
return top->valoare;
}
- isEmpty (Verificarea dacă stiva este goală):
bool isEmpty(Nod* top) {
return top == nullptr;
}
3. Parcurgerea stivei
void parcurgeStiva(Nod* top) {
if (top == nullptr) {
cout << „Stiva este goală.” << endl;
return;
}
Nod* temp = top;
while (temp != nullptr) {
cout << temp->valoare << ” „;
temp = temp->urmator;
}
cout << endl;
}
4. 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 push(Nod*& top, int valoare) {
Nod* nod = creeazaNod(valoare);
nod->urmator = top;
top = nod;
}
void pop(Nod*& top) {
if (top == nullptr) {
cout << „Stiva este goală. Nu se poate elimina elementul.” << endl;
return;
}
Nod* temp = top;
top = top->urmator;
delete temp;
}
int peek(Nod* top) {
if (top == nullptr) {
cout << „Stiva este goală.” << endl;
return -1; // Valoare simbolică pentru eroare
}
return top->valoare;
}
bool isEmpty(Nod* top) {
return top == nullptr;
}
void parcurgeStiva(Nod* top) {
if (top == nullptr) {
cout << „Stiva este goală.” << endl;
return;
}
Nod* temp = top;
while (temp != nullptr) {
cout << temp->valoare << ” „;
temp = temp->urmator;
}
cout << endl;
}
int main() {
Nod* top = nullptr;
push(top, 10);
push(top, 20);
push(top, 30);
cout << „Stiva după adăugări: „;
parcurgeStiva(top);
cout << „Elementul de la vârf: ” << peek(top) << endl;
pop(top);
cout << „Stiva după eliminarea elementului de la vârf: „;
parcurgeStiva(top);
cout << „Stiva este goală? ” << (isEmpty(top) ? „Da” : „Nu”) << endl;
return 0;
}
5. Utilizări practice ale stivei
- Evarea expresiilor aritmetice:
Utilizată în evarea expresiilor postfixate sau conversia expresiilor infixate. - Controlul recursivității:
Stiva este utilizată intern pentru a gestiona apelurile recursive. - Operații de backtracking:
Găsirea soluțiilor prin explorarea căilor posibile și revenirea (ex.: labirinturi). - Parantezare corectă:
Verificarea dacă o expresie conține paranteze deschise și închise în mod corect.
6. Activități practice pentru elevi
- Implementați o funcție care verifică dacă o expresie aritmetică are paranteze corecte utilizând o stivă.
- Realizați o funcție care calculează factorialul unui număr utilizând o stivă în loc de recursivitate.
- Implementați un algoritm care convertește o expresie infixată într-o expresie postfixată utilizând o stivă.
7. Scheme logice
- Push:
- Creează un nod -> Conectează nodul la vârful stivei -> Actualizează top.
- Pop:
- Verifică dacă stiva este goală -> Elimină nodul de la vârf -> Actualizează top.
- Peek:
- Returnează valoarea din nodul de la vârf fără a-l elimina.
8. Concluzie
- Stiva este o structură de date esențială în informatică, cu multiple aplicații practice.
- Implementarea sa folosind alocarea dinamică oferă flexibilitate în gestionarea datelor.
- Practica ajută la înțelegerea conceptelor și la utilizarea eficientă a acestei structuri.
Structuri de Date Liniare Implementate Dinamic – Coada
1. Obiectivele lecției:
- Să înțeleagă conceptul de coadă și principiul său de funcționare.
- Să învețe cum să implementeze o coadă utilizând alocarea dinamică a memoriei.
- Să implementeze operații comune pe cozi: enqueue, dequeue, peek, isEmpty.
2. Ce este o coadă?
- Definiție:
O coadă este o structură de date liniară care urmează principiul FIFO (First In, First Out), ceea ce înseamnă că primul element introdus este primul care se scoate. - Operații comune:
- Enqueue: Adăugarea unui element la sfârșitul cozii.
- Dequeue: Eliminarea elementului din fața cozii.
- Peek: Accesarea elementului din fața cozii fără a-l elimina.
- isEmpty: Verificarea dacă coada este goală.
- Aplicații practice:
- Gestionarea cozii de imprimare.
- Planificarea proceselor în sistemele de operare.
- Simulări (ex.: linii de așteptare, sisteme bancare).
3. Avantaje și dezavantaje
| Avantaje | Dezavantaje |
| Structură simplă și ușor de implementat. | Inserarea și ștergerea sunt limitate la capete. |
| Eficientă pentru gestionarea operațiilor FIFO. | Acces aleator nu este posibil. |
| Poate fi implementată dinamic. | Necesită gestionarea pointerilor pentru dinamism. |
4. Implementarea unei cozi folosind liste simplu înlănțuite
Structura unui nod
- Structura nodului pentru coadă:
struct Nod {
int valoare; // Informația stocată
Nod* urmator; // Pointer către următorul nod
};
- Pointeri pentru gestionarea cozii:
- Front: Indică primul element al cozii.
- Rear: Indică ultimul element al cozii.
1. Crearea unui nod
Nod* creeazaNod(int valoare) {
Nod* nod = new Nod();
nod->valoare = valoare;
nod->urmator = nullptr;
return nod;
}
2. Operații comune pe coadă
- Enqueue (Adăugarea unui element):
void enqueue(Nod*& front, Nod*& rear, int valoare) {
Nod* nod = creeazaNod(valoare);
if (rear == nullptr) { // Coada este goală
front = rear = nod;
} else {
rear->urmator = nod;
rear = nod;
}
}
- Dequeue (Eliminarea elementului din față):
void dequeue(Nod*& front, Nod*& rear) {
if (front == nullptr) { // Coada este goală
cout << „Coada este goală. Nu se poate elimina elementul.” << endl;
return;
}
Nod* temp = front;
front = front->urmator;
if (front == nullptr) { // Dacă coada devine goală
rear = nullptr;
}
delete temp;
}
- Peek (Accesarea elementului din față):
int peek(Nod* front) {
if (front == nullptr) {
cout << „Coada este goală.” << endl;
return -1; // Valoare simbolică pentru eroare
}
return front->valoare;
}
- isEmpty (Verificarea dacă coada este goală):
bool isEmpty(Nod* front) {
return front == nullptr;
}
3. Parcurgerea cozii
void parcurgeCoada(Nod* front) {
if (front == nullptr) {
cout << „Coada este goală.” << endl;
return;
}
Nod* temp = front;
while (temp != nullptr) {
cout << temp->valoare << ” „;
temp = temp->urmator;
}
cout << endl;
}
4. 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 enqueue(Nod*& front, Nod*& rear, int valoare) {
Nod* nod = creeazaNod(valoare);
if (rear == nullptr) { // Coada este goală
front = rear = nod;
} else {
rear->urmator = nod;
rear = nod;
}
}
void dequeue(Nod*& front, Nod*& rear) {
if (front == nullptr) { // Coada este goală
cout << „Coada este goală. Nu se poate elimina elementul.” << endl;
return;
}
Nod* temp = front;
front = front->urmator;
if (front == nullptr) { // Dacă coada devine goală
rear = nullptr;
}
delete temp;
}
int peek(Nod* front) {
if (front == nullptr) {
cout << „Coada este goală.” << endl;
return -1; // Valoare simbolică pentru eroare
}
return front->valoare;
}
bool isEmpty(Nod* front) {
return front == nullptr;
}
void parcurgeCoada(Nod* front) {
if (front == nullptr) {
cout << „Coada este goală.” << endl;
return;
}
Nod* temp = front;
while (temp != nullptr) {
cout << temp->valoare << ” „;
temp = temp->urmator;
}
cout << endl;
}
int main() {
Nod* front = nullptr;
Nod* rear = nullptr;
enqueue(front, rear, 10);
enqueue(front, rear, 20);
enqueue(front, rear, 30);
cout << „Coada după adăugări: „;
parcurgeCoada(front);
cout << „Elementul din fața cozii: ” << peek(front) << endl;
dequeue(front, rear);
cout << „Coada după eliminarea elementului din față: „;
parcurgeCoada(front);
cout << „Coada este goală? ” << (isEmpty(front) ? „Da” : „Nu”) << endl;
return 0;
}
5. Utilizări practice ale cozii
- Planificarea proceselor:
Cozile sunt utilizate pentru gestionarea proceselor în ordine de sosire. - Aplicații grafice:
Cozile sunt utilizate pentru parcurgerea pe niveluri (Breadth-First Search – BFS). - Aplicații în rețele:
Gestionarea pachetelor de date în comunicațiile de rețea.
6. Activități practice pentru elevi
- Implementați o funcție care verifică dacă două cozi sunt identice.
- Scrieți un program care inversează elementele unei cozi utilizând o stivă.
- Realizați o funcție care simulează un sistem de coadă de așteptare pentru un ATM.
7. Scheme logice
- Enqueue:
- Creează nod -> Conectează nodul la sfârșitul cozii -> Actualizează rear.
- Dequeue:
- Verifică dacă coada este goală -> Elimină nodul din față -> Actualizează front și, eventual, rear.
8. Concluzie
- Cozile sunt structuri de date esențiale pentru gestionarea operațiilor FIFO.
- Implementarea lor dinamică oferă flexibilitate în gestionarea dimensiunii.
- Practica ajută la înțelegerea utilizării și implementării eficiente a acestei structuri.
Structuri de Date Arborescente Implementate Dinamic – Arbori
1. Obiectivele lecției:
- Să înțeleagă conceptul de arbore și proprietățile acestuia.
- Să învețe cum să implementeze un arbore binar folosind alocarea dinamică a memoriei.
- Să implementeze operații comune pe arbori: inserare, traversare (în ordine, preordine, postordine) și căutare.
2. Ce este un arbore?
- Definiție:
Un arbore este o structură de date non-liniară care conține noduri organizate ierarhic. Fiecare nod poate avea copii, iar primul nod este numit rădăcină (root). - Proprietăți ale arborilor:
- Un arbore are un singur nod rădăcină.
- Fiecare nod are un părinte, cu excepția rădăcinii.
- Nodurile fără copii se numesc frunze (leaves).
- Un arbore poate avea subarbori.
- Tipuri de arbori:
- Arbore binar: Fiecare nod poate avea cel mult doi copii.
- Arbore binar de căutare (BST): Valorile din subarborele stâng sunt mai mici decât rădăcina, iar cele din subarborele drept sunt mai mari.
3. Avantaje și dezavantaje
| Avantaje | Dezavantaje |
| Eficient pentru căutări rapide în structuri mari (BST). | Implementarea și gestionarea sunt mai complexe. |
| Structură flexibilă pentru date ierarhice. | Consumul de memorie crește cu dimensiunea arborelui. |
4. Structura unui nod
- Structura unui nod pentru un arbore binar:
struct Nod {
int valoare; // Informația stocată
Nod* stanga; // Pointer către subarborele stâng
Nod* dreapta; // Pointer către subarborele drept
};
- Pointerul către rădăcina arborelui:
Nod* radacina = nullptr;
5. Operații comune pe arbori binari
1. Crearea unui nod
Nod* creeazaNod(int valoare) {
Nod* nod = new Nod();
nod->valoare = valoare;
nod->stanga = nullptr;
nod->dreapta = nullptr;
return nod;
}
2. Inserarea unui nod într-un arbore binar de căutare (BST)
- Funcția de inserare:
Nod* insereazaNod(Nod* radacina, int valoare) {
if (radacina == nullptr) {
return creeazaNod(valoare);
}
if (valoare < radacina->valoare) {
radacina->stanga = insereazaNod(radacina->stanga, valoare);
} else if (valoare > radacina->valoare) {
radacina->dreapta = insereazaNod(radacina->dreapta, valoare);
}
return radacina;
}
3. Traversări ale arborelui
- Traversare în ordine (in-order):
Vizitează nodurile în ordinea: stânga → rădăcină → dreapta.
void traversareInOrdine(Nod* radacina) {
if (radacina == nullptr) return;
traversareInOrdine(radacina->stanga);
cout << radacina->valoare << ” „;
traversareInOrdine(radacina->dreapta);
}
- Traversare preordine (pre-order):
Vizitează nodurile în ordinea: rădăcină → stânga → dreapta.
void traversarePreOrdine(Nod* radacina) {
if (radacina == nullptr) return;
cout << radacina->valoare << ” „;
traversarePreOrdine(radacina->stanga);
traversarePreOrdine(radacina->dreapta);
}
- Traversare postordine (post-order):
Vizitează nodurile în ordinea: stânga → dreapta → rădăcină.
void traversarePostOrdine(Nod* radacina) {
if (radacina == nullptr) return;
traversarePostOrdine(radacina->stanga);
traversarePostOrdine(radacina->dreapta);
cout << radacina->valoare << ” „;
}
4. Căutarea unui element
- Funcția de căutare:
bool cautaValoare(Nod* radacina, int valoare) {
if (radacina == nullptr) {
return false;
}
if (valoare == radacina->valoare) {
return true;
} else if (valoare < radacina->valoare) {
return cautaValoare(radacina->stanga, valoare);
} else {
return cautaValoare(radacina->dreapta, valoare);
}
}
5. Exemplu complet
#include <iostream>
using namespace std;
struct Nod {
int valoare;
Nod* stanga;
Nod* dreapta;
};
Nod* creeazaNod(int valoare) {
Nod* nod = new Nod();
nod->valoare = valoare;
nod->stanga = nullptr;
nod->dreapta = nullptr;
return nod;
}
Nod* insereazaNod(Nod* radacina, int valoare) {
if (radacina == nullptr) {
return creeazaNod(valoare);
}
if (valoare < radacina->valoare) {
radacina->stanga = insereazaNod(radacina->stanga, valoare);
} else if (valoare > radacina->valoare) {
radacina->dreapta = insereazaNod(radacina->dreapta, valoare);
}
return radacina;
}
void traversareInOrdine(Nod* radacina) {
if (radacina == nullptr) return;
traversareInOrdine(radacina->stanga);
cout << radacina->valoare << ” „;
traversareInOrdine(radacina->dreapta);
}
bool cautaValoare(Nod* radacina, int valoare) {
if (radacina == nullptr) {
return false;
}
if (valoare == radacina->valoare) {
return true;
} else if (valoare < radacina->valoare) {
return cautaValoare(radacina->stanga, valoare);
} else {
return cautaValoare(radacina->dreapta, valoare);
}
}
int main() {
Nod* radacina = nullptr;
radacina = insereazaNod(radacina, 50);
insereazaNod(radacina, 30);
insereazaNod(radacina, 70);
insereazaNod(radacina, 20);
insereazaNod(radacina, 40);
insereazaNod(radacina, 60);
insereazaNod(radacina, 80);
cout << „Traversare în ordine: „;
traversareInOrdine(radacina);
cout << endl;
cout << „Căutare valoare 40: ” << (cautaValoare(radacina, 40) ? „Găsită” : „Negăsită”) << endl;
cout << „Căutare valoare 25: ” << (cautaValoare(radacina, 25) ? „Găsită” : „Negăsită”) << endl;
return 0;
}
6. Activități practice pentru elevi
- Implementați o funcție care determină numărul de noduri dintr-un arbore.
- Realizați o funcție care calculează înălțimea unui arbore.
- Scrieți un program care determină dacă un arbore este arbore binar de căutare.
7. Scheme logice
- Inserare:
- Verifică dacă nodul curent este gol -> Creează un nou nod -> Compară valoarea și inserează în stânga sau dreapta.
- Traversare:
- Utilizează recursivitate pentru a parcurge nodurile în ordinea specificată.
- Căutare:
- Compară valoarea căutată cu nodul curent -> Explorează subarborele corespunzător.
8. Concluzie
- Arborii sunt structuri de date esențiale pentru gestionarea informațiilor ierarhice și pentru căutări rapide.
- Implementarea arborilor binari necesită înțelegerea recursivității.
- Practica ajută la stăpânirea conceptelor și implementării eficiente.