Structuri de date si algoritmi fundamentali in C#
Tags: romanian, datastructures, algorithms, csharp
Published: 2020-03-05 18:46:15

---
title: Structuri de date si algoritmi fundamentali in C#
published: true
description: 
tags: romanian, datastructures, algorithms, csharp
cover_image: https://res.cloudinary.com/dbvcampra/image/upload/v1588403699/Webp.net-resizeimage_5_beudao.jpg
---
<a name="top"></a>
<a href="#stiva" style="text-decoration: underline;">Stiva (Stack)</a>
<a href="#coada" style="text-decoration: underline;">Coada (Queue)</a>
<a href="#lista" style="text-decoration: underline;">Lista Inlatuita (Linked List)</a>
<a href="#hashtable" style="text-decoration: underline;">Tablou De Dispersie (Hashtable)</a>
<a href="#cautareBinara" style="text-decoration: underline;">Cautare Binara (Binary Search)</a>
<a href="#arboreBinar" style="text-decoration: underline;">Arbore Binar De Cautare (Binary Search Tree)</a>
<a href="#grafuri" style="text-decoration: underline;">Grafuri (Graphs)</a>
<p>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 <b>.NET Framework</b>, 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.</p>
<a href="https://3.bp.blogspot.com/-FKfFL6z0zcI/XlfPWDD-SGI/AAAAAAAAHPk/MQ1l_RovxXgTIJCTReag9FzJRA3TILiYACLcBGAsYHQ/s1600/7365ce00a403fa7605fd2058c80ea65599ce67a2.png" imageanchor="1"><img border="0" data-original-height="514" data-original-width="953" src="https://3.bp.blogspot.com/-FKfFL6z0zcI/XlfPWDD-SGI/AAAAAAAAHPk/MQ1l_RovxXgTIJCTReag9FzJRA3TILiYACLcBGAsYHQ/s1600/7365ce00a403fa7605fd2058c80ea65599ce67a2.png" /></a>
Ca sa ne facem o idee ce inseamna o complexitate buna si una mai putin buna avem urmatorul grafic:
<a href="https://3.bp.blogspot.com/-DnioLTNlg2w/XlfPxIW0RlI/AAAAAAAAHPo/Glbj6UQ7KGA1OumrK_w-1-MArhdtKnuvACLcBGAsYHQ/s1600/8920364de7d83c9b50d5c51a5f385f20b4dd65d4.png" imageanchor="1"><img border="0" data-original-height="592" data-original-width="851" src="https://3.bp.blogspot.com/-DnioLTNlg2w/XlfPxIW0RlI/AAAAAAAAHPo/Glbj6UQ7KGA1OumrK_w-1-MArhdtKnuvACLcBGAsYHQ/s1600/8920364de7d83c9b50d5c51a5f385f20b4dd65d4.png" /></a>
In <b>.NET Framework</b> avem implementate urmatoarele structuri de date: <b> array, stack, queue, linked list</b> si algoritmi: <b>cautare binara(binary search)</b>, restul pe care nu le gasim in <b>.NET Framework</b> se pot gasi in pachete <b>NuGet</b> sau pe <b>GitHub</b>.
<b>Array</b> este una dintre cele mai folosite si cunoscute structuri de date si nu am sa detaliez cu exemple principiul de functionare.
<h2 id="stiva">
Stiva (Stack)</h2>
<b>Stiva (Stack)</b> este o structura de date implementata in <b>.NET Framework</b> sub doua forme, stiva simpla in namespace <b>System.Collections</b>, si stiva ca structura de date generica in namespace <b>System.Collections.Generic</b>, principiul de functionare a structuri stack este <b>LIFO(last in first out)</b>, ultimul element intrat primul iesit.
<a href="https://3.bp.blogspot.com/-ZTPyluNn8oU/XlkES_014qI/AAAAAAAAHRs/fG18AQEHxAwtzXiM7nKbssA3sl3uPVAtQCLcBGAsYHQ/s1600/0_SESFJYWU5a-3XM9m.gif" imageanchor="1" ><img border="0" src="https://3.bp.blogspot.com/-ZTPyluNn8oU/XlkES_014qI/AAAAAAAAHRs/fG18AQEHxAwtzXiM7nKbssA3sl3uPVAtQCLcBGAsYHQ/s1600/0_SESFJYWU5a-3XM9m.gif" data-original-width="640" data-original-height="400" /></a> 
Exemplu de folosire <b>stiva simpla</b> din namespace <b>System.Collections</b>:
{% gist https://gist.github.com/adavidoaiei/5fc3a1d28de925eee356416e2cbf8fe5.js %}

Exemplu de folosire <b>stiva generica</b> din namespace <b>System.Collections.Generic</b>:
{% gist https://gist.github.com/adavidoaiei/b3f6c2d76643268432b8eacdc467d5ba.js %}
<h2 id="coada">
Coada (Queue)</h2>
<b>Coada (Queue)</b> este o structura de date implementata in <b>.NET Framework</b> sub doua forme, coada simpla in namespace <b>System.Collections</b>, si coada ca structura de date generica in namespace <b>System.Collections.Generic</b>, principiul de functionare a structuri queue este <b>FIFO(first in first out)</b>, primul element intrat primul iesit.
<a href="https://1.bp.blogspot.com/-N-v_FiIdQXM/XlkFCQQYtPI/AAAAAAAAHR0/zxkuX6WfQS8Y8Mkoj1nHZDWtMOD3MjsUwCLcBGAsYHQ/s1600/0_E33E-AjyAUTFjVmM.gif" imageanchor="1" ><img border="0" src="https://1.bp.blogspot.com/-N-v_FiIdQXM/XlkFCQQYtPI/AAAAAAAAHR0/zxkuX6WfQS8Y8Mkoj1nHZDWtMOD3MjsUwCLcBGAsYHQ/s1600/0_E33E-AjyAUTFjVmM.gif" data-original-width="640" data-original-height="400" /></a>
Exemplu de folosire <b>coada simpla</b> din namespace <b>System.Collections</b>:
{% gist https://gist.github.com/adavidoaiei/0f66e5493ef84cb3a0aa222ba643656d.js %}

Exemplu de folosire <b>coada generica</b> din namespace <b>System.Collections.Generic</b>:
{% gist https://gist.github.com/adavidoaiei/ac81f3ad3c8c7b0e895820c6b001574f.js %}
<h2 id="lista">
Lista Inlantuita (Linked List)</h2>
<b>Lista Inlantuita (Linked List)</b> este o structura de date implementata in <b>.NET Framework</b> ca structura generica in namespace <b>System.Collections.Generic</b>, principiul de functionare a structuri <b>lista inlatuita</b> este ca fiecare nod din lista are o referinta la nodul urmator, exceptand coada listei care nu are o referinta la urmatorul nod.<br />
<a href="https://1.bp.blogspot.com/-mycmX6b0ubA/XlkFzTEJdZI/AAAAAAAAHSA/-dlS_xT-Wmoh8qPLWWiNO7Lthu8ByHY0wCLcBGAsYHQ/s1600/linked-list-programming-interview-questions-1.gif" imageanchor="1" ><img border="0" src="https://1.bp.blogspot.com/-mycmX6b0ubA/XlkFzTEJdZI/AAAAAAAAHSA/-dlS_xT-Wmoh8qPLWWiNO7Lthu8ByHY0wCLcBGAsYHQ/s1600/linked-list-programming-interview-questions-1.gif" data-original-width="1125" data-original-height="446" /></a>
Un exemplu de cautare in lista inlatuita a celui de al treilea element incepand de la sfarsit:
<a href="https://2.bp.blogspot.com/-TFPEI7QYVVQ/XlkGVSEJiZI/AAAAAAAAHSI/M_oTsk9FQeEpkqac8UCZiI_dA5Khr8MPQCLcBGAsYHQ/s1600/linked-list-programming-interview-questions-5.gif" imageanchor="1" ><img border="0" src="https://2.bp.blogspot.com/-TFPEI7QYVVQ/XlkGVSEJiZI/AAAAAAAAHSI/M_oTsk9FQeEpkqac8UCZiI_dA5Khr8MPQCLcBGAsYHQ/s1600/linked-list-programming-interview-questions-5.gif" data-original-width="960" data-original-height="383" /></a>
Exemplu de folosire <b>lista inlatuita generica</b> din namespace <b>System.Collections.Generic</b>:
{% gist https://gist.github.com/adavidoaiei/9b9c964b8c9ab47787c8b1d5c03de94d.js %}
<h2 id="hashtable">Tablou De Dispersie (Hashtable)</h2>
<b>Tablou De Dispersie (Hashtable)</b> este o structura de date implementata in <b>.NET Framework</b> sub doua forme <b>Hashtable</b> simplu in namespace <b>System.Collections</b> si <b>Dictionary<tkey alue=""></tkey></b> ca structura de date generica in namespace <b>System.Collections.Generic</b>, este recomandat sa folosim <b>Dictionary<tkey alue=""></tkey></b> in loc de <b>Hashtable</b>, principiul de functionare a structuri <b>Hashtable, Dictionary</b> este ca se construieste un hash care e index intr-un array de obicei folosind polinoame.
Cautarea intr-un <b>Hashtable, Dictionary</b> are complexitatea de timp <b>O(1)</b>.
<a href="https://2.bp.blogspot.com/-Ev3g3OAw7x8/XlkJGYgdg6I/AAAAAAAAHSo/UiWwc1NZPikJAClCrlCUafpcxjVoCDQbgCLcBGAsYHQ/s1600/2671f5ebb8358c5347b9d9e3c65b3d50.gif" imageanchor="1" ><img border="0" src="https://2.bp.blogspot.com/-Ev3g3OAw7x8/XlkJGYgdg6I/AAAAAAAAHSo/UiWwc1NZPikJAClCrlCUafpcxjVoCDQbgCLcBGAsYHQ/s1600/2671f5ebb8358c5347b9d9e3c65b3d50.gif" data-original-width="1024" data-original-height="768" /></a>
Exemplu de folosire <b>Dictionary</b> generic din namespace <b>System.Collections.Generic</b>:
{% gist https://gist.github.com/adavidoaiei/64b8708d88483ba351c43ce5e0c46399.js %}

Desigur <b>.NET Framework</b> 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.
<h2 id="cautareBinara">
Cautare Binara (Binary Search)</h2>
<b>Algoritmi de cautare</b> reprezinta un alt topic din cursurile de algoritmi si structuri de date, putem folosi cautare secventiala cu complexitate <b>O(n)</b>, sau binara daca elementele sunt sortate cu complexitate <b>O(log n)</b>. 
Ideea din spatele <b>binary search</b> 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 <b>.NET Framework</b> se realizeaza cu <b>Array.BinarySearch</b>.
<a href="https://2.bp.blogspot.com/-8p4tjlqWJUA/Xlfp7ZMmXBI/AAAAAAAAHQw/-hwOCmpL-ForYEKgPejMaVgGRfWeCf3agCLcBGAsYHQ/s1600/Binary-Search.png" imageanchor="1"><img border="0" data-original-height="891" data-original-width="1600" src="https://2.bp.blogspot.com/-8p4tjlqWJUA/Xlfp7ZMmXBI/AAAAAAAAHQw/-hwOCmpL-ForYEKgPejMaVgGRfWeCf3agCLcBGAsYHQ/s1600/Binary-Search.png" /></a>
Un exemplu de folosire <b>cautare binara</b> folosind metoda <b>Array.BinarySearch</b> din <b>.NET Framework</b>:
{% gist https://gist.github.com/adavidoaiei/9daf6cecf62d3afe9813fb31064366ec.js %}
<h2 id="arboreBinar">
Arbore Binar De Cautare (Binary Search Tree)</h2>
Un repository <b>GitHub</b> cu implementari custom pentru majoritatea structurilor de date cu cod sursa: <a href="https://github.com/aalhour/C-Sharp-Algorithms" target="_blank">https://github.com/aalhour/C-Sharp-Algorithms</a>
Am sa prezint in continuare <b>arbore binar de cautare (binary search tree)</b> 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:
<a href="https://1.bp.blogspot.com/-pGiDeTRcsLg/XlkHp31PCWI/AAAAAAAAHSU/50wl0AFRcBcVEnOsWCoQzELZZAkhi_B8gCLcBGAsYHQ/s1600/binary-search-tree-insertion-animation.gif" imageanchor="1" ><img border="0" src="https://1.bp.blogspot.com/-pGiDeTRcsLg/XlkHp31PCWI/AAAAAAAAHSU/50wl0AFRcBcVEnOsWCoQzELZZAkhi_B8gCLcBGAsYHQ/s1600/binary-search-tree-insertion-animation.gif" data-original-width="400" data-original-height="255" /></a>
Cautarea intr-un arbore binar de cautare are complexitatea de timp <b>O(log n)</b>, exemplu de cautare in arbore binar:
<a href="https://2.bp.blogspot.com/-yVH0ySkTzSc/XlkH1xlGjpI/AAAAAAAAHSY/AAOHTzDFTNMI06I6zi465ENOftos8CVIgCLcBGAsYHQ/s1600/binary-search-tree-sorted-array-animation.gif" imageanchor="1" ><img border="0" src="https://2.bp.blogspot.com/-yVH0ySkTzSc/XlkH1xlGjpI/AAAAAAAAHSY/AAOHTzDFTNMI06I6zi465ENOftos8CVIgCLcBGAsYHQ/s1600/binary-search-tree-sorted-array-animation.gif" data-original-width="450" data-original-height="378" /></a>

<b>Metode de parcurgere arbori binari:</b>
<b>Preordine</b>
<ul>
<li>Se parcurge rădăcina</li>
<li>Se parcurge subarborele stâng</li>
<li>Se parcurge subarborele drept</li>
</li>
</ul>
<b>Inordine</b>
<ul>
<li>Se parcurge subarborele stâng</li>
<li>Se parcurge rădăcina</li>
<li>Se parcurge subarborele drept</li>
</ul>
<b>Postordine</b>
<ul>
<li>Se parcurge subarborele stâng</li>
<li>Se parcurge subarborele drept</li>
<li>Se parcurge rădăcina</li>
</ul>
In <b>.NET Framework</b>, structura de date <b>SortedList</b> foloseste intern un arbore binar ca sa pastreze elementele sortate.
<h2 id="grafuri">Graphs</h2>
<b>Grafurile</b> sunt structuri de date caracterizate prin noduri si muchii care unesc nodurile, se foloseste de obicei notatia <b>G=(V, E)</b>
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.
<a href="https://1.bp.blogspot.com/-IpYtBbTx2so/XlgW-8pdUZI/AAAAAAAAHRU/yHxOd7zlDssb8Qle7vVxOLbq67n0Y3qWACLcBGAsYHQ/s1600/undirectedgraph.png" imageanchor="1"><img border="0" data-original-height="212" data-original-width="491" src="https://1.bp.blogspot.com/-IpYtBbTx2so/XlgW-8pdUZI/AAAAAAAAHRU/yHxOd7zlDssb8Qle7vVxOLbq67n0Y3qWACLcBGAsYHQ/s1600/undirectedgraph.png" /></a>  
<b>Grafurile si arbori</b> pot fi parcursi si in <b>latime(BREADTH FIRST) cu o coada</b>, <b>adancime(DEPTH FIRST) cu o stiva</b>.
<a href="https://4.bp.blogspot.com/-Jmkim2LA2Sc/Xlgeg6oMrtI/AAAAAAAAHRg/vopRL-U9cbMGzrjon4_00ov2Sbi5bYuOwCLcBGAsYHQ/s1600/dfsbfs.gif" imageanchor="1"><img border="0" data-original-height="333" data-original-width="640" src="https://4.bp.blogspot.com/-Jmkim2LA2Sc/Xlgeg6oMrtI/AAAAAAAAHRg/vopRL-U9cbMGzrjon4_00ov2Sbi5bYuOwCLcBGAsYHQ/s1600/dfsbfs.gif" /></a>  
<b>Algoritmi de sortare</b> sunt un alt topic din cursurile de algoritmi si structuri de date, un tabel cu complexitatile acestora:
<a href="https://2.bp.blogspot.com/-oTc6mX9YO1c/XlfsQNo8WlI/AAAAAAAAHQ8/6oewcGTWPQAZlYWDT_lvalfi1x-JgoUagCLcBGAsYHQ/s1600/80a161cc62e754af348a85e9f3f56f92d80bb279%2B%25281%2529.png" imageanchor="1"><img border="0" data-original-height="477" data-original-width="591" src="https://2.bp.blogspot.com/-oTc6mX9YO1c/XlfsQNo8WlI/AAAAAAAAHQ8/6oewcGTWPQAZlYWDT_lvalfi1x-JgoUagCLcBGAsYHQ/s1600/80a161cc62e754af348a85e9f3f56f92d80bb279%2B%25281%2529.png" /></a>