DataStructureAndAlgorithm

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

Compile and Run

$ cd src
$ make
$ make run
$ make clean

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
N-Puzzle Problem	NPuzzle.h NPuzzle.cpp	can search 240 nodes per millisecond in average(5*5 puzzle; compiler: g++ -O2) (GUI demo, 中文博客)
Sorting	SortHelper.h	classic sorting algorithms
Random Generation	RandomEngine.h RandomEngine.cpp	pseudorandom number generation
Arithmetic Expression	ArithmeticExpression.h ArithmeticExpression.cpp	arithemetic expression calculation
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(KM)	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

Copyright 2016 ChuyangLiu

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.