Home

Awesome

Algorithms & Data Structures in C++

Build Status

目标 ( goal ) :

  1. 经典的算法实现
    (classical algorithms implementations)
  2. 服务器端
    (based on linux/gcc)
  3. 正确，易于使用和改造, 一个头文件一个算法，并附带一个demo.
    (correct! and ease of use, one .header file per algorithm)

约定 ( Convention ):

  1. 一个算法用一个.h文件表示放到include下. ( one .header file per algorithm. )
  2. 算法演示的demo程序放到src下. ( one demo per algorithm. )
  3. 程序正确通过后，请发起Pull Requests，代码被验证后入库，并在README中发布新算法实现。 (Please Use Fork+Pull Requests !!! Correctness is the most important!)
  4. TAB = 4 space. set ts=4 in vim
  5. Graph的输出格式为 Graphviz Dot格式. (the output format of the graph is in dot of graphviz.) eg: demograph

已实现 ( Implemented ):

NameFile
Array shufflehttps://github.com/xtaci/algorithms/blob/master/include/shuffle.h
Prime test(trial division)https://github.com/xtaci/algorithms/blob/master/include/prime.h
Prime test(Miller-Rabin's method)https://github.com/xtaci/algorithms/blob/master/include/prime.h
2D Arrayhttps://github.com/xtaci/algorithms/blob/master/include/2darray.h
Arbitrary Integerhttps://github.com/xtaci/algorithms/blob/master/include/integer.h
Linear congruential generatorhttps://github.com/xtaci/algorithms/blob/master/include/random.h
Maximum subarray problemhttps://github.com/xtaci/algorithms/blob/master/include/max_subarray.h
Bit-Sethttps://github.com/xtaci/algorithms/blob/master/include/bitset.h
Queuehttps://github.com/xtaci/algorithms/blob/master/include/queue.h
Stackhttps://github.com/xtaci/algorithms/blob/master/include/stack.h
Binary Heaphttps://github.com/xtaci/algorithms/blob/master/include/heap.h
Fibonacci Heaphttps://github.com/xtaci/algorithms/blob/master/include/fib-heap.h
Priority Queue (list based)https://github.com/xtaci/algorithms/blob/master/include/priority_queue.h
Bubble sorthttps://github.com/xtaci/algorithms/blob/master/include/bubble_sort.h
Selection sorthttps://github.com/xtaci/algorithms/blob/master/include/selection_sort.h
Insertion sorthttps://github.com/xtaci/algorithms/blob/master/include/insertion_sort.h
Shell sorthttps://github.com/xtaci/algorithms/blob/master/include/shell_sort.h
Radix sorthttps://github.com/xtaci/algorithms/blob/master/include/radix_sort.h
Quicksorthttps://github.com/xtaci/algorithms/blob/master/include/quick_sort.h
Merge sorthttps://github.com/xtaci/algorithms/blob/master/include/merge_sort.h
Double linked listhttps://github.com/xtaci/algorithms/blob/master/include/double_linked_list.h
Skip listhttps://github.com/xtaci/algorithms/blob/master/include/skiplist.h
Largest common sequencehttps://github.com/xtaci/algorithms/blob/master/include/lcs.h
Binary search treehttps://github.com/xtaci/algorithms/blob/master/include/binary_search_tree.h
AVL treehttps://github.com/xtaci/algorithms/blob/master/include/avl.h
Dynamic order statisticshttps://github.com/xtaci/algorithms/blob/master/include/dos_tree.h
Red-black treehttps://github.com/xtaci/algorithms/blob/master/include/rbtree.h
Interval treehttps://github.com/xtaci/algorithms/blob/master/include/interval_tree.h
Prefix Tree(Trie)https://github.com/xtaci/algorithms/blob/master/include/trie.h
Suffix Treehttps://github.com/xtaci/algorithms/blob/master/include/suffix_tree.h
B-Treehttps://github.com/xtaci/algorithms/blob/master/include/btree.h
Suffix Arrayhttps://github.com/xtaci/algorithms/blob/master/include/suffix_array.h
Hash by multiplicationhttps://github.com/xtaci/algorithms/blob/master/include/hash_multi.h
Hash tablehttps://github.com/xtaci/algorithms/blob/master/include/hash_table.h
Universal hash functionhttps://github.com/xtaci/algorithms/blob/master/include/universal_hash.h
Perfect hashhttps://github.com/xtaci/algorithms/blob/master/include/perfect_hash.h
Java's string hashhttps://github.com/xtaci/algorithms/blob/master/include/hash_string.h
FNV-1a string hashhttps://github.com/xtaci/algorithms/blob/master/include/hash_string.h
SimHashhttps://github.com/xtaci/algorithms/blob/master/include/simhash.h
Bloom Filterhttps://github.com/xtaci/algorithms/blob/master/include/bloom_filter.h
SHA-1 Message Digest Algorithmhttps://github.com/xtaci/algorithms/blob/master/include/sha1.h
MD5https://github.com/xtaci/algorithms/blob/master/include/md5.h
Base64https://github.com/xtaci/algorithms/blob/master/include/base64.h
Strongly Connected Components(SCC)https://github.com/xtaci/algorithms/blob/master/include/scc.h
Prim's minimum spanning treehttps://github.com/xtaci/algorithms/blob/master/include/prim_mst.h
Kruskal MSThttps://github.com/xtaci/algorithms/blob/master/include/kruskal_mst.h
Breadth First Searchhttps://github.com/xtaci/algorithms/blob/master/include/graph_search.h
Depth First Searchhttps://github.com/xtaci/algorithms/blob/master/include/graph_search.h
Dijkstra's algorithmhttps://github.com/xtaci/algorithms/blob/master/include/dijkstra.h
Bellman-Ford algorithmhttps://github.com/xtaci/algorithms/blob/master/include/bellman_ford.h
Edmonds-Karp Maximal Flowhttps://github.com/xtaci/algorithms/blob/master/include/edmonds_karp.h
Push–Relabel algorithmhttps://github.com/xtaci/algorithms/blob/master/include/relabel_to_front.h
Huffman Codinghttps://github.com/xtaci/algorithms/blob/master/include/huffman.h
Word segementationhttps://github.com/xtaci/algorithms/blob/master/include/word_seg.h
A* algorithmhttps://github.com/xtaci/algorithms/blob/master/include/astar.h
K-Meanshttps://github.com/xtaci/algorithms/blob/master/include/k-means.h
Knuth–Morris–Pratt algorithmhttps://github.com/xtaci/algorithms/blob/master/include/kmp.h
Disjoint-Sethttps://github.com/xtaci/algorithms/blob/master/include/disjoint-set.h
8-Queen Problemhttps://github.com/xtaci/algorithms/blob/master/include/8queen.h
Palindromehttps://github.com/xtaci/algorithms/blob/master/include/palindrome.h
LCA using Binary Liftinghttps://github.com/xtaci/algorithms/blob/master/include/LCA.h

贡献者 ( Contributors ) :

Samana:  for heavy work of MSVC compatability
wycg1984: for K-Means
xmuliang: for HeapSort, Kruskal MST
wyh267: for base64, LRU, bubble sort, selection sort
ZhangYou0122: Push-Relabel algorithm, Suffix Tree           
UsingtcNower: Suffix Array
afernandez90: AVL trees