Structuri de Date 2023 - C2: Liste, Stive, Cozi

Structuri de Date

Curs 2: Liste, Stive si Cozi

Cuprins:

Structuri liniare
Liste alocate secvential
Stiva
Coada
Liste alocate dinamic
Inserare la inceput
Inserare la final
Stergere
Alte tipuri de liste
Skip lists

1. Structuri liniare

Relatie de ordine totala pe multimea elementelor
Fiecare element are un singur element precedent (prev) si un singur element succesor (next).
Exemple de structuri liniare

liste
stive
cozi

Exemple de structuri neliniare

arbori
grafuri

Clasificare

Dupa localizarea elementelor:

• succesorul unui element e in zona imediat alaturata (liste secventiale = array)

• orice element retine si adresa succesorului (liste înlantuite).

Dupa modul de efectuare al operatiilor de intrare (inserarile) si de iesire (stergerile):

• Structuri liniare fara restrictii de intrare/iesire

• Structuri liniare cu restrictii de intrare/iesire (stive si cozi)

Operatii

Traversarea - operatia care acceseaza fiecare element al structurii, o singura data, in vederea procesarii (vizitarea elementului).
Cautarea - se cauta un element cu cheie data in structura (cu sau fara succes) : consta dintr-o traversare - eventual incompleta a structurii, in care vizitarea revine la comparatia cu elementul cautat.
Inserarea - adaugarea unui nou element, cu pastrarea proprietatilor structurii.
Stergerea - extragerea unui element al structurii (eventual in vederea unei procesari), cu pastrarea proprietatilor structurii pe elementele ramase.

2. Liste alocate secvential (cu array)

Operatii:

insertie pe pozitii arbitrare
stergere de la pozitii arbitrare

Date de acelasi tip stocate in locatii de memorie contigue in ordinea indicilor (Nodurile se afla in pozitii succesive de memorie)
Avantaj: acces direct la orice nod
Dezavantaj: multe deplasari la operatiile de inserare si stergere

#include <iostream>using namespace std;
class arrayStruct{    int *a;    int n;    int maxsize=128;
    public:    arrayStruct(int siz, int arr[]){        n=siz;        a=new int[maxsize];        for (int i=0;i<siz;i++)            a[i]=arr[i];    }
    void af(){        for (int i = 0; i<n; i++)            cout<<a[i]<<" ";        cout<<endl;    }
    int search(int x){        for (int i = 0; i<n; i++)            if (a[i]==x)                return i; //gasit        //cautare fara succes        return -1;    }
    void insert(int x, int poz){        for (int i = n-1; i >= poz; i--)            a[i+1] = a[i];        a[poz] = x;        n++;        //daca vrem sa fie si dinamic        if (n==maxsize){            maxsize*=2;            int* aaa=new int[maxsize];            for (int i=0;i<n;i++)                aaa[i]=a[i];            delete[] a;            a=aaa;        }     }
    void remove(int poz){        for (int i = poz; i<n-1; i++)            a[i] = a[i+1];        n--;    }};
int main(){    int vec[]={1,2,3,4,5};    arrayStruct A(5,vec);    A.af();    A.insert(123,2);    A.af();    return 0;}

3. Stiva

Operatii:

push = insertie
pop = extragerea celui mai nou element inserat

struct stiva_cu_vector{ int elemente[200]; int varf=0; void push(int x){ if (varf==200) {cout<<"OVERFLOW"; return;} elemente[varf]=x; varf++; } int pop(){ if (varf==0) {cout<<"UNDERFLOW"; return -1;} varf--; return elemente[varf]; } void afisare(){ int i; cout<<"[BAZA> "; for(i=0;i<varf;i++) cout<<elemente[i]; cout<<" [VARF>"<<endl; }};

4. Coada

Operatii:

enqueue = insertie
dequeue = extragerea celui mai vechi element inserat

5. Liste alocate dinamic

Operatii:

insertie la inceput/final/pe pozitii arbitrare
stergere de la inceput/final/pozitii arbitrare

Pointerul prim retine adresa primului nod din lista, iar ultim retine adresa sfarsitului listei;

Fiecare nod conţine:

un câmp de date notat info, pe care se reprezintă un element al mulţimii;
un pointer către nodul următor, notat next.

Datele (info) pot fi:

de tip simplu (int, float etc.)
multiple tipuri simple (de exemplu punem doua campuri int pentru a implementa o lista de perechi de intregi)
alti pointeri (la vectori, la siruri de caractere sau la alte obiecte)

struct nod{ int info; nod* next;};struct lista{ nod* primul_element;//pointer la primul element nod* ultimul_element;//pointer la ultimul element lista(){ primul_element=NULL;//initializare ultimul_element=NULL;//initializare } void insert_la_inceput(int x); void insert_la_final(int x); void afisare(){ nod* pointer; for (pointer = primul_element; pointer !=NULL;pointer = pointer->next) cout<<pointer->info<< " -> "; cout<<endl; }};
int main(){ lista L; L.insert_la_inceput(1); L.afisare(); L.insert_la_inceput(2); L.afisare(); L.insert_la_inceput(3); L.afisare(); return 0;}

Lista in memorie

6. Inserarea la inceput

void insert_la_inceput(int x){ nod* nou = new nod;//alocam spatiu nou->info =x;//punem x in campul intreg nou->next = primul_element; // punem adresa din primul_element in campul adresa next // legam nou de primul_element primul_element = nou; // actualizam care este adresa noului nod de la inceput if (ultimul_element==NULL) // daca lista era goala -> acum extista 1 nod ultimul_element=nou; //ultimul_element trebuie sa-l indice pe acel nod }

7. Inserarea la final

void insert_la_final(int x){ nod* nou = new nod; //alocam nou->info =x; //info nou->next = NULL; //punem NULL in adresa pentru ca acest nod va fi ultimul if (ultimul_element==NULL) //daca lista era vida primul_element=ultimul_element=nou; //atunci ambii pointeri indica noul nod else{ ultimul_element->next=nou; //legam ultimul de nou ultimul_element=nou; //ultimul nod trebuie actualizat, stocam adresa lui in ultimul_element } }

8. Stergerea

//implementare exercitiu//caz 1 -> sterg element din mijloc, exista vecin in stanga, exista vecin in dreapta//caz 2 -> sterg primul element, NU exista vecin in stanga, exista vecin in dreapta//caz 2.1 -> sterg primul element, NU exista vecin in stanga, NU exista vecin in dreapta,//deci era singurul element, trebuie updatat si prim si ultim = NULL//caz 3 -> sterg ultimul element, exista vecin in stanga, NU exista vecin in dreapta

9. Alte tipuri de liste

liste circulare (ultimul element este legat de primul)
liste dublu inlantuite (au pointer si catre elementul anterior, memoria suplimentara folosita pentru retinerea pointerului de dinainte micsoreaza timpul necesar parcurgerii/prelucrarii listei in sens invers)
liste circulare cu nod marcaj (lista vida contine un singur element alocat, a carei informatie nu se utilizeaza, adresa lui se foloseste la parcurgere -> incepem din dreapta lui si cand il intalnim din nou inseamna ca a fost parcursa lista)
liste de liste (se pot utiliza pentru matrici rare, alocam noduri doar pentru elementele nonzero ale matricii, daca exista o lista de tip coloana, aceasta memoreaza indicii liniilor si cate un pointer pentru fiecare lista-linie, ale carei elemente contin indicii de coloana, valoarea nonzero si pointer catre urmatorul element lista-linie)

10. Skip list (link)

Structura probabilista, sortata:

Avem un numar de benzi express cu mai putine elemente:

cand dorim sa inseram, stergem sau updatam un element: cautam pozitia lui pornind cu benzile express cele mai rare.
cand il inseram in lista are 50% sanse sa fie inserat in banda express superioara. Pentru fiecare succes, are din nou 50% sanse sa fie inserat in banda express superioara.

Insertia elementelor: