xtaci/algorithms

Algorithms & Data structures in C++.

Algorithms & Data Structures in C++

目标 ( 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:

已实现 ( Implemented ):

Name	File
Array shuffle	https://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 Array	https://github.com/xtaci/algorithms/blob/master/include/2darray.h
Arbitrary Integer	https://github.com/xtaci/algorithms/blob/master/include/integer.h
Linear congruential generator	https://github.com/xtaci/algorithms/blob/master/include/random.h
Maximum subarray problem	https://github.com/xtaci/algorithms/blob/master/include/max_subarray.h
Bit-Set	https://github.com/xtaci/algorithms/blob/master/include/bitset.h
Queue	https://github.com/xtaci/algorithms/blob/master/include/queue.h
Stack	https://github.com/xtaci/algorithms/blob/master/include/stack.h
Binary Heap	https://github.com/xtaci/algorithms/blob/master/include/heap.h
Fibonacci Heap	https://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 sort	https://github.com/xtaci/algorithms/blob/master/include/bubble_sort.h
Selection sort	https://github.com/xtaci/algorithms/blob/master/include/selection_sort.h
Insertion sort	https://github.com/xtaci/algorithms/blob/master/include/insertion_sort.h
Shell sort	https://github.com/xtaci/algorithms/blob/master/include/shell_sort.h
Radix sort	https://github.com/xtaci/algorithms/blob/master/include/radix_sort.h
Quicksort	https://github.com/xtaci/algorithms/blob/master/include/quick_sort.h
Merge sort	https://github.com/xtaci/algorithms/blob/master/include/merge_sort.h
Double linked list	https://github.com/xtaci/algorithms/blob/master/include/double_linked_list.h
Skip list	https://github.com/xtaci/algorithms/blob/master/include/skiplist.h
Largest common sequence	https://github.com/xtaci/algorithms/blob/master/include/lcs.h
Binary search tree	https://github.com/xtaci/algorithms/blob/master/include/binary_search_tree.h
AVL tree	https://github.com/xtaci/algorithms/blob/master/include/avl.h
Dynamic order statistics	https://github.com/xtaci/algorithms/blob/master/include/dos_tree.h
Red-black tree	https://github.com/xtaci/algorithms/blob/master/include/rbtree.h
Interval tree	https://github.com/xtaci/algorithms/blob/master/include/interval_tree.h
Prefix Tree(Trie)	https://github.com/xtaci/algorithms/blob/master/include/trie.h
Suffix Tree	https://github.com/xtaci/algorithms/blob/master/include/suffix_tree.h
B-Tree	https://github.com/xtaci/algorithms/blob/master/include/btree.h
Suffix Array	https://github.com/xtaci/algorithms/blob/master/include/suffix_array.h
Hash by multiplication	https://github.com/xtaci/algorithms/blob/master/include/hash_multi.h
Hash table	https://github.com/xtaci/algorithms/blob/master/include/hash_table.h
Universal hash function	https://github.com/xtaci/algorithms/blob/master/include/universal_hash.h
Perfect hash	https://github.com/xtaci/algorithms/blob/master/include/perfect_hash.h
Java's string hash	https://github.com/xtaci/algorithms/blob/master/include/hash_string.h
FNV-1a string hash	https://github.com/xtaci/algorithms/blob/master/include/hash_string.h
SimHash	https://github.com/xtaci/algorithms/blob/master/include/simhash.h
Bloom Filter	https://github.com/xtaci/algorithms/blob/master/include/bloom_filter.h
SHA-1 Message Digest Algorithm	https://github.com/xtaci/algorithms/blob/master/include/sha1.h
MD5	https://github.com/xtaci/algorithms/blob/master/include/md5.h
Base64	https://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 tree	https://github.com/xtaci/algorithms/blob/master/include/prim_mst.h
Kruskal MST	https://github.com/xtaci/algorithms/blob/master/include/kruskal_mst.h
Breadth First Search	https://github.com/xtaci/algorithms/blob/master/include/graph_search.h
Depth First Search	https://github.com/xtaci/algorithms/blob/master/include/graph_search.h
Dijkstra's algorithm	https://github.com/xtaci/algorithms/blob/master/include/dijkstra.h
Bellman-Ford algorithm	https://github.com/xtaci/algorithms/blob/master/include/bellman_ford.h
Edmonds-Karp Maximal Flow	https://github.com/xtaci/algorithms/blob/master/include/edmonds_karp.h
Push–Relabel algorithm	https://github.com/xtaci/algorithms/blob/master/include/relabel_to_front.h
Huffman Coding	https://github.com/xtaci/algorithms/blob/master/include/huffman.h
Word segementation	https://github.com/xtaci/algorithms/blob/master/include/word_seg.h
A* algorithm	https://github.com/xtaci/algorithms/blob/master/include/astar.h
K-Means	https://github.com/xtaci/algorithms/blob/master/include/k-means.h
Knuth–Morris–Pratt algorithm	https://github.com/xtaci/algorithms/blob/master/include/kmp.h
Disjoint-Set	https://github.com/xtaci/algorithms/blob/master/include/disjoint-set.h
8-Queen Problem	https://github.com/xtaci/algorithms/blob/master/include/8queen.h
Palindrome	https://github.com/xtaci/algorithms/blob/master/include/palindrome.h
LCA using Binary Lifting	https://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

algorithms's Issues

LRU算法链表名称问题

个人觉得链表的头和尾p_cache_list_head, p_cache_list_near
用类似p_cache_list_head, p_cache_list_tail
或者 p_cache_list_front, p_cache_list_rear感觉更好些
p_cache_list_near的意思读起来不是很清晰

Add Backtracking

Backtracking is not present.
Backtracking is an algorithmic-technique for solving problems recursively by trying to build a solution incrementally.

Swapped indexes in astar.h

Hey man, while using your fantastic rep I encountered a bug in the astar header, in particular the indexing of the grid in the neighbor search when using nx,ny and cx,cy where swapped. That was causing the algorithm to search blocks that could be occupied by walls if the map was different from the sample one. I'm using your astar header in one of my repositories, so if you want feel free to have a look at the changes I've done 😉

I'm not using the github tools to fork the rep and request a merge since I'm somehow new to git and I don't want to create a mess 👅

Conform to C++ standard

Hi,
this is an awesome repository which contains a lot of useful algorithms for C++, but the code style, I think, could be improved:

• Use <cstddef> instead of <stddef.h>
• each identifier with two underscores at the beginning(__foobar) or one underscore followed by character in uppercase(_Foobar) is reserved by language
• the void keyword could be omitted inint main(void), so is struct in struct Foo obj

Segregated code

After looking at this project i want to say that this project is good for the one who is learning algorithm. The only opinion i could give right now is that if possible we could segregate the implementations in include directory( only contains the declarations ) and move it to .cpp file( some src directory). It not only helps in readability of the code but also the compile time could increase.

cmake build not working

Hi, I found this repo interesting to contribute with some of my data structures and C++ implementations of algorithms, but I can only build the demos using the UNIX makefile. For some reason, the cmake project
setup is broken and it fails after running the Makefile generated by cmake.

I think it's because the include folders are not set accordingly. I'll try to fix it myself before adding my code. If I succeed, I'll send you my pull request. Thanks for the great work!

Queue& needs to be const as well

algorithms/include/queue.h

Line 63 in 2ac19a7

Queue& operator=(const Queue &);

You probably need to make the returned alias to be const as well.
For info, check the (x = y) = z problem...

I can't compile kruskal_mst.h.

Look this.
I can't compile kruskal_mst.h.
Who can help me?

Message:
/home/yangjz/code/forkprojects/algorithms/include/kruskal_mst.h: In member function ‘alg::Graph* alg::Kruskal::run()’:
/home/yangjz/code/forkprojects/algorithms/include/kruskal_mst.h:143:41: error: ‘class alg::Heapalg::Graph::Vertex*’ has no member named ‘min_key’
if(!pa->heap.is_empty()&&pa->heap.min_key()<weight) {
^~~~~~~
/home/yangjz/code/forkprojects/algorithms/include/kruskal_mst.h:144:26: error: ‘class alg::Heapalg::Graph::Vertex*’ has no member named ‘min_key’
weight = pa->heap.min_key();
^~~~~~~
/home/yangjz/code/forkprojects/algorithms/include/kruskal_mst.h:145:21: error: ‘class alg::Heapalg::Graph::Vertex*’ has no member named ‘min_value’
v = pa->heap.min_value();
^~~~~~~~~
/home/yangjz/code/forkprojects/algorithms/include/kruskal_mst.h:174:23: error: ‘class alg::Heapalg::Graph::Vertex*’ has no member named ‘delete_min’
best_from->heap.delete_min();
^~~~~~~~~~
/home/yangjz/code/forkprojects/algorithms/include/kruskal_mst.h:175:29: error: ‘class alg::Heapalg::Graph::Vertex*’ has no member named ‘delete_min’
lookup(best_to)->heap.delete_min();
^~~~~~~~~~
/home/yangjz/code/forkprojects/algorithms/include/kruskal_mst.h: In member function ‘void alg::Kruskal::print()’:
/home/yangjz/code/forkprojects/algorithms/include/kruskal_mst.h:191:35: error: no match for ‘operator[]’ (operand types are ‘alg::Heapalg::Graph::Vertex*’ and ‘uint32_t {aka unsigned int}’)
Graph::Vertex * v = pa->heap[i];

Added MSVC support

https://github.com/Samana

samana added support for msvc... really great work!

thanks...

How do i start contributing ?

Hello , I am new to the Github and i have decent knowledge about the data structures and algorithms . How can i start contributing ?

Build error gcc (GCC) 6.1.1 20160501

Hello,

first of all, this is a great compilation of non-trivial algorithms ... thank you for putting it together.

secondly, I get this build error for suffix_tree in my environment.
most probably compiler dependent issues.
I will look into it and if i fix it I will send a pull request from a fork.

In file included from src/suffix_tree_demo.cpp:1:0:
./include/suffix_tree.h: In member function ‘Iterator SuffixTree::inc_search(Iterator)’:
./include/suffix_tree.h:34:41: warning: typedef ‘T’ locally defined but not used [-Wunused-local-typedefs]
typedef typename Iterator::value_type T; // extract real type
^
./include/suffix_tree.h: In function ‘std::ostream& operator<<(std::ostream&, SuffixTree::Node&)’:
./include/suffix_tree.h:214:8: error: ‘typedef struct SuffixTree::Edge SuffixTree::Edge’ is private within this context
map<Edge*, bool>::iterator iter;
^~~~
./include/suffix_tree.h:149:22: note: declared private here
typedef struct Edge Edge;
^~~~
./include/suffix_tree.h:215:14: error: ‘typedef struct SuffixTree::Edge SuffixTree::Edge’ is private within this context
map<char, Edge*>::iterator iter_f;
^~~~
./include/suffix_tree.h:149:22: note: declared private here
typedef struct Edge Edge;
^~~~
src/suffix_tree_demo.cpp: At global scope:
src/suffix_tree_demo.cpp:107:70: error: no ‘SuffixTree::Node* SuffixTree::seperate_edge(SuffixTree::Node_, SuffixTree::Edge_)’ member function declared in class ‘SuffixTree’
SuffixTree::Node* SuffixTree::seperate_edge(Node * node, Edge* a_edge)
^
src/suffix_tree_demo.cpp:107:13: error: ‘typedef struct SuffixTree::Node SuffixTree::Node’ is private within this context
SuffixTree::Node* SuffixTree::seperate_edge(Node * node, Edge* a_edge)
^~~~
In file included from src/suffix_tree_demo.cpp:1:0:
./include/suffix_tree.h:81:22: note: declared private here
typedef struct Node Node;
^~~~
src/suffix_tree_demo.cpp:107:58: error: ‘typedef struct SuffixTree::Edge SuffixTree::Edge’ is private within this context
SuffixTree::Node* SuffixTree::seperate_edge(Node * node, Edge* a_edge)
^~~~
In file included from src/suffix_tree_demo.cpp:1:0:
./include/suffix_tree.h:149:22: note: declared private here
typedef struct Edge Edge;
^~~~
Makefile:257: recipe for target 'suffix_tree_demo' failed
make: *** [suffix_tree_demo] Error 1

RANDOM has some problems

define RANDOM(L, R) (L + rand() % ((R) - (L))) // gen a random integer in [L, R]

I think the RANDOM cannot get R, it should be (L + rand() % ((R) - (L) + 1))

Makefile

makefile creates many unused files. use *.o to remove those files

skiplist

memset(update, 0, SL_MAX_LEVEL + 1);
error size isn't it ?

and make_node use 0 to build a value that may not init with arg 0

I think it needs a make file. Compilation keeps failing on different files every time.

快速排序枢纽值pivot的选择不是最高效的.

In https://github.com/xtaci/algorithms/blob/master/include/quick_sort.h

在目前（2013年10月21日 16时12分55秒）快速排序算法的实现中，枢纽值pivot是通过随机数选取的，即int pivot_idx = RANDOM(begin,end);但这不是最高效的枢纽选择策略。
对快速排序效率影响最大的是枢纽值pivot的选择，建议采取首值、中间值和末尾值进行比较，选择中间大小的那个值作为枢纽值pivot策略。这样在数据量大的情况下，排序效果会更加高效。

可以详见博客描述：http://blog.csdn.net/nwpu_kexie/article/details/7538673

Initializing unsigned value with a negative number.

Hello,
In "queue.h"
We use uint32_t for m_front and m_rear and other member variables.
However in constructor, we are assigning m_rear as -1.
I understand the purpose of assigning it -1, as we want to enqueue first element at m_rear = 0 and we increment m_rear with each enqueue operation.
Although, the code behaves right, as assigning -1 would overflow it to UMAX and then adding 1 to it will bring it back to 0. I just wanted to understand the purpose of declaring it uint32_t instead of simple integer.

Your repository is really awesome, learning a lot from it.

Thanks

double linked list demo 失败

hi，各位：
我的代码环境：g++ 4.8.4, Ubuntu 14.04.6，kernel 4.4.0-148-generic
失败的地方是在 src/double_linked_list_demo.cpp 中的代码：

	list_for_each_prev(pos, &head){
		struct DemoNode * node = list_entry(pos, struct DemoNode, list);
		printf("%d\n", node->key);
	}
	
	list_for_each_entry(node, &head, list){
		printf("%d\n", node->key);
	}

上面demo 示例，list_for_each_prev 中，list_entry中的type 参数是struct DemoNode， 但在 list_for_each_entry 中使用 typeof(*pos) (也就是decltype(*pos) ) ， 它返回的type 为 struct DemoNode& ， 也就导致编译失败。我做了下面的简单修复.

其中原来的 list_for_each_entry 的实现

#ifndef _MSC_VER
#define list_for_each_entry(pos, head, member)				\
	for (pos = list_entry((head)->next, typeof(*pos), member);	\
	     &pos->member != (head); 					\
	     pos = list_entry(pos->member.next, typeof(*pos), member))
#else
#define list_for_each_entry(pos, head, member)				\
	for (pos = list_entry((head)->next, typeof(pos), member);	\
	     &pos->member != (head); 					\
	     pos = list_entry(pos->member.next, typeof(pos), member))
#endif

修复：

#define list_for_each_entry(pos, head, member)               \
  for (pos = list_entry_ptr((head)->next, typeof(pos), member); \
       &pos->member != (head);                               \
       pos = list_entry_ptr(pos->member.next, typeof(pos), member))

#define list_entry_ptr(ptr, ptrtype, member) \
  (reinterpret_cast<ptrtype>(            \
      (char *)(ptr) - (char *)(&(reinterpret_cast<ptrtype>(1)->member)) + 1))

build failed on Ubuntu

Error message is like following.

c++: error: /FImsvc/alg_vs.h: 没有那个文件或目录
CMakeFiles/astar_demo.dir/build.make:62: recipe for target 'CMakeFiles/astar_demo.dir/src/astar_demo.cpp.o' failed
make[3]: *** [CMakeFiles/astar_demo.dir/src/astar_demo.cpp.o] Error 1
CMakeFiles/Makefile2:992: recipe for target 'CMakeFiles/astar_demo.dir/all' failed
make[2]: *** [CMakeFiles/astar_demo.dir/all] Error 2
CMakeFiles/Makefile2:1004: recipe for target 'CMakeFiles/astar_demo.dir/rule' failed
make[1]: *** [CMakeFiles/astar_demo.dir/rule] Error 2
Makefile:443: recipe for target 'astar_demo' failed
make: *** [astar_demo] Error 2

Having looked through the CmakeList.txt, it seams that the default msvc building option is not open.
So how to build on Ubuntu/Linux?
I am new to Cmake, could you tell me how to fix this?

use cmake build repo and integrate ctest, I can help with refactoring

k-means need more comments

ok, i merge k-means , great job!!!

i think adding more comments for k-means functions will be helpful for successor.

Typo

8-Queen Problem was typed "8-Queue Problem" in README.md.

The miller_rabin_test function in the prime header seems to be wrong, and I can't draw the correct conclusion

That's a terrible question

sort_demo,exception error

in sort _demo.cpp
i find a exception error named std::out_of_range when i run the program.
exactlly,there are something wrong in the heap sort which is about std::vector's using.

This contain the circular queue operation. [ Inserting an element and deletion of element]

include<stdio.h>

include<stdlib.h>

int ch,i,item,f=0,r=0,q[5],max=5,c=0;
void insert();
void Delete();
void display();
void main()
{
for(;;)
{
printf("\n\tMENU\n1.INSERT\n2.DELETE\n3.DISPLAY\n4.EXIT\n");
printf("Enter your Choice\n");
scanf("%d", &ch);
switch(ch)
{
case 1: insert();
display();
break;
case 2: Delete();
display();
break;
case 3: display();
break;
case 4: exit(0);

         default: printf("Invalid Input\n");
    }
}

}
void insert()
{
if(f==r && c==max)
{
printf("Insertion not possible, due to overflow\n");
}
else
{
printf("Enter the element to be inserted\n");
scanf("%d", &item);
q[r]=item;
r=(r+1)%max;
c++;
}
}
void Delete()
{
if(f==r && c==0)
{
printf("Deletion is not possible, due to underflow\n");
}
else
{
printf("The item deleted is %d\n",q[f]);
f=(f+1)%max;
c--;
}
}
void display()
{
printf("The circular queue is \n");
for(i=f;i<c+f;i++)
{
printf("%d",q[i]);

 }

}