Algorithms & Data structures in C++.

In graph theory and computer science, the lowest common ancestor (LCA) of two nodes v and w in a tree or directed a cyclic graph (DAG) T is the lowest (i.e. deepest) node that has both v and w as descendants, where we define each node to be a descendant of itself (so if v has a direct connection from w, w is the lowest common ancestor).

There's many methods to find the LCA, one can be using Euler tour and a segment tree or by using Binary lifting which is the implemented method.

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

INPUT: Man is distinguished not only by his reason, but by this singular passion from other animals, which is a lust of the mind, that by a perseverance of delight in the continued and indefatigable generation of knowledge, exceeds the short vehemence of any carnal pleasure..

encodeBase64: TWFuIGlzIGRpc3Rpbmd1aXNoZWQgbm90IG9ubHkgYnkgaGlzIHJlYXNvbiwgYnV0IGJ5IHRoaXMgc2luZ3VsYXIgcGFzc2lvbiBmcm9tIG90aGVyIGFuaW1hbHMsIHdoaWNoIGlzIGEgbHVzdCBvZiB0aGUgbWluZCwgdGhhdCBieSBhIHBlcnNldmVyYW5jZSBvZiBkZWxpZ2h0IGluIHRoZSBjb250aW51ZWQgYW5kIGluZGVmYXRpZ2FibGUgZ2VuZXJhdGlvbiBvZiBrbm93bGVkZ2UsIGV4Y2VlZHMgdGhlIHNob3J0IHZlaGVtZW5jZSBvZiBhbnkgY2FybmFsIHBsZWFzdXJlLi4=

decodeBase64: Man is distinguished not only by his reason, but by this singular passion from other animals, which is a lust of the mind, that by a perseverance of delight in the continued and indefatigable generation of knowledge, exceeds the short vehemence of any carnal pleasure..

It's not making any sense to use typeof(i) to define length, since 'i' is obviously a 'int'. And it's probably not a good idea to put the choose pivot function in a separate file, this will force user to call srand() unnaturally.

https://github.com/xtaci/algorithms/blob/2ac19a715c06f2578c7ebbc201fff6c763320579/include/queue.h#L63

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

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.

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

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

Hi, I added a generic AVL tree. I saw there is already an RBTree structure in the repo and uses key/value pairs. In my case, I think AVL trees are not only for dictionaries with key/value pairs. However, the same behavior can be achieved by making the elements in the AVL a key/value pair and redefining the ordering operators, just like when using an std::set.

The AVL is more balanced than a RBT but it takes a bit longer to insert/delete elements due to the rotations. So it's faster for searching but slower for the rest.

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 :wink:

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 :tongue:

个人觉得链表的头和尾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的意思读起来不是很清晰

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))