Liste Liniare: Implementare Statică

Structuri de Date - Clasa a XI-a
adr (Index Nod Nou/Țintă) p (Index Cursor) q (Index Anterior)

Concept: Memorie Simulată (Memory Pool)

Vectorul lista[MAX]
Reprezintă "heap-ul" simulat. Este o zonă contiguă de memorie unde sunt stocate nodurile. "Pointerii" sunt de fapt indici în acest vector (0..99).
Vectorul s[MAX]
Actionează ca un "Allocation Table". Reține starea fiecărui bloc de memorie: 0 = Liber, 1 = Alocat.
Variabila prim
Este echivalentul pointerului head. Reține indexul primului nod din structura logică. -1 echivalează cu NULL.
Modulul 0: Gestionarea Memoriei (Alocare & Dealocare)

0.1 Verificare Capacitate (exista_spatiu)

int exista_spatiu() {
    
    // Verificam contorul global
    if (nr < MAX) {
        return 1; // True
    }
    
    return 0;     // False (Stack Overflow)
}
Această funcție previne erorile de depășire a memoriei statice.
Verifică variabila globală nr (numărul curent de noduri active) față de constanta MAX.
Este apelată obligatoriu înainte de orice adauga sau inserare.

0.2 Alocare Memorie (aloca)

void aloca(int &adr) {
    int i = 0;

    // Cautare liniara a primului loc liber
    while (s[i] == 1 && i < MAX) {
        i++;
    }

    adr = i;    // Returnam indexul liber gasit
    s[i] = 1;   // Marcam ca OCUPAT
    nr++;       // Incrementam contorul
}
Simulează operatorul new.
Pasul 1: Parcurge vectorul caracteristic s[] (harta memoriei).
Pasul 2: Se oprește la primul 0 găsit (First Fit).
Pasul 3: Setează s[i] = 1 pentru a rezerva blocul și returnează indexul prin referința adr.
1 i=0 1 0 Scanare... adr = 2

0.3 Eliberare Memorie (elibereaza)

void elibereaza(int adr) {
    // Marcam locul ca fiind LIBER
    s[adr] = 0;
    
    // Decrementam numarul de noduri active
    nr--;
    
    if (adr == prim) {
        prim = -1;
    }
}
Simulează operatorul delete.
Transformă valoarea din s[adr] din 1 în 0.
Blocul de memorie devine disponibil pentru a fi refolosit de un viitor apel aloca().
Modulul 1: Operații pe Lista Liniară

1. Adăugare la Final (adauga)

void adauga(int &prim, int x) {
    int adr, p;
    aloca(adr);
    
    lista[adr].inf = x;
    lista[adr].urm = -1; // Va fi ultimul nod

    if (prim == -1) {
        prim = adr;
    } 
    else {
        p = prim;
        
        // Traversare pana la ultimul nod
        while (lista[p].urm != -1) {
            p = lista[p].urm;
        }
        
        // Legarea noului nod
        lista[p].urm = adr;
    }
}
Pasul 1: Se obține un bloc de memorie nou (indexul adr) și se inițializează (urm = -1).
Pasul 2: Dacă lista nu e vidă, se folosește cursorul p pentru traversare.
Pasul 3: Bucla while avansează p atâta timp cât urm nu este -1.
Pasul 4: Când p ajunge pe ultimul nod existent, se actualizează legătura spre adr.
Ultim Vechi Cursor (p) Legare Nod Nou Target (adr)

2. Căutare Valoare (cautare)

int cautare(int x) {
    int p = prim;

    // Parcurgere liniara
    while (p != -1 && lista[p].inf != x) {
        p = lista[p].urm;
    }

    return p; // Returneaza indexul sau -1
}
Algoritm standard de parcurgere liniară.
Cursorul p avansează din nod în nod.
Complexitate: O(n).

3. Inserare DUPĂ un Nod (inserare_dupa)

void inserare_dupa(int adr, int x) {
    int p;
    aloca(p);
    lista[p].inf = x;

    // 1. Noul nod preia legatura nodului 'adr'
    lista[p].urm = lista[adr].urm;

    // 2. Nodul 'adr' se leaga de noul nod
    lista[adr].urm = p;
}
adr: Nodul reper. p: Nodul nou.
Pas Critic: Ordinea operațiilor contează. Întâi legăm p de restul listei, apoi legăm adr de p.
Reper adr Nou Următor

4. Inserare ÎNAINTE (Optimizare)

void inserare_inainte(int adr, int x) {
    int p;
    aloca(p);

    // 1. Copierea datelor (Clonare)
    lista[p] = lista[adr];

    // 2. Suprascrierea nodului curent
    lista[adr].inf = x;

    // 3. Legarea nodului curent de clona
    lista[adr].urm = p;
}
Pentru a insera înainte fără a parcurge lista pentru a găsi precedentul, se folosește un truc logic.
Pasul 1: Se creează un nod nou p după nodul curent adr, care este o copie exactă a lui adr (primește informația veche).
Pasul 2: În nodul curent adr se scrie valoarea nouă x.
VAL. NOUĂ adr (Fizic Neschimbat) VAL. VECHE p (Clona)

5. Ștergere Nod (stergere)

void stergere(int adr) {
    int p, q;
    p = lista[adr].urm;

    // CAZUL 1: Nodul nu e ultimul
    if (p != -1) {
        lista[adr] = lista[p]; // Copiem urmatorul
        elibereaza(p);         // Stergem urmatorul
    }
    // CAZUL 2: Nodul este ultimul
    else {
        q = prim;
        p = lista[q].urm;
        
        // Parcurgere pt penultimul
        while (lista[p].urm != -1) {
            q = p;
            p = lista[p].urm;
        }
        lista[q].urm = -1; // Rupem legatura
        elibereaza(p);
    }
}
Cazul 1 (Interior): Se copiază informația din nodul următor (p) peste nodul curent (adr), apoi se șterge nodul p. O(1).
Cazul 2 (Final): Se parcurge lista pentru a găsi penultimul nod q. Se setează urm-ul lui q la -1.
Cazul 1 (Copiere)
Target (adr) Victima (p)
Cazul 2 (Parcurgere)
Penultim (q) ✂️ Ultimul (p)

Codul Sursă Complet (C++)

#include <iostream>
using namespace std;

#define MAX 100

struct nod {
    int inf;
    int urm;
};

nod lista[MAX];
int s[MAX];
int prim = -1;
int nr = 0;

int exista_spatiu() {
    if (nr < MAX) return 1;
    return 0;
}

void aloca(int &adr) {
    int i = 0;
    while (s[i] == 1 && i < MAX) i++;
    adr = i;
    s[i] = 1;
    nr++;
}

void elibereaza(int adr) {
    s[adr] = 0;
    nr--;
    if (adr == prim) prim = -1;
}

void adauga(int &prim, int x) {
    int p = prim;
    int adr;
    aloca(adr);
    lista[adr].inf = x;
    lista[adr].urm = -1;

    if (prim == -1) prim = adr;
    else {
        while (lista[p].urm != -1)
            p = lista[p].urm;
        lista[p].urm = adr;
    }
}

int cautare(int x) {
    int p = prim;
    while (p != -1 && lista[p].inf != x)
        p = lista[p].urm;
    return p;
}

void inserare_dupa(int adr, int x) {
    int p;
    aloca(p);
    lista[p].inf = x;
    lista[p].urm = lista[adr].urm;
    lista[adr].urm = p;
}

void inserare_inainte(int adr, int x) {
    int p;
    aloca(p);
    lista[p] = lista[adr];
    lista[adr].inf = x;
    lista[adr].urm = p;
}

void stergere(int adr) {
    int q, p = lista[adr].urm;
    if(p != -1) {
        lista[adr] = lista[p];
        elibereaza(p);
    } else {
        q = prim;
        p = lista[q].urm;
        if(p != -1){
            while(lista[p].urm != -1){
                q = p;
                p = lista[p].urm;
            }
            lista[q].urm = -1;
        } else p = prim;
        elibereaza(p);
    }
}

void parcurgere(int prim) {
    int p = prim;
    if (prim == -1) cout << "Lista vida!" << endl;
    else {
        cout << "Elemente: ";
        while (p != -1) {
            cout << lista[p].inf << " ";
            p = lista[p].urm;
        }
        cout << endl;
    }
}

int main() {
    int p, opt, x, y;
    for(int i=0; ido {
        cout << "\n1.Adauga 2.Afiseaza 3.Cauta 4.Ins_Dupa 5.Ins_Inainte 6.Sterge 7.Exit\nOpt: ";
        cin >> opt;
        switch(opt) {
            case 1: 
                cin >> x; 
                if(exista_spatiu()) adauga(prim, x); 
                break;
            case 2: parcurgere(prim); break;
            case 3: 
                cin >> x; p = cautare(x); 
                if(p!=-1) cout << "Gasit: " << p; 
                break;
            case 4:
                cin >> x; p = cautare(x);
                if(p!=-1) { cin >> y; inserare_dupa(p, y); }
                break;
            case 5:
                cin >> x; p = cautare(x);
                if(p!=-1) { cin >> y; inserare_inainte(p, y); }
                break;
            case 6:
                cin >> x; p = cautare(x);
                if(p!=-1) stergere(p);
                break;
        }
    } while (opt != 7);
    return 0;
}