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ă - Sequence)

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 primul index pe care apare elementul în structură).
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

Clasa din STL care implementează secvențe folosind array-uri cu redimensionare dinamică se numește std::vector. Această clasă este un template care poate fi folosit pentru stocarea de elemente de diferite tipuri.

Crearea unui std::vector

Pentru crearea unei vector nou se pot utiliza doi constructori:

/**
 * Constructorul aloca memorie si creeaza un nou vector cu o capacitate initiala nulă.
 */
vector();

/**
 * Constructorul aloca memorie si creeaza un nou vector cu o dimensiune si o capacitate initiala.
 * Vectorul va avea "initialSize" elemente neutre (0 pentru valori numerice).
 * @param initialSize dimensiunea initiala a secventei.
 */
vector(uint32_t initialSize);

Exemplu:

#include <vector>

using namespace std;

int main() {
    vector<int> intVector;   // Foloseste primul constructor, dimensiune 0
    /* intVector[0] = 0; */  // Aici s-ar genera un Segmentation Fault pentru ca nu exista alocata memorie pentru un element (dimensiune si capacitate 0).
    intVector.push_back(10); // Aceasta linie functioneaza, pentru ca push_back adauga la sfarsitul vectorului, determinand redimensionarea acestuia.
    
    vector<float> floatVector(10); // Foloseste al doilea constructor, dimensiunea initiala e 10.
    floatVector[0] = 1;            // Linia NU genereaza un SegFault pentru ca exista capacitatea necesata pentru stocarea valorii.
     
    return 0;
}

Interogarea dimensiunii

Pentru interogarea dimensiunii, se definește următoarea metodă:

/**
 * Metoda intoarce numarul de elemente valide din vector.
 * @return numarul de elemente valide din vector.
 */
uint32_t size();

Exemplu:

#include <vector>
#include <cstdio>

using namespace std;

int main() {
    vector<int> intVector;
    intVector.push_back(10);
    intVector.push_back(20);
    intVector.push_back(5);    

    printf("Vectorul are %u elemente!\n", intVector.size()); // Programul va afisa valoarea 3.

    return 0;
}

Inserția

Pentru inserția unui element value pe o anumită poziție index se definesc funcțiile de mai jos. Se observă că aceste funcții fac uz de iteratori. Acești iteratori sunt niște pointeri cu informații suplimentare. Există doi iteratori disponibili pentru orice vector: begin() și end(). Primul reprezintă adresa primului element din vector, iar al doilea reprezintă adresa DE DUPĂ ultimul element din vector.

/**
 * Metoda insereaza elementul value pe pozitia position in vector. Daca capacitatea este insuficienta
 *  se face realocare.
 * @param position pozitia pe care se va face insertia
 * @param value valoarea ce trebuie inserata
 * @return metoda intoarce un iterator la elementul inserat
 */
iterator insert(iterator position, T value);

/**
 * Metoda insereaza count elemente cu valoarea value pe pozitia position in vector. Daca capacitatea este insuficienta
 *  se face realocare.
 * @param position pozitia pe care se va face insertia
 * @param count numarul de elemente ce trebuie introduse
 * @param value valoarea ce trebuie inserata
 * @return metoda intoarce un iterator la primul element inserat
 */
iterator insert(iterator position, uint32_t count, T value);

/**
 * Metoda insereaza toate elementele dintre iteratorii first inclusiv si last exclusiv pe pozitia position in vector.
 *  Daca capacitatea este insuficienta se face realocare.
 * @param position pozitia pe care se va face insertia
 * @param first iteratorul de start
 * @param last iteratorul de final
 * @return metoda intoarce un iterator la primul element inserat
 */
iterator insert(iterator position, iterator first, iterator last);

/**
 * Metoda adauga un element la sfarsitul vectorului. Daca capacitatea este insuficienta se face realocare.
 * @param value valoarea ce trebuie inserata
 */
void push_back (T value);

Exemplu:

#include <vector>
#include <cstdio>

using namespace std;

int main() {
    vector<int> intVector;
    intVector.push_back(1);
    intVector.push_back(2);
    intVector.push_back(3);    

    // vectorul acum e: {1, 2, 3}

    intVector.insert(intVector.begin(), 0); // se insereaza inaintea primului element din vector o valoare de 0

    // vectorul acum e: {0, 1, 2, 3}

    intVector.insert(intVector.begin() + 1, 3); // se insereaza inaintea celui de-al doilea element din vector o valoare de 3

    // vectorul acum e: {0, 3, 1, 2, 3}

    intVector.insert(intVector.end(), 10); // se insereaza dupa ultimul element din vector, o valoare de 10 (echivalent cu push_back)

    // vectorul e acum: {0, 3, 1, 2, 3, 10}

    vector<int> newVector;
    newVector.push_back(-1);
    newVector.push_back(-2);
    newVector.push_back(-3);

    // newVector e acum: {-1, -2, -3}

    intVector.insert(intVector.begin(), newVector.begin(), newVector.end()); //Se insereaza inaintea primului element din intVector toate elementele din newVector

    // intVector e acum: {-1, -2, -3, 0, 3, 1, 2, 3, 10}

    return 0;
}

Ștergerea

Pentru ștergerea unui element de pe o anumită poziție index se definește următoarea funcție:

/**
 * Metoda sterge elementul pe pozitia index in vector. Se afiseaza un mesaj de eroare
 *  daca indexul este mai mare decat (size - 1).
 * @param index indexul de la care se va face stergerea
 */
void erase(uint32_t index);

Ștergerea unui element de pe o anumită poziție index dintr-o secvență implementată cu vectori, se face urmând următorul algoritm:

1. Dacă index este mai mare decat count - 1, se afișează un mesaj de eroare și funcția se încheie.
2. Se folosește funcția memmove pentru a muta elementele de la poziția index + 1 la count - 1 cu un element mai la stânga.
3. count se decrementează cu 1.

Căutarea

Pentru căutarea unui element value într-o secvență neordonată se definește următoarea funcție:

/**
 * Metoda cauta elementul value in vector si intoarce prima pozitie pe care apare.
 *  Se intoarce -1 daca valoarea nu exista in vector.
 * @param list lista in care se face cautarea.
 * @param value valoarea care se cauta.
 * @return indexul la care apare valoarea sau -1 daca nu exista in vector.
 */
int arrayListSearch(struct ArrayList * list, short value);

Căutarea unui element value într-o secvență neordonată implementată cu vectori, se face urmând următorul algoritm:

1. Se iterează cu o variabilă i de la 0 la size - 1.
2. Dacă elementul de pe poziția i din vector este egal cu value, se întoarce valoarea lui i.
3. Se întoarce valoarea -1.

Accesarea elementului de pe o anumită poziție

Pentru accesarea unui element de pe poziția index dintr-o secvență se definește următoarea funcție:

/**
 * Functia intoarce elementul din vector de pe poziția index. Daca index este mai mare decat (size - 1) se afiseaza
 *   un mesaj de eroare (si se întoarce 0).
 * @param list lista in care se face accesul.
 * @param index pozitia de la care se doreste citirea elementului. 
 * @return valoarea de la pozitia index sau 0 daca index este mai mare decat (size - 1)
 */
short arrayListGet(struct ArrayList * list, unsigned index);

Accesarea unui element de pe poziția index dintr-o secvență neordonată implementată cu vectori, se face urmând următorul algoritm:

1. Dacă index este mai mare decât (size - 1) se afișează un mesaj de eroare și se întoarce 0.
2. Se întoarce valoarea de la indexul index din vector.

Sortarea unei secvențe implementate cu vectori - Bubble Sort

Pentru sortarea unei secvențe se definește următoarea funcție:

/**
 * Functia sorteaza crescator elementele din secventa list folosind algoritmul Bubble Sort. 
 * @param list lista care se doreste sortata.
 */
void arrayListBubbleSort(struct ArrayList * list);

Sortarea unei secvențe implementată cu vectori se face urmând următorul algoritm:

1. Se declară o variabilă done.
2. Se atribuie lui done valoarea 1.
3. Se iterează cu un contor i de la 0 la (size - 2)
4. Dacă elementul de pe poziția i din vector este mai mare decât elementul de pe poziția (i + 1), acestea se interschimbă și lui done i se atribuie valoarea 0.
5. După terminarea iterării peste vector, dacă done e 0, se sare la pasul 2 (se folosește o buclă do-while).

Căutarea într-o secvență sortată implementată cu vectori - Binary Search

Căutarea într-o secvență ordonată se poate realiza mai eficient decât iterând peste toate elementele cu o buclă în O(n), deoarece avem informații suplimentare legate de poziția cea mai probabilă a elementului căutat.

Algoritmul numit Binary Search, care face parte din clasa Divide-et-impera, funcționează căutând elementul la mijlocul intervalului în care se realizează căutare, și în funcție de rezultat întorcând poziția sau eliminând în întregime jumătate din interval.

Pentru căutarea unei valori value într-o secvență sortată implementată cu vectori, se definește următoarea funcție:

/**
 * Functia cauta elementul value in secventa list sortata crescator. 
 *    Daca secventa nu este sortata, comportamentul nu este definit.
 * @param list lista in care se cauta.
 * @param value valoarea cautata in secventa.
 * @return indexul unde s-a găsit valoarea value sau -1 daca valoarea nu exista.
 */
int arrayListBinarySearch(struct ArrayList * list, short value);

Căutarea unei valori value într-o secvență sortată implementată cu vectori se face urmând următorul algoritm:

1. Se inițializează o variabilă start cu valoarea 0 și o varibilă end cu valoarea (size - 1).
2. Cât timp start este mai mic sau egal decât end se realizează următoarele operații:
3. Se declară o variabilă middle și i se atribuie valoarea (start + end ) / 2.
4. Dacă elementul din vector de pe poziția middle este egal cu value, se întoarce valoarea middle.
5. Dacă elementul din vector de pe poziția middle este mai mare decât value, end va lua valoarea middle - 1 altfel,
6. Dacă elementul din vector de pe poziția middle este mai mic decât value, start va lua valoarea middle + 1.
7. Se sare la punctul 3.
8. Aici se ajunge dacă start devine mai mare decât end, în care situație se întoarce -1.

Atenție: Acest algoritm nu va întoarce întotdeauna prima apariție a elementului value din vector. De ce? Ce soluție propuneți pentru a rezolva această problemă?

Ștergerea unui ArrayList

Pentru ștergerea unui ArrayList se definește următoarea funcție.

/**
 * Functia dezalocă memoria folosită de lista specificată.
 * @param list lista care trebuie ștearsă.
 */
void deleteArrayList(struct ArrayList * list);

Ștergerea unui ArrayList se realizează în doi pași:

1. Se dezalocă memoria alocată pentru vector.
2. Se dezalocă memoria alocată pentru structura de tip struct ArrayList.

Exerciții

Săptămâna 1

1. Se dă următorul header file arrayList.h:

   #ifndef ARRAY_LIST_H
   #define ARRAY_LIST_H
   
   struct ArrayList {
       short * array;     // pointer la zona de memorie alocată
       unsigned capacity; // dimensiunea zonei alocate
       unsigned size;     // numarul de elemente valide din secventa
   };
   
   /**
    * 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);
   
   /**
    * Functia intoarce numarul de elemente valide din lista specificata.
    * @param list lista pentru care se cere dimensinea.
    * @return numarul de elemente valide din lista list.
    */
   unsigned arrayListSize(struct ArrayList * list);
   
   /**
    * Functia inseareaza elementul value pe pozitia index in vector. Daca capacitatea este insuficienta
    *  se face realocare. Se afiseaza un mesaj de eroare daca indexul este mai mare decat size.
    * @param list lista in care se face insertia.
    * @param index indexul pe care se va face insertia
    * @param value valoarea ce trebuie inserata
    */
   void arrayListInsert(struct ArrayList * list, unsigned index, short value);
   
   /**
    * Functia sterge elementul pe pozitia index in vector. Se afiseaza un mesaj de eroare
    *  daca indexul este mai mare decat (size - 1).
    * @param list lista din care se face stergerea.
    * @param index indexul de la care se va face stergerea
    */
   void arrayListDelete(struct ArrayList * list, unsigned index);
   
   /**
    * Functia cauta elementul value in vector si intoarce prima pozitie pe care apare.
    *  Se intoarce -1 daca valoarea nu exista in vector.
    * @param list lista in care se face cautarea.
    * @param value valoarea care se cauta.
    * @return indexul la care apare valoarea sau -1 daca nu exista in vector.
    */
   int arrayListSearch(struct ArrayList * list, short value);
   
   /**
    * Functia intoarce elementul din vector de pe poziția index. Daca index este mai mare decat (size - 1) se afiseaza
    *   un mesaj de eroare (si se întoarce 0).
    * @param list lista in care se face accesul.
    * @param index pozitia de la care se doreste citirea elementului. 
    * @return valoarea de la pozitia index sau 0 daca index este mai mare decat (size - 1)
    */
   short arrayListGet(struct ArrayList * list, unsigned index);
   
   /**
    * Functia sorteaza crescator elementele din secventa list folosind algoritmul Bubble Sort. 
    * @param list lista care se doreste sortata.
    */
   void arrayListBubbleSort(struct ArrayList * list);
   
   /**
    * Functia cauta elementul value in secventa list sortata crescator. 
    *    Daca secventa nu este sortata, comportamentul nu este definit.
    * @param list lista in care se cauta.
    * @param value valoarea cautata in secventa.
    * @return indexul unde s-a găsit valoarea value sau -1 daca valoarea nu exista.
    */
   int arrayListBinarySearch(struct ArrayList * list, short value);
   
   /**
    * Functia dezalocă memoria folosită de lista specificată.
    * @param list lista care trebuie ștearsă.
    */
   void deleteArrayList(struct ArrayList * list);
   
   #endif
   

   Implementați într-un fișier sursă C funcțiile definite în header.

2. Folosind structura și funcțiile definite în header, scrieți un program simplu care să efectueze următoarele operații:
   • definiți un ArrayList de capacitatea initiala 3.
   • adăugați 7 elemente: 6, 10, 0, -5, 4, 16, 20 (utilizați arrayListInsert cu indexul 0 de fiecare dată).
   • căutați valoarea 4 și afișați indexul pe care apare.
   • inserați valoarea 9 la indexul 5.
   • afișați valoarea de la indexul 5.
   • sortați vectorul.
   • căutați valoarea 16 și afișați indexul la care apare.
   • afișați conținutul secvenței.
   • ștergeți secvența.

Săptămâna 2

1. Se dă următorul header file linkedList.h:

   #ifndef LINKED_LIST_H
   #define LINKED_LIST_H
   
   struct ListNode {
       double value;
       struct ListNode * next;
   };
   
   struct LinkedList {
       struct ListNode * firstNode;
       struct ListNode * lastNode;
       unsigned size;
   };
   
   /**
    * Functia aloca memorie si creeaza un nou LinkedList.
    * @return pointer la o structura de tip LinkedList. 
    */
   struct LinkedList * createLinkedList();
   
   /**
    * Functia intoarce numarul de elemente valide din lista specificata.
    * @param list lista pentru care se cere dimensinea.
    * @return numarul de elemente valide din lista list.
    */
   unsigned linkedListSize(struct LinkedList * list);
   
   /**
    * Functia insereaza elementul value pe pozitia index in lista. Se afiseaza un 
    *  mesaj de eroare daca indexul este mai mare decat size.
    * @param list lista in care se face insertia.
    * @param index indexul pe care se va face insertia
    * @param value valoarea ce trebuie inserata
    */
   void linkedListInsert(struct LinkedList * list, unsigned index, double value);
   
   /**
    * Functia sterge elementul de pe pozitia index din lista. Se afiseaza un mesaj de eroare
    *  daca indexul este mai mare sau egal decat size.
    * @param list lista din care se face stergerea.
    * @param index indexul de la care se va face stergerea
    */
   void linkedListDelete(struct LinkedList * list, unsigned index);
   
   /**
    * Functia cauta elementul value in lista si intoarce prima pozitie pe care apare.
    *  Se intoarce -1 daca valoarea nu exista in lista.
    * @param list lista in care se face cautarea.
    * @param value valoarea care se cauta.
    * @return indexul la care apare valoarea sau -1 daca nu exista in lista.
    */
   int linkedListSearch(struct LinkedList * list, double value);
   
   /**
    * Functia intoarce elementul din lista de pe poziția index. Daca index este mai 
    *  mare sau egal decat size se afiseaza un mesaj de eroare (si se întoarce 0).
    * @param list lista in care se face accesul.
    * @param index pozitia de la care se doreste citirea elementului. 
    * @return valoarea de la pozitia index sau 0 daca index este mai mare sau egal decat size
    */
   double linkedListGet(struct LinkedList * list, unsigned index);
   
   /**
    * Functia sorteaza crescator elementele din secventa list folosind algoritmul Bubble Sort. 
    * @param list lista care se doreste sortata.
    */
   void linkedListBubbleSort(struct LinkedList * list);
   
   /**
    * Functia dezalocă memoria folosită de lista specificată.
    * @param list lista care trebuie ștearsă.
    */
   void deleteLinkedList(struct LinkedList * list);
   
   #endif
   

   Implementați într-un fișier sursă C funcțiile definite în header.

2. Folosind structura și funcțiile definite în header, scrieți un program simplu care să efectueze următoarele operații:
   • definiți un LinkedList.
   • adăugați 7 elemente: 6, 10, 0, -5, 4, 16, 20 (utilizați linkedListInsert cu indexul 0 de fiecare dată).
   • căutați valoarea 4 și afișați indexul pe care apare.
   • inserați valoarea 9 la indexul 5.
   • afișați valoarea de la indexul 5.
   • sortați vectorul.
   • căutați valoarea 16 și afișați indexul la care apare.
   • afișați conținutul secvenței.
   • ștergeți secvența.