数据结构与算法的C#实现
Implementations of Data Structures and Algorithms in C#.
I started writing this organized collection of classes as part of my preparation for technical interviews. This is for educational purposes only. However, the source code is stable.
This is a .NET solution and it can be opened with both Xamarin Studio (MonoDevelop) and Visual Studio. It has two separate projects: 1) Algorithms, 2) DataStructures. Both of them are classlibrary projects.
The third project is called MainProgram and it has all the tests for all the implemented algorithms and data structures. It has two main directories:
Data Structures
Lists:
 SingleLinked List.
 DoubleLinked List.
 Array List. A generic arraysbased list. Implements autoresizing and handles overflow.
 Stack. Based on my ArrayList<T>.
 Queue. Based on my ArrayList<T>.
Priority Queues:
 Priority Queue. Based on my MaxHeap<T>.
 Keyed Priority Queue. Based on my MaxHeap<T>.
Heaps:
 Binary MinHeap. Uses the ArrayList<T> class.
 Binary MaxHeap. Uses the ArrayList<T> class.
 Binomial MinHeap. Uses the ArrayList<T> class as a collection of connected BinomialNode lists. The BinomialNode is a private class inside the Heap data structure class.
Trees:
 Binary Search Tree. Standard BST.
 Augmented Binary Search Tree. A BST that is augmented to keep track of the subtreessize for each node. Extends the BinarySearchTree<T> class.
 AVL Tree. The selfbalancing AVL binarysearch tree. Extends the BinarySearchTree<T> class.
Hashing Functions:
 Prime Hashing Family. Implements a simple family of hash functions using primes. The functions are initialized by randomly selecting primes. Supports regeneration of functions.
 Universal Hashing Family. Implements a family class of simple universalhashing functions. Supports regeneration of functions. It uses the Common/PrimesList helper class.
Hash Tables / Dictionaries:
 Chained Hash Table. A hash table that implements the SeparateChaining scheme for resolving keyscollisions. It also implements autoresizing (expansion and contraction).
 Cuckoo Hash Table. A hash table that implements the Cuckoo Hashing algorithm for resolving keyscollisions. This is a singletable implementation, the source behind this is the work of Mark Allen Weiss, 2014.
Graphs:

Undirected Graphs:
 Undirected Sparse Graph. An adjacencylist graph representation. Implemented using a Dictionary of IComparable<T> keys and DoubleLinked Lists values. The IComparable<T> keys serve as the nodes (vertices), and the lists serve as each node's adjacent nodes. Implements the IGraph<T> interface.
 Undirected Dense Graph. An incidencematrix graph representation. Implemented using the native two dimensional arrays in C#. The two dimenssional array holds boolean values that represent the edges connectivity between vertices. The vertices are held inside an internal dynamic list. The index of each vertex represent its key. Keys of vertices are managed systematically between the verticesvector and the adjacencymatrix. It was implemented this way to achieve the capability of inserting any IComparable<Type> of vertex into the graph. Implements the IGraph<T> interface.

Directed Graphs / Digraphs:
 Directed Sparse Graph. An adjacencylist digraph representation. Follows almost the same implementation details of the Undirected version, except for managing the directed edges. Implements the IGraph<T> interface.
 Directed Dense Graph. An incidencematrix digraph representation. Follows almost the same implementation details of the Undirected version, except for managing the directed edges. Implements the IGraph<T> interface. </ul> </li>

Directed Weighted Graphs / Weighted Digraphs:
 Directed Weighted Sparse Graph. An adjacencylist weighted digraph representation. Shares a great deal of implemention details with the Directed Sparse version (DirectedSparseGraph<T>). Implements both interfaces: IGraph<T> and IWeightedGraph<T>. It manages the weights of edges through an internal WeightedEdge<T> class.
 Directed Weighted Dense Graph. An adjacencymatrix weighted digraph representation. Inherits and extends Directed Dense verion (DirectedDenseGraph<T>). Implements the IWeightedGraph<T> interface. </ul> </li> </ul>
 Insertion Sort.
 Quick Sort.
 Merge Sort.
 Heap Sort.
 BST Sort. Implements an unbalanced binary search tree sort.

Counting Sort. Only sorts arrays of integers.
int[] array = new int[] { 23, 42, 4, 16, 8, 15, 3, 9, 55, 0 }; List<long> list = new List<long> () { 23, 42, 4, 16, 8, 15, 3, 9, 55, 0 }; // The value comparer object. Can be any value comparer that implmenets IComparer. var valueComparer = Comparer<long>.Default; list.InsertionSort (valueComparer); list.QuickSort (valueComparer); list.MergeSort (valueComparer); list.HeapSort (valueComparer); list.UnbalancedBSTSort(); array.CountingSort();
 DepthFirst Searcher. Implements the DFS algorithm in two ways: Iterative and Recursive. Provides multiple functions for traversing graphs: PrintAll(), VisitAll(Action<T> forEachFunc), FindFirstMatch(Predicate<T> match). The VisitAll() applies a function to every graph nodes. The FindFirstMatch() function takes searches the graph for a predicate match.
 BreadthFirst Searcher. Implements the DFS algorithm in an iterative fashion. Provides multiple functions for traversing graphs: PrintAll(), VisitAll(Action<T> forEachFunc), FindFirstMatch(Predicate<T> match). The VisitAll() applies a function to every graph nodes. The FindFirstMatch() function takes searches the graph for a predicate match.
 Breadth First Paths. A class that takes a Graph instance upon objectinstantiation as a parameter, and then applies BFS to the graph. Meanwhile applying BFS to the graph, it extracts information about shortestpaths and connectivity. It provides the capability to find shortestpaths from singlesources and multiplesources. Also, to check for reachable and unreachable nodes from the specified sourcenode(s).
 Catalan Numbers. A class that calculates the catalan numbers. A dynamicprogramming solution.

Tree Drawer. Draws any tree that extends my BinarySearchTree<T> class. It is defined as an extension method.
var avlTree = new AVLTree<int>(); var treeDataList = new List<int>() { 15, 25, 5, 12, 1, 9, 7, 1, 11, 30, 8, 10, 13, 28, 39 }; avlTree.Insert(treeDataList); Console.WriteLine( avlTree.DrawTree() ); /*** ** Drawer output: ** .......9...... ** / \ ** .5 ....12... ** / \ / \ ** 1 7 11 .25. ** /\ / \ /\ / \ ** 1 8 10 15 30 ** /\ /\ /\ /\ / \ ** 13 28 39 ** /\ /\ /\ */
Algorithms
Sorting:
Sorting algorithms are implemented as an extension method. They support the native Array<T>, and List<T> classes. They can takes value comparers. Insertion Sort supports my ArrayList<T> class.
Graphs:
Numeric:
Visualization: