SDA

• Structuri de date


  Un mod de organizare a datelor în memorie pentru accesul eficient la date
• Structuri de date abstracte


  O descriere logică a unui mod de organizare a datelor împreună cu operațiile specifice asociate
• ADT colecție


  Un grup de elemente de același tip în care pot exista duplicate
• ADT mulțime


  O colecție ce nu conține duplicate
• Operații de bază asupra unei colecții


  • Constructori (inițializare, adăugare, eliminare, reuniune, intersecție, diferență)
  • Operații de caracterizare (vid, cardinal, aparține, identice, include)
• Implementare ADT mulțime


  1. Vector alocat static

  2. Vector alocat dinamic

  3. Listă înlănțuită
• Căutare secvențială


  Căutare în colecții/mulțimi nesortate, cu oprire la sfârșitul colecției sau îndeplinirea criteriului
• Căutare secvențială sortată


  Căutare în colecții/mulțimi sortate, cu oprire la sfârșitul colecției sau întâlnire cu succesorul
• Adăugare element


  1. Adăugare la sfârșit pentru elemente nesortate

  2. Inserare în interiorul vectorului pentru elemente sortate
• Eliminare element


  1. Înlocuire prin ultimul element pentru elemente nesortate

  2. Deplasare spre stânga a succesorilor pentru elemente sortate
• Noțiuni elementare de analiza algoritmilor


  • Eficiența algoritmilor
  • Cazul mediu
  • Cazul cel mai defavorabil
  • Funcții de creștere (constante, logaritmice, liniare, N*logN, pătratice, cubice, exponențiale)
  • Timp de rulare
• Funcții de creștere


  • 1. Cele mai multe instrucțiuni sunt executate o dată sau numai de câteva ori – timp constant
  • 2. logN – probleme descompuse în subprobleme – timp logaritmic
  • 3. N - O prelucrare se efectuează pe fiecare element de intrare – timp liniar
  • 4. N*logN – algoritmul rezolvă problema prin descompunere în subprobleme, rezolvă subproblemele și combină apoi intrarea
  • 5. N2 – algoritmul prelucrează toate perechile formate cu datele de intrare – timp cuadratic
  • 6. N3 - algoritmul prelucrează toate tripletele formate cu datele de intrare – timp cubic
  • 7. 2N – timp exponențial
• Timp de rulare


  Timpul de rulare a unui algoritm va fi de obicei una din aceste funcții înmulțită cu o constantă plus o altă constantă
• Notația Big-Oh (O mare)


  O funcție g(N) se spune că este de ordinul O(f(N)) dacă există constantele c0 și N0 astfel încât g(N) < c0*f(N) pentru ∀N > N0
• Algoritm Cautare_Secventiala


  1. Examinează N numere pentru căutarea fără succes (worst case) și aproximativ N/2 numere pentru căutarea cu succes (average case)

  2. O(N)
• Algoritm Cautare_Binara


  1. Nu examinează mai mult de logN+1 numere (worst case)

  2. O(logN)
• Algoritm Sortare Bubble


  O(N2) cazul mediu și cel mai defavorabil
• Algoritm sortare Quicksort


  1. O(N2) cazul cel mai defavorabil

  2. O(NlogN) cazul mediu
• Liste înlănțuite


  O serie de obiecte ordonate, o mulțime de elemente în care fiecare element face parte dintr-un nod care conține și un link la un alt nod sau vid

  
• Elementele liste: celule, noduri
• Alocarea memoriei pentru liste se face la nivelul fiecarui nod, numai cand avem nevoie de un nou nod (un nou element)
• Alocarea este dinamica (se realizeaza in heap)
• Vectori vs. Liste înlănțuite

  • Vectori: necesita estimarea nr elem, cautarea unui element se face direct, prin index, inserarea si eliminarea unui element gasit se face in O(N), compacte in memorie
  • Liste inlantuite: nu necesita sa stim nr elem, trebuie sa parcurgem toate elementele pana la elementul cautat, inserarea si eliminarea unui element gasit se face in O(1), nu sunt compacte in memorie, au nevoi de spatiu suplim pt legaturi
• Reprezentare (R1)


  typedef int Item; typedef struct cel { Item elem; struct cel *next;} ListCel, *TList;
• Reprezentare (R2)


  typedef struct node *Link; typedef struct node { Item elem; Link next; } ListNode;
• Adresari de baza in liste


  TList p = NULL; test lista vida: (p == NULL); pentru lista nevida (p != NULL): valoarea primului element, adresa primului element, adresa urmatoarei liste (celule), test continuare lista, valoarea urmatorului element, avans la urmatoarea lista (celula)
• Operatii de baza cu liste


  • Testare lista vida
  • Parcurgere lista (afisare ordine directa, ordine inversa)
  • Creare lista
  • Lungime lista (numar de elemente)
  • Cautare un element in lista
  • Inserare un element in lista (la inceput, la sfarsit, dupa un anumit element, in lista ordonata)
  • Eliminare element (de la inceput, de la sfarsit, un element gasit)
  • Distrugere lista (eliminarea tututor elementelor)
• Creare lista


  Initializeaza lista la lista vida, aloca memorie pentru un nou nod, depune datele in nod, actualizeaza legatura din nod la head, head = t
• Cautare element x in lista


  Parcurge lista pana la elementul cautat sau pana la sfarsitul listei
• Inserare element d in lista


  Inserare la inceputul listei, la sfarsitul listei, dupa un anumit element, intr-o lista ordonata
• Eliminare prim element din lista


  Salveaza adresa celulei, actualizeaza head la urmatorul element, elibereaza memoria celulei
• Inserare element in d lista

  1. Aloca in t memorie pentru un nou nod

  2. Depune d in nodul referit de t (t->elem=d)

  3. Localizeaza adresa elementului x

  4. Daca elementul x exista in lista atunci actualizeaza legatura din t la nodul ce urmeaza lui x (t->next = x->next)

  5. Actualizeaza legatura din x la t (x->next = t)
• Inserare element intr-o lista ordonata head

  Insereaza elementul in lista pastrand ordinea crescatoare
• Eliminare prim element din lista head

  1. Daca head == NULL atunci intoarce esec

  2. Salveaza adresa celulei de eliminat in t

  3. Modifica adresa inceput lista (head = head->next)

  4. Elibereaza spatiul ocupat de celula eliminata (free(t))

  5. Intoarce succes
• Eliminare unui element d din lista head


  1. Daca head == NULL atunci intoarce esec

  2. Localizeaza adresa x a elementului predecesor lui d

  3. Daca d nu exista in lista atunci intoarce esec

  4. Salveaza adresa celulei de eliminat in t

  5. Elimina celula (x->next = x->next->next)

  6. Elibereaza spatiul ocupat de celula eliminata (free(t))

  7. Intoarce succes
• Inversarea unei liste


  Parcurge lista si insereaza fiecare element la inceputul unei noi liste
• Lista circulara nu va fi vida niciodata
• Parcurgere lista circulara


  t = head; do { ... t = t->next; } while (t != head)
• Problema Iosefiana (Josephus problem) - Un numar de N persoane se aseaza intr-un cerc. Se elimina repetitiv persoana de pe pozitia M pana ramane o singura persoana. Acea persoana este aleasa leader
• Implementare Problema Iosefiana folosind lista circulara


  1. Creare lista circulara

  2. Eliminare element din lista circulara