SDA Lucrarea 3

În acest laborator se vor implementa secvențe cu vectori și liste simplu și dublu înlănțuite.

Secvența (lista abstractă - List)

Secvența este o structură de date abstractă care stochează datele sub forma unui șir de elemente de același fel.

Secvența are următoarele proprietăți:

1. Datele sunt stocate într-o anumită ordine (se poate spune că un element este plasat înaintea sau după un alt element în structură).
2. Numărul de elemente ce poate fi stocat de structură este nelimitat (a nu se confunda cu infinit, există întotdeauna limita dată de memoria disponibilă).
3. Elementele stocate în secvență sunt de același fel.

Secvența suportă următoarele operații de bază:

1. Interogarea numărului de elemente din secvență.
2. Inserția unui element pe o anumită poziție în secvență.
3. Ștergerea unui element de pe o anumită poziție din secvență.
4. Căutarea unui element în secvență (căutare care va întoarce indexul pe care apare elementul în strucutră).
5. Accesarea unui element de pe o anumită poziție.
6. Dacă există o relație de ordine pe mulțimea din care fac parte elementele, se poate defini operația de sortare a secevenței care implică mutarea elementelor pe alte poziții, astfel încât un element considerat mai mic după relația de ordine folosită să fie plasat înaintea oricărui element considerat mai mare.

Implementarea secvenței cu vectori

În cazul implementării cu vectori, elementele sunt plasate într-un vector de dimensiune fixă și cunoscută. Din cauza faptului că secvența are dimensiune nelimitată, se cere ca vectorii să suporte redimensionarea dinamică a acestora pentru a acomoda elemente suplimentare în momentul când se umplu. Astfel, suntem obligați ca pentru implementarea secvențelor să folosim alocare dinamică de memorie, iar tipul de date care poate fi folosit pentru stocarea adreselor alocate este pointerul. Totuși cunoaștem din lecțiile anterioare faptul că o variabilă de tip pointer nu memorează decât o adresă de start a zonei de memorie alocată, nu și dimensiunea ei. Prin urmare vom defini o structură numită ArrayList care va stoca adresa de start dar și dimensiunea zonei alocate. Mai jos este un exemplu de secvență de valori întregi pe 16 biți:

struct ArrayList {
    short * array;     // pointer la zona de memorie alocată
    unsigned capacity; // dimensiunea zonei alocate
};

În plus față de câmpurile de mai sus, structura ArrayList trebuie să memoreze și numărul de elemente valide din secvență. Motivul fiind acela că inițial, chiar dacă vectorul este alocat și are o capacitate ne-nulă, el nu conține de fapt nici un element. Astfel introducem un nou câmp: size, care reprezintă numărul de elemente din secvență, și care este inițial 0:

struct ArrayList {
    short * array;     // pointer la zona de memorie alocată
    unsigned capacity; // dimensiunea zonei alocate
    unsigned size;     // numarul de elemente valide din secventa
};

Crearea unui ArrayList

Pentru crearea unei secvențe noi, se definește următoarea funcție:

/**
 * Functia aloca memorie si creeaza un nou ArrayList cu o capacitate initiala.
 * @param initialCapacity capacitatea initiala a secventei.
 * @return pointer la o structura de tip ArrayList. 
 */
struct ArrayList * createArrayList(unsigned initialCapacity);

Implementarea acestei funcții se face folosind următorul algoritm:

1. Se alocă memorie pentru o variabilă de tip struct ArrayList.
2. Se inițializează capacity cu valoarea din initialCapacity.
3. Se inițializează size cu 0.
4. Se alocă memorie pentru un vector de initialCapacity elemente iar adresa alocată se memorează în array.
5. Se întoarce adresa variabilei de tip struct ArrayList.

Inserția

Pentru inserția unui element value pe o anumită poziție index se definește următoarea funcție:

/**
 * Functia inseareaza elementul value pe pozitia index in vector. Daca capacitatea este insuficienta
 *  se face realocare. Se afiseaza un mesaj de eroare daca index-ul este mai mare decat size.
 * @param list lista in care se face insertia.
 * @param index index-ul pe care se va face insertia
 * @param value valoarea ce trebuie inserata
 */
void arrayListInsert(struct ArrayList * list, unsigned index, short value);

Inserția unui element value pe o anumită poziție index într-o secvență implementată cu vectori, se face urmând următorul algoritm:

1. Dacă index este mai mare decat size, se afișează un mesaj de eroare și funcția se încheie.
2. Dacă size este egal cu capacity, se face realocare de memorie alocând un vector nou de 2 * capacity elemente. Acest lucru se realizează folosind funcția realloc.
3. Lui capacity i se atribuie valoarea 2 * capacity.
4. Se folosește funcția memmove pentru a muta elementele de la poziția index la size - 1 cu un element mai la dreapta.
5. Se atribuie elementului de pe poziția index din vector valoarea value.
6. size se incrementează cu 1.

Implementarea secvenței cu liste simplu și dublu înlănțuite

În curând...