Stiva (Stack)
Coada (Queue)
Lista Inlatuita (Linked List)
Tablou De Dispersie (Hashtable)
Cautare Binara (Binary Search)
Arbore Binar De Cautare (Binary Search Tree)
Grafuri (Graphs)
Importanta complexitati algoritmilor este data de faptul ca ne zice daca codul se scaleaza. Majoritatea structurilor de date si a algoritmilor fundamentali sunt deja implementati in .NET Framework, e important sa stim cum functioneaza aceste structuri de date si ce complexitate de timp, memorie au la operatiile de baza: accesare element, cautare element, stergere element, adaugare element.
Ca sa ne facem o idee ce inseamna o complexitate buna si una mai putin buna avem urmatorul grafic:
In .NET Framework avem implementate urmatoarele structuri de date: array, stack, queue, linked list si algoritmi: cautare binara(binary search), restul pe care nu le gasim in .NET Framework se pot gasi in pachete NuGet sau pe GitHub.
Array este una dintre cele mai folosite si cunoscute structuri de date si nu am sa detaliez cu exemple principiul de functionare.
Stiva (Stack)
Stiva (Stack) este o structura de date implementata in .NET Framework sub doua forme, stiva simpla in namespace System.Collections, si stiva ca structura de date generica in namespace System.Collections.Generic, principiul de functionare a structuri stack este LIFO(last in first out), ultimul element intrat primul iesit.
Exemplu de folosire stiva simpla din namespace System.Collections:
Exemplu de folosire stiva generica din namespace System.Collections.Generic:
Coada (Queue)
Coada (Queue) este o structura de date implementata in .NET Framework sub doua forme, coada simpla in namespace System.Collections, si coada ca structura de date generica in namespace System.Collections.Generic, principiul de functionare a structuri queue este FIFO(first in first out), primul element intrat primul iesit.
Exemplu de folosire coada simpla din namespace System.Collections:
Exemplu de folosire coada generica din namespace System.Collections.Generic:
Lista Inlantuita (Linked List)
Lista Inlantuita (Linked List) este o structura de date implementata in .NET Framework ca structura generica in namespace System.Collections.Generic, principiul de functionare a structuri lista inlatuita este ca fiecare nod din lista are o referinta la nodul urmator, exceptand coada listei care nu are o referinta la urmatorul nod.
Un exemplu de cautare in lista inlatuita a celui de al treilea element incepand de la sfarsit:
Exemplu de folosire lista inlatuita generica din namespace System.Collections.Generic:
Tablou De Dispersie (Hashtable)
Tablou De Dispersie (Hashtable) este o structura de date implementata in .NET Framework sub doua forme Hashtable simplu in namespace System.Collections si Dictionary ca structura de date generica in namespace System.Collections.Generic, este recomandat sa folosim Dictionary in loc de Hashtable, principiul de functionare a structuri Hashtable, Dictionary este ca se construieste un hash care e index intr-un array de obicei folosind polinoame.
Cautarea intr-un Hashtable, Dictionary are complexitatea de timp O(1).
Exemplu de folosire Dictionary generic din namespace System.Collections.Generic:
Desigur .NET Framework contine mai multe structuri de date optimizate pe anumite probleme, scopul acestui articol este sa prezint echivalente la structurile de date implementate in cursurile de algoritmi si structuri de date.
Cautare Binara (Binary Search)
Algoritmi de cautare reprezinta un alt topic din cursurile de algoritmi si structuri de date, putem folosi cautare secventiala cu complexitate O(n), sau binara daca elementele sunt sortate cu complexitate O(log n).
Ideea din spatele binary search este ca accesam elementul din mijloc si comparam cu cel cautat daca e mai mic se repeta procesul recursiv pentru prima jumatate, altfel se cauta in a doua jumatate, cautarea binara in .NET Framework se realizeaza cu Array.BinarySearch.
Un exemplu de folosire cautare binara folosind metoda Array.BinarySearch din .NET Framework:
Arbore Binar De Cautare (Binary Search Tree)
Un repository GitHub cu implementari custom pentru majoritatea structurilor de date cu cod sursa: https://github.com/aalhour/C-Sharp-Algorithms
Am sa prezint in continuare arbore binar de cautare (binary search tree) ideea e ca ai un nod radacina, fiecare nod are cel mult doua noduri copii, cel din stanga e mai mic decat radacina, la fel tot subarbore stang, nodul drept este mai mare decat radacina, la fel tot subarbore drept.
Exemplu de construire arbore binar:
Cautarea intr-un arbore binar de cautare are complexitatea de timp O(log n), exemplu de cautare in arbore binar:
Metode de parcurgere arbori binari:
Preordine
- Se parcurge rădăcina
- Se parcurge subarborele stâng
- Se parcurge subarborele drept
Inordine
- Se parcurge subarborele stâng
- Se parcurge rădăcina
- Se parcurge subarborele drept
Postordine
- Se parcurge subarborele stâng
- Se parcurge subarborele drept
- Se parcurge rădăcina
In .NET Framework, structura de date SortedList foloseste intern un arbore binar ca sa pastreze elementele sortate.
Graphs
Grafurile sunt structuri de date caracterizate prin noduri si muchii care unesc nodurile, se foloseste de obicei notatia G=(V, E)
unde, V reprezinta multimea de noduri(varfuri, vertices), si E reprezinta multimea de edges(muchii), in limbajul de programare se reprezinta prin matrice de adiacenta de exemplu a[i, j] = k, asta inseamna ca intre nodul i si j avem o muchie cu pondere k, se mai folosesc si liste de adiacenta pentru reprezentarea lor.
Grafurile si arbori pot fi parcursi si in latime(BREADTH FIRST) cu o coada, adancime(DEPTH FIRST) cu o stiva.
Algoritmi de sortare sunt un alt topic din cursurile de algoritmi si structuri de date, un tabel cu complexitatile acestora:
Top comments (0)