AlgorithmLibrary

A library containing some data structures and algorithms written in c/c++.

Getting Started

Compile and run

$ make
$ make run

For usage, see function main()

Data Structure

Name	Source	Comment
Linked List	LinkedList.h	support sort
Binary Heap	BinaryHeap.h	priority queue
Hash Table	HashTable.h	use bucket list
AVL Tree	AVLTree.h	support balanced insert and remove
Disjoint Set	DisjointSet.h DisjointSet.cpp	express relation of equivalence
Graph	Graph.h Graph.cpp	use adjacent list or matrix; node stores nonnegative number

Algorithm

Name	Source	Comment
Sorting	SortHelper.h	classic sorting algorithms
Random Number Generation	Random.h Random.cpp	pseudorandom number generation
Arithmetic Expression	ArithmeticExpression.h ArithmeticExpression.cpp	arithemetic expression calculation
MD5 (CN)	MD5.h MD5.cpp	message encrypt
N-Puzzle Problem	NPuzzle.h NPuzzle.cpp	solve using hill climbing, simulated annealing, A* search; GUI demo; 中文博客
N-Queens Problem	NQueen.h NQueen.cpp	solve using hill climbing and simulated annealing
Factorial	Algorithm::factorial()	20! is max (return unsigned long long)
Binary Search	Algorithm::binarySearch()	find first or last appeared position
Permutation	Algorithm::nextPermutation()	non-recursive version
Combination	Algorithm::printCombinations()	non-recursive version
Cantor Expansion (CN)	Algorithm::cantorExpand()	cantor expansion and its inverse
Prime Number	Algorithm::nextPrime()	find next prime number (choose appropriate buckets number for hash table)
Topological Sort	AlgorithmGraph::topoSort()	check if a graph is cyclic
Dijkstra	AlgorithmGraph::dijkstra()	shortest path
Prim	AlgorithmGraph::prim()	minimum spanning tree
Hungarian	AlgorithmGraph::hungarian()	solve unweighted bipartite graph matching problem; 中文博客
Kuhn-Munkras	AlgorithmGraph::km()	solve optimal weighted bipartite graph matching problem; 中文博客
Edmonds–Karp	AlgorithmGraph::EdmondKarp()	solve maximum flow problem; 中文博客

Utility

Name	Source	Comment
Timer	Timer.h Timer.cpp	calculate program execution time

License

See the LICENSE file for license rights and limitations.