Structuri de date si algoritmi fundamentali in C#

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:

	using System;
	using System.Collections;
	public class SamplesStack {
	public static void Main() {
	// Creates and initializes a new Stack.
	Stack myStack = new Stack();
	myStack.Push("Hello");
	myStack.Push("World");
	myStack.Push("!");
	// Displays the properties and values of the Stack.
	Console.WriteLine( "myStack" );
	Console.WriteLine( "\tCount: {0}", myStack.Count );
	Console.Write( "\tValues:" );
	PrintValues( myStack );
	}
	public static void PrintValues( IEnumerable myCollection ) {
	foreach ( Object obj in myCollection )
	Console.Write( " {0}", obj );
	Console.WriteLine();
	}
	}
	/*
	This code produces the following output.
	myStack
	Count: 3
	Values: ! World Hello
	*/

view raw Stack.cs hosted with ❤ by GitHub

Exemplu de folosire stiva generica din namespace System.Collections.Generic:

	using System;
	using System.Collections.Generic;
	class Example
	{
	public static void Main()
	{
	Stack<string> numbers = new Stack<string>();
	numbers.Push("one");
	numbers.Push("two");
	numbers.Push("three");
	numbers.Push("four");
	numbers.Push("five");
	// A stack can be enumerated without disturbing its contents.
	foreach( string number in numbers )
	{
	Console.WriteLine(number);
	}
	Console.WriteLine("\nPopping '{0}'", numbers.Pop());
	Console.WriteLine("Peek at next item to destack: {0}",
	numbers.Peek());
	Console.WriteLine("Popping '{0}'", numbers.Pop());
	// Create a copy of the stack, using the ToArray method and the
	// constructor that accepts an IEnumerable<T>.
	Stack<string> stack2 = new Stack<string>(numbers.ToArray());
	Console.WriteLine("\nContents of the first copy:");
	foreach( string number in stack2 )
	{
	Console.WriteLine(number);
	}
	// Create an array twice the size of the stack and copy the
	// elements of the stack, starting at the middle of the
	// array.
	string[] array2 = new string[numbers.Count * 2];
	numbers.CopyTo(array2, numbers.Count);
	// Create a second stack, using the constructor that accepts an
	// IEnumerable(Of T).
	Stack<string> stack3 = new Stack<string>(array2);
	Console.WriteLine("\nContents of the second copy, with duplicates and nulls:");
	foreach( string number in stack3 )
	{
	Console.WriteLine(number);
	}
	Console.WriteLine("\nstack2.Contains(\"four\") = {0}",
	stack2.Contains("four"));
	Console.WriteLine("\nstack2.Clear()");
	stack2.Clear();
	Console.WriteLine("\nstack2.Count = {0}", stack2.Count);
	}
	}
	/* This code example produces the following output:
	five
	four
	three
	two
	one
	Popping 'five'
	Peek at next item to destack: four
	Popping 'four'
	Contents of the first copy:
	one
	two
	three
	Contents of the second copy, with duplicates and nulls:
	one
	two
	three
	stack2.Contains("four") = False
	stack2.Clear()
	stack2.Count = 0
	*/

view raw GenericStack.cs hosted with ❤ by GitHub

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:

	using System;
	using System.Collections;
	public class SamplesQueue {
	public static void Main() {
	// Creates and initializes a new Queue.
	Queue myQ = new Queue();
	myQ.Enqueue("Hello");
	myQ.Enqueue("World");
	myQ.Enqueue("!");
	// Displays the properties and values of the Queue.
	Console.WriteLine( "myQ" );
	Console.WriteLine( "\tCount: {0}", myQ.Count );
	Console.Write( "\tValues:" );
	PrintValues( myQ );
	}
	public static void PrintValues( IEnumerable myCollection ) {
	foreach ( Object obj in myCollection )
	Console.Write( " {0}", obj );
	Console.WriteLine();
	}
	}
	/*
	This code produces the following output.
	myQ
	Count: 3
	Values: Hello World !
	*/

view raw Queue.cs hosted with ❤ by GitHub

Exemplu de folosire coada generica din namespace System.Collections.Generic:

	using System;
	using System.Collections.Generic;
	class Example
	{
	public static void Main()
	{
	Queue<string> numbers = new Queue<string>();
	numbers.Enqueue("one");
	numbers.Enqueue("two");
	numbers.Enqueue("three");
	numbers.Enqueue("four");
	numbers.Enqueue("five");
	// A queue can be enumerated without disturbing its contents.
	foreach( string number in numbers )
	{
	Console.WriteLine(number);
	}
	Console.WriteLine("\nDequeuing '{0}'", numbers.Dequeue());
	Console.WriteLine("Peek at next item to dequeue: {0}",
	numbers.Peek());
	Console.WriteLine("Dequeuing '{0}'", numbers.Dequeue());
	// Create a copy of the queue, using the ToArray method and the
	// constructor that accepts an IEnumerable<T>.
	Queue<string> queueCopy = new Queue<string>(numbers.ToArray());
	Console.WriteLine("\nContents of the first copy:");
	foreach( string number in queueCopy )
	{
	Console.WriteLine(number);
	}
	// Create an array twice the size of the queue and copy the
	// elements of the queue, starting at the middle of the
	// array.
	string[] array2 = new string[numbers.Count * 2];
	numbers.CopyTo(array2, numbers.Count);
	// Create a second queue, using the constructor that accepts an
	// IEnumerable(Of T).
	Queue<string> queueCopy2 = new Queue<string>(array2);
	Console.WriteLine("\nContents of the second copy, with duplicates and nulls:");
	foreach( string number in queueCopy2 )
	{
	Console.WriteLine(number);
	}
	Console.WriteLine("\nqueueCopy.Contains(\"four\") = {0}",
	queueCopy.Contains("four"));
	Console.WriteLine("\nqueueCopy.Clear()");
	queueCopy.Clear();
	Console.WriteLine("\nqueueCopy.Count = {0}", queueCopy.Count);
	}
	}
	/* This code example produces the following output:
	one
	two
	three
	four
	five
	Dequeuing 'one'
	Peek at next item to dequeue: two
	Dequeuing 'two'
	Contents of the copy:
	three
	four
	five
	Contents of the second copy, with duplicates and nulls:
	three
	four
	five
	queueCopy.Contains("four") = True
	queueCopy.Clear()
	queueCopy.Count = 0
	*/

view raw QueueGeneric.cs hosted with ❤ by GitHub

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:

	using System;
	using System.Text;
	using System.Collections.Generic;
	public class Example
	{
	public static void Main()
	{
	// Create the link list.
	string[] words =
	{ "the", "fox", "jumps", "over", "the", "dog" };
	LinkedList<string> sentence = new LinkedList<string>(words);
	Display(sentence, "The linked list values:");
	Console.WriteLine("sentence.Contains(\"jumps\") = {0}",
	sentence.Contains("jumps"));
	// Add the word 'today' to the beginning of the linked list.
	sentence.AddFirst("today");
	Display(sentence, "Test 1: Add 'today' to beginning of the list:");
	// Move the first node to be the last node.
	LinkedListNode<string> mark1 = sentence.First;
	sentence.RemoveFirst();
	sentence.AddLast(mark1);
	Display(sentence, "Test 2: Move first node to be last node:");
	// Change the last node to 'yesterday'.
	sentence.RemoveLast();
	sentence.AddLast("yesterday");
	Display(sentence, "Test 3: Change the last node to 'yesterday':");
	// Move the last node to be the first node.
	mark1 = sentence.Last;
	sentence.RemoveLast();
	sentence.AddFirst(mark1);
	Display(sentence, "Test 4: Move last node to be first node:");
	// Indicate the last occurence of 'the'.
	sentence.RemoveFirst();
	LinkedListNode<string> current = sentence.FindLast("the");
	IndicateNode(current, "Test 5: Indicate last occurence of 'the':");
	// Add 'lazy' and 'old' after 'the' (the LinkedListNode named current).
	sentence.AddAfter(current, "old");
	sentence.AddAfter(current, "lazy");
	IndicateNode(current, "Test 6: Add 'lazy' and 'old' after 'the':");
	// Indicate 'fox' node.
	current = sentence.Find("fox");
	IndicateNode(current, "Test 7: Indicate the 'fox' node:");
	// Add 'quick' and 'brown' before 'fox':
	sentence.AddBefore(current, "quick");
	sentence.AddBefore(current, "brown");
	IndicateNode(current, "Test 8: Add 'quick' and 'brown' before 'fox':");
	// Keep a reference to the current node, 'fox',
	// and to the previous node in the list. Indicate the 'dog' node.
	mark1 = current;
	LinkedListNode<string> mark2 = current.Previous;
	current = sentence.Find("dog");
	IndicateNode(current, "Test 9: Indicate the 'dog' node:");
	// The AddBefore method throws an InvalidOperationException
	// if you try to add a node that already belongs to a list.
	Console.WriteLine("Test 10: Throw exception by adding node (fox) already in the list:");
	try
	{
	sentence.AddBefore(current, mark1);
	}
	catch (InvalidOperationException ex)
	{
	Console.WriteLine("Exception message: {0}", ex.Message);
	}
	Console.WriteLine();
	// Remove the node referred to by mark1, and then add it
	// before the node referred to by current.
	// Indicate the node referred to by current.
	sentence.Remove(mark1);
	sentence.AddBefore(current, mark1);
	IndicateNode(current, "Test 11: Move a referenced node (fox) before the current node (dog):");
	// Remove the node referred to by current.
	sentence.Remove(current);
	IndicateNode(current, "Test 12: Remove current node (dog) and attempt to indicate it:");
	// Add the node after the node referred to by mark2.
	sentence.AddAfter(mark2, current);
	IndicateNode(current, "Test 13: Add node removed in test 11 after a referenced node (brown):");
	// The Remove method finds and removes the
	// first node that that has the specified value.
	sentence.Remove("old");
	Display(sentence, "Test 14: Remove node that has the value 'old':");
	// When the linked list is cast to ICollection(Of String),
	// the Add method adds a node to the end of the list.
	sentence.RemoveLast();
	ICollection<string> icoll = sentence;
	icoll.Add("rhinoceros");
	Display(sentence, "Test 15: Remove last node, cast to ICollection, and add 'rhinoceros':");
	Console.WriteLine("Test 16: Copy the list to an array:");
	// Create an array with the same number of
	// elements as the linked list.
	string[] sArray = new string[sentence.Count];
	sentence.CopyTo(sArray, 0);
	foreach (string s in sArray)
	{
	Console.WriteLine(s);
	}
	// Release all the nodes.
	sentence.Clear();
	Console.WriteLine();
	Console.WriteLine("Test 17: Clear linked list. Contains 'jumps' = {0}",
	sentence.Contains("jumps"));
	Console.ReadLine();
	}
	private static void Display(LinkedList<string> words, string test)
	{
	Console.WriteLine(test);
	foreach (string word in words)
	{
	Console.Write(word + " ");
	}
	Console.WriteLine();
	Console.WriteLine();
	}
	private static void IndicateNode(LinkedListNode<string> node, string test)
	{
	Console.WriteLine(test);
	if (node.List == null)
	{
	Console.WriteLine("Node '{0}' is not in the list.\n",
	node.Value);
	return;
	}
	StringBuilder result = new StringBuilder("(" + node.Value + ")");
	LinkedListNode<string> nodeP = node.Previous;
	while (nodeP != null)
	{
	result.Insert(0, nodeP.Value + " ");
	nodeP = nodeP.Previous;
	}
	node = node.Next;
	while (node != null)
	{
	result.Append(" " + node.Value);
	node = node.Next;
	}
	Console.WriteLine(result);
	Console.WriteLine();
	}
	}
	//This code example produces the following output:
	//
	//The linked list values:
	//the fox jumps over the dog
	//Test 1: Add 'today' to beginning of the list:
	//today the fox jumps over the dog
	//Test 2: Move first node to be last node:
	//the fox jumps over the dog today
	//Test 3: Change the last node to 'yesterday':
	//the fox jumps over the dog yesterday
	//Test 4: Move last node to be first node:
	//yesterday the fox jumps over the dog
	//Test 5: Indicate last occurence of 'the':
	//the fox jumps over (the) dog
	//Test 6: Add 'lazy' and 'old' after 'the':
	//the fox jumps over (the) lazy old dog
	//Test 7: Indicate the 'fox' node:
	//the (fox) jumps over the lazy old dog
	//Test 8: Add 'quick' and 'brown' before 'fox':
	//the quick brown (fox) jumps over the lazy old dog
	//Test 9: Indicate the 'dog' node:
	//the quick brown fox jumps over the lazy old (dog)
	//Test 10: Throw exception by adding node (fox) already in the list:
	//Exception message: The LinkedList node belongs a LinkedList.
	//Test 11: Move a referenced node (fox) before the current node (dog):
	//the quick brown jumps over the lazy old fox (dog)
	//Test 12: Remove current node (dog) and attempt to indicate it:
	//Node 'dog' is not in the list.
	//Test 13: Add node removed in test 11 after a referenced node (brown):
	//the quick brown (dog) jumps over the lazy old fox
	//Test 14: Remove node that has the value 'old':
	//the quick brown dog jumps over the lazy fox
	//Test 15: Remove last node, cast to ICollection, and add 'rhinoceros':
	//the quick brown dog jumps over the lazy rhinoceros
	//Test 16: Copy the list to an array:
	//the
	//quick
	//brown
	//dog
	//jumps
	//over
	//the
	//lazy
	//rhinoceros
	//Test 17: Clear linked list. Contains 'jumps' = False
	//

view raw LinkedListGeneric.cs hosted with ❤ by GitHub

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:

	// Create a new dictionary of strings, with string keys.
	//
	Dictionary<string, string> openWith =
	new Dictionary<string, string>();
	// Add some elements to the dictionary. There are no
	// duplicate keys, but some of the values are duplicates.
	openWith.Add("txt", "notepad.exe");
	openWith.Add("bmp", "paint.exe");
	openWith.Add("dib", "paint.exe");
	openWith.Add("rtf", "wordpad.exe");
	// The Add method throws an exception if the new key is
	// already in the dictionary.
	try
	{
	openWith.Add("txt", "winword.exe");
	}
	catch (ArgumentException)
	{
	Console.WriteLine("An element with Key = \"txt\" already exists.");
	}
	// The Item property is another name for the indexer, so you
	// can omit its name when accessing elements.
	Console.WriteLine("For key = \"rtf\", value = {0}.",
	openWith["rtf"]);
	// The indexer can be used to change the value associated
	// with a key.
	openWith["rtf"] = "winword.exe";
	Console.WriteLine("For key = \"rtf\", value = {0}.",
	openWith["rtf"]);
	// If a key does not exist, setting the indexer for that key
	// adds a new key/value pair.
	openWith["doc"] = "winword.exe";
	// The indexer throws an exception if the requested key is
	// not in the dictionary.
	try
	{
	Console.WriteLine("For key = \"tif\", value = {0}.",
	openWith["tif"]);
	}
	catch (KeyNotFoundException)
	{
	Console.WriteLine("Key = \"tif\" is not found.");
	}
	// When a program often has to try keys that turn out not to
	// be in the dictionary, TryGetValue can be a more efficient
	// way to retrieve values.
	string value = "";
	if (openWith.TryGetValue("tif", out value))
	{
	Console.WriteLine("For key = \"tif\", value = {0}.", value);
	}
	else
	{
	Console.WriteLine("Key = \"tif\" is not found.");
	}
	// ContainsKey can be used to test keys before inserting
	// them.
	if (!openWith.ContainsKey("ht"))
	{
	openWith.Add("ht", "hypertrm.exe");
	Console.WriteLine("Value added for key = \"ht\": {0}",
	openWith["ht"]);
	}
	// When you use foreach to enumerate dictionary elements,
	// the elements are retrieved as KeyValuePair objects.
	Console.WriteLine();
	foreach( KeyValuePair<string, string> kvp in openWith )
	{
	Console.WriteLine("Key = {0}, Value = {1}",
	kvp.Key, kvp.Value);
	}
	// To get the values alone, use the Values property.
	Dictionary<string, string>.ValueCollection valueColl =
	openWith.Values;
	// The elements of the ValueCollection are strongly typed
	// with the type that was specified for dictionary values.
	Console.WriteLine();
	foreach( string s in valueColl )
	{
	Console.WriteLine("Value = {0}", s);
	}
	// To get the keys alone, use the Keys property.
	Dictionary<string, string>.KeyCollection keyColl =
	openWith.Keys;
	// The elements of the KeyCollection are strongly typed
	// with the type that was specified for dictionary keys.
	Console.WriteLine();
	foreach( string s in keyColl )
	{
	Console.WriteLine("Key = {0}", s);
	}
	// Use the Remove method to remove a key/value pair.
	Console.WriteLine("\nRemove(\"doc\")");
	openWith.Remove("doc");
	if (!openWith.ContainsKey("doc"))
	{
	Console.WriteLine("Key \"doc\" is not found.");
	}
	/* This code example produces the following output:
	An element with Key = "txt" already exists.
	For key = "rtf", value = wordpad.exe.
	For key = "rtf", value = winword.exe.
	Key = "tif" is not found.
	Key = "tif" is not found.
	Value added for key = "ht": hypertrm.exe
	Key = txt, Value = notepad.exe
	Key = bmp, Value = paint.exe
	Key = dib, Value = paint.exe
	Key = rtf, Value = winword.exe
	Key = doc, Value = winword.exe
	Key = ht, Value = hypertrm.exe
	Value = notepad.exe
	Value = paint.exe
	Value = paint.exe
	Value = winword.exe
	Value = winword.exe
	Value = hypertrm.exe
	Key = txt
	Key = bmp
	Key = dib
	Key = rtf
	Key = doc
	Key = ht
	Remove("doc")
	Key "doc" is not found.
	*/

view raw Dictionary.cs hosted with ❤ by GitHub

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:

	class Program
	{
	static void Main(string[] args)
	{
	// Create an array of 10 elements
	int[] IntArray = new int[10] { 1, 3, 5, 7, 11, 13, 17, 19, 23, 31 };
	// Value to search for
	int target = 17;
	int pos = Array.BinarySearch(IntArray, target);
	if (pos >= 0)
	Console.WriteLine($"Item {IntArray[pos].ToString()} found at position {pos + 1}.");
	else
	Console.WriteLine("Item not found");
	Console.ReadKey();
	}
	}

view raw ArrayBinarySearch.cs hosted with ❤ by GitHub

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: