Algorithm and data structures exercises.
Build with Cpp and Ruby.
- ListNode: node for single linked list.
- LinkedList: single linked list based on pointer.
- Polynomial: polynomial class based on linked list, which supports operators +, - and *.
- Stack: stack based on linked list.
- StackBasedOnArray: stack based on array.
- Queue: queue based on linked list.
- QueueBasedOnArray: queue based on array.
- PriorityQueue: priority queue based on linked list.
- BinaryHeap: Binary heap based on array.
- SymbolTable: Symbol table based on linked list.
- OrderlySymbolTable: Orderly symbol table based on priority queue.
- BinarySearchTree: Binary search tree based on pointer.
- TwoThreeTree: 2-3-tree based on pointer, waiting for testing.
- RBTree: Red-black tree based on pointer.
- AVLTree: AVL tree based on pointer.
- HashTable: Separate chaining hash table based on array and symbol table.
- Graph: Undirected graph based on red black tree(vertex) and symbol table(adjacent vertex set).
- Digraph: Directed graph based on red black tree(vertex) and symbol table(adjacent vertex set).
- WeightedGraph: Weighted graph based on red black tree(vertex) and symbol table(adjacent vertex set).
- WeightedDigraph: Weighted directed graph based on red black tree(vertex) and symbol table(adjacent vertex set).
- Aplhabet: alphabet based on array.
- BucketSort: bucket sort, time-O(num_max + num_size), space-O(num_max).
- RadixSort: radix sort, time-O(num_msd(num_size)), space-O(num_size * num_radix).
- SymbolPairChecker: check the symbol pairs in string, time-online-O(n), space-O(n).
- PostfixExpressionManager: evaluate a postfix expression(time-O(n), space-O(1)) or convert an infix expression to postfix expression(time-O(n), space-O(N)).
- SelectionSort: selection sort, time-O(n^2), space-O(1).
- insertionSort: insertion sort, time-O(n)~O(n^2), space-O(1).
- shellSort: shell sort, time-O(n)~O(n^(3/2))(faster than insertion sort), space-O(1).
- mergeSort: merge sort, time-O(n * log(n)), space-O(Pn).
- quickSort: quick sort, optimized by insertion sort, median3 and 3way, time-O(n * log(n)), space-O(n).
- heapSort: heap sort, time-O(n * log(n)), space-O(n).
- binarySearch: binary search, time-O(log(n)), space-O(1).
- GraphDFS, GraphPathsDFS, GraphPathsBFS: algorithms for searching in graphs.
- DigraphDFS, DigraphPathsDFS, DigraphPathsBFS: algorithms for searching in graphs.
- DigraphFindCycle: find the cycle in an digraph.
- DigraphDFO: depth-first-order algorithm for digraph.
- DigraphTopological: topological sorting for an non-cycle digraph.
- DigraphSCCKosaraju: find all strongly connected components in a digraph.
- UnionFind: a tool class to solve problems about dynamic connectivity.
- WeightedGraphMSTPrim: find the Minimum Spanning Tree for a weighted graph with prim algorithm.
- WeightedGraphMSTKruskal: find the Minimum Spanning Tree for a weighted graph with kruskal algorithm.
- WeightedDigraphSPDijkstra: find the shortest path for a connected weighted digraph which has no negative weight with dijkstra algorithm.
- WeightedDigraphSPAcyclic: find the shortest path for a weighted DAG with a simple and fast algorithm.
- Sorting: sortings for string, includes msd, lsd, q3w.