Structuri de date implementate dinamic

Nodul conține un număr întreg și adresa nodului următor. Lista vidă are prim și ultim egali cu NULL, iar testul prim == NULL arată dacă lista este vidă.

struct nod {
    int info;    // informatia utila
    nod *urm;    // adresa nodului urmator
};

nod *prim = NULL, *ultim = NULL;   // lista vida

Pașii.

1. Se alocă memorie pentru nodul nou și se scrie informația în el.
2. Legătura nodului nou primește adresa primului nod.
3. Dacă lista era vidă, nodul nou devine și ultimul nod.
4. Nodul nou devine primul nod.

Ordinea pașilor 2 și 4 nu se poate inversa: după prim = nou, adresa vechiului prim nod nu mai este păstrată nicăieri, iar lista se pierde.

void adaugaInceput(nod *&prim, nod *&ultim, int x) {
    nod *nou = new nod;
    nou->info = x;
    nou->urm = prim;
    if (prim == NULL)          // lista era vida
        ultim = nou;
    prim = nou;
}

Pașii.

1. Se alocă memorie pentru nodul nou și se scrie informația în el.
2. Legătura nodului nou primește valoarea NULL, fiindcă el va fi ultimul.
3. Dacă lista este vidă, nodul nou devine primul nod; altfel, legătura ultimului nod primește adresa nodului nou.
4. Nodul nou devine ultimul nod.

Crearea listei se face pornind de la lista vidă și inserând la sfârșit fiecare valoare, în ordinea citirii.

void adaugaSfarsit(nod *&prim, nod *&ultim, int x) {
    nod *nou = new nod;
    nou->info = x;
    nou->urm = NULL;
    if (prim == NULL)          // lista era vida
        prim = nou;
    else
        ultim->urm = nou;
    ultim = nou;
}

Nodul q după care se inserează este cunoscut, deci nu este nevoie de parcurgere.

Pașii.

1. Se alocă memorie pentru nodul nou și se scrie informația în el.
2. Legătura nodului nou primește adresa succesorului lui q.
3. Legătura lui q primește adresa nodului nou.
4. Dacă q era ultimul nod, nodul nou devine ultimul nod.

void adaugaDupa(nod *q, nod *&ultim, int x) {
    nod *nou = new nod;
    nou->info = x;
    nou->urm = q->urm;
    q->urm = nou;
    if (q == ultim)
        ultim = nou;
}

Nodul nou trebuie legat de predecesorul lui q, dar într-o listă simplu înlănțuită un nod nu păstrează adresa predecesorului. Predecesorul se află prin parcurgerea listei de la început.

Pașii.

1. Se alocă memorie pentru nodul nou și se scrie informația în el.
2. Legătura nodului nou primește adresa lui q.
3. Dacă q este primul nod, nodul nou devine primul nod.
4. Altfel, se parcurge lista până la nodul p pentru care p->urm este q, iar legătura lui p primește adresa nodului nou.

void adaugaInainte(nod *&prim, nod *q, int x) {
    nod *nou = new nod;
    nou->info = x;
    nou->urm = q;
    if (q == prim)
        prim = nou;
    else {
        nod *p = prim;
        while (p->urm != q)    // predecesorul lui q
            p = p->urm;
        p->urm = nou;
    }
}

Inserarea se poate face și fără parcurgere. Nodul nou se inserează după q, apoi informația lui q se mută în nodul nou, iar în q se scrie informația de inserat. Ordinea informațiilor în listă este aceeași ca la inserarea înaintea lui q.

Metoda schimbă însă informația păstrată la adresa q. Dacă programul reținuse adresa lui q în alt pointer, acel pointer indică de acum informația nouă.

void adaugaInainteCopiere(nod *q, nod *&ultim, int x) {
    nod *nou = new nod;
    nou->info = q->info;       // nodul nou preia informatia lui q
    nou->urm = q->urm;
    q->info = x;               // in q se scrie informatia de inserat
    q->urm = nou;
    if (q == ultim)
        ultim = nou;
}

Într-o listă ordonată crescător, nodul nou se inserează înaintea primului nod cu informația mai mare decât x. Dacă lista este vidă sau x este mai mic decât informația din primul nod, inserarea se face la început. Altfel, se caută nodul p după care trebuie inserat: parcurgerea continuă cât timp există un nod următor și informația lui este mai mică decât x.

void inserareOrdonata(nod *&prim, int x) {
    nod *nou = new nod;
    nou->info = x;
    if (prim == NULL || x < prim->info) {
        nou->urm = prim;
        prim = nou;
    } else {
        nod *p = prim;
        while (p->urm != NULL && p->urm->info < x)
            p = p->urm;
        nou->urm = p->urm;
        p->urm = nou;
    }
}

Nodurile se vizitează de la primul la ultimul, cu un pointer p care pornește de la prim și trece la fiecare pas la adresa din p->urm. Parcurgerea se încheie când p devine NULL.

Pentru parcurgere se folosește un pointer separat. Dacă s-ar avansa chiar cu prim, adresa primului nod s-ar pierde.

void afisare(nod *prim) {
    for (nod *p = prim; p != NULL; p = p->urm)
        cout << p->info << " ";
    cout << endl;
}

Nodurile se verifică pe rând, începând cu primul, până la găsirea nodului căutat sau până la sfârșitul listei. Funcția întoarce adresa nodului găsit sau NULL.

Se poate căuta:

• nodul care conține o valoare dată;
• nodul aflat într-o poziție dată, numărând pozițiile de la 1.

Ordinea condițiilor din while contează: p != NULL se verifică primul, astfel încât p->info nu se evaluează niciodată pentru un pointer NULL.

nod *cauta(nod *prim, int x) {
    nod *p = prim;
    while (p != NULL && p->info != x)
        p = p->urm;
    return p;
}

nod *nodulDePePozitia(nod *prim, int k) {
    nod *p = prim;
    for (int i = 1; p != NULL && i < k; i++)
        p = p->urm;
    return p;
}

Operația cere o listă nevidă.

Pașii.

1. Adresa primului nod se salvează în pointerul q.
2. Succesorul primului nod devine primul nod.
3. Se eliberează memoria de la adresa q.
4. Dacă lista a rămas vidă, ultim primește valoarea NULL.

void eliminaPrimul(nod *&prim, nod *&ultim) {
    nod *q = prim;
    prim = prim->urm;
    delete q;
    if (prim == NULL)          // lista a ramas vida
        ultim = NULL;
}

Pașii.

1. Dacă lista are un singur nod, acesta se eliberează, iar lista devine vidă.
2. Altfel, se parcurge lista până la predecesorul ultimului nod, adică nodul p pentru care p->urm este ultim.
3. Legătura lui p primește valoarea NULL.
4. Se eliberează ultimul nod, iar p devine ultimul nod.

void eliminaUltimul(nod *&prim, nod *&ultim) {
    if (prim == ultim) {       // un singur nod
        delete prim;
        prim = ultim = NULL;
        return;
    }
    nod *p = prim;
    while (p->urm != ultim)    // predecesorul ultimului nod
        p = p->urm;
    p->urm = NULL;
    delete ultim;
    ultim = p;
}

Un nod se scoate din listă legând predecesorul lui de succesorul lui. De aceea ștergerea se exprimă prin predecesor: se elimină succesorul nodului p.

Pașii.

1. Adresa succesorului lui p se salvează în pointerul q.
2. Legătura lui p primește adresa succesorului lui q.
3. Dacă q era ultimul nod, p devine ultimul nod.
4. Se eliberează memoria de la adresa q.

Pentru a șterge un nod cu o valoare dată, se caută predecesorul lui, ca la inserarea înaintea unui nod, iar dacă nodul căutat este chiar primul, se folosește ștergerea primului nod.

void eliminaDupa(nod *p, nod *&ultim) {
    nod *q = p->urm;           // nodul care se sterge
    p->urm = q->urm;
    if (q == ultim)
        ultim = p;
    delete q;
}

Nodurile se eliberează pe rând, de la primul la ultimul. Înaintea eliberării unui nod se trece la succesorul lui, fiindcă după delete câmpul urm al nodului eliberat nu mai poate fi citit.

void eliberare(nod *&prim, nod *&ultim) {
    while (prim != NULL) {
        nod *q = prim;
        prim = prim->urm;
        delete q;
    }
    ultim = NULL;
}

Crearea și inserarea după ultimul nod. Se inserează ca într-o listă simplu înlănțuită, apoi legătura ultimului nod primește adresa primului nod. Dacă lista are un singur nod, acesta este legat de el însuși.

void adaugaCirculara(nod *&prim, nod *&ultim, int x) {
    nod *nou = new nod;
    nou->info = x;
    if (prim == NULL)
        prim = nou;
    else
        ultim->urm = nou;
    ultim = nou;
    ultim->urm = prim;         // ultimul nod se leaga de primul
}

Parcurgerea. Nu există o legătură egală cu NULL la care să se oprească parcurgerea. Se pornește de la primul nod și se oprește la revenirea în primul nod. Fiindcă primul nod trebuie prelucrat înaintea testului, parcurgerea se scrie cu o structură repetitivă cu test final.

void afisareCirculara(nod *prim) {
    if (prim == NULL)
        return;
    nod *p = prim;
    do {
        cout << p->info << " ";
        p = p->urm;
    } while (p != prim);
    cout << endl;
}

Ștergerea nodului care urmează după nodul p. Legătura lui p primește adresa succesorului nodului șters. Dacă nodul șters era primul sau ultimul, se actualizează prim, respectiv ultim. Dacă nodul șters era singurul din listă, adică succesorul lui p este chiar p, lista devine vidă.

void eliminaDupaCirculara(nod *p, nod *&prim, nod *&ultim) {
    nod *q = p->urm;
    if (q == p)                // singurul nod din lista
        prim = ultim = NULL;
    else {
        p->urm = q->urm;
        if (q == prim)
            prim = q->urm;
        if (q == ultim)
            ultim = p;
    }
    delete q;
}

Operațiile de la lista simplu înlănțuită se păstrează, dar la fiecare inserare și la fiecare ștergere se actualizează ambele legături ale nodurilor vecine.

struct nod {
    int info;
    nod *ant, *urm;   // adresele predecesorului si succesorului
};

La sfârșit. Nodul nou are ca predecesor ultimul nod și nu are succesor. Dacă lista este vidă, el devine primul nod; altfel, legătura urm a ultimului nod primește adresa lui.

La început. Nodul nou nu are predecesor și are ca succesor primul nod. Dacă lista este vidă, el devine ultimul nod; altfel, legătura ant a primului nod primește adresa lui.

void adaugaSfarsit(nod *&prim, nod *&ultim, int x) {
    nod *nou = new nod;
    nou->info = x;
    nou->ant = ultim;
    nou->urm = NULL;
    if (prim == NULL)
        prim = nou;
    else
        ultim->urm = nou;
    ultim = nou;
}

void adaugaInceput(nod *&prim, nod *&ultim, int x) {
    nod *nou = new nod;
    nou->info = x;
    nou->ant = NULL;
    nou->urm = prim;
    if (prim == NULL)
        ultim = nou;
    else
        prim->ant = nou;
    prim = nou;
}

După nodul q. Nodul nou se așază între q și succesorul lui. Dacă q are succesor, legătura ant a succesorului primește adresa nodului nou; altfel, nodul nou devine ultimul nod.

Înaintea nodului q. Nodul nou se așază între predecesorul lui q și q. Predecesorul se citește din q->ant, deci parcurgerea nu mai este necesară. Dacă q nu are predecesor, nodul nou devine primul nod.

void adaugaDupa(nod *q, nod *&ultim, int x) {
    nod *nou = new nod;
    nou->info = x;
    nou->ant = q;
    nou->urm = q->urm;
    if (q->urm != NULL)
        q->urm->ant = nou;
    else
        ultim = nou;
    q->urm = nou;
}

void adaugaInainte(nod *&prim, nod *q, int x) {
    nod *nou = new nod;
    nou->info = x;
    nou->urm = q;
    nou->ant = q->ant;
    if (q->ant != NULL)
        q->ant->urm = nou;
    else
        prim = nou;
    q->ant = nou;
}

De la primul nod la ultimul, parcurgerea urmează legăturile urm. De la ultimul nod la primul, urmează legăturile ant și pornește de la ultim.

void afisareInainte(nod *prim) {
    for (nod *p = prim; p != NULL; p = p->urm)
        cout << p->info << " ";
    cout << endl;
}

void afisareInapoi(nod *ultim) {
    for (nod *p = ultim; p != NULL; p = p->ant)
        cout << p->info << " ";
    cout << endl;
}

Nodul q se poate șterge direct, fiindcă ambii vecini ai lui sunt cunoscuți.

Pașii.

1. Dacă q are predecesor, legătura urm a predecesorului primește adresa succesorului lui q; altfel, q era primul nod, iar succesorul lui devine primul nod.
2. Dacă q are succesor, legătura ant a succesorului primește adresa predecesorului lui q; altfel, q era ultimul nod, iar predecesorul lui devine ultimul nod.
3. Se eliberează memoria de la adresa q.

Aceeași funcție tratează ștergerea primului nod, a ultimului nod și a unui nod din interior.

void elimina(nod *&prim, nod *&ultim, nod *q) {
    if (q->ant != NULL)
        q->ant->urm = q->urm;
    else
        prim = q->urm;         // se sterge primul nod
    if (q->urm != NULL)
        q->urm->ant = q->ant;
    else
        ultim = q->ant;        // se sterge ultimul nod
    delete q;
}

La adăugare, nodul nou se leagă de vechiul vârf și devine vârf. La extragere, nodul de sub vârf devine vârf, iar vechiul vârf se eliberează.

void adauga(nod *&varf, int x) {
    nod *nou = new nod;
    nou->info = x;
    nou->urm = varf;
    varf = nou;
}

void extrage(nod *&varf) {
    nod *q = varf;
    varf = varf->urm;
    delete q;
}