|

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ă?

  1. 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ă.
  2. Caracteristici:
    • Permite parcurgerea listei în ambele sensuri.
    • Este circulară, astfel încât lista poate fi parcursă continuu fără punct final.
  3. 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

AvantajeDezavantaje
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

  1. 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;

    }

}

  1. 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

  1. Ș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;

    }

}

  1. Ș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;

    }

}

  1. Ș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

  1. 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;

}

  1. 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

  1. Implementați o funcție care determină lungimea unei liste circulare dublu înlănțuite.
  2. Scrieți o funcție care inserează un nod după un alt nod specificat.
  3. Realizați o funcție care verifică dacă un element există în listă.

7. Scheme logice

  1. Adăugare:
    • Creează nod -> Actualizează pointerii -> Asigură circularitatea listei.
  2. Ș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.

Similar Posts

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *