Monthly Archives: September 2010

Double-Array Trie举例

Posted on 2010/09/15 by admin

下面我先画一个图来说明字典的构成. 1.假设我们有词典如下

Posted in 算法与数据结构 | Tagged , , , , | 1 Comment

并查集（等价类）及其实现

Posted on 2010/09/03 by admin

并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。 进行快速规整。

Posted in 算法与数据结构 | Tagged , , , , | Comments Off

线段树及其实现

Posted on 2010/09/03 by admin

线段树是二叉搜索树的一种。与一般的二叉搜索树不同的是，线段树保存的是所有元素可能取的值，而不是每个元素。通常情况下，线段树只用叶节点表示每个值。而其余的节点对应的就是一个范围。由于线段树所保存的节点是固定的，所以可以直接在开始的时候做成一个比较完美的二叉树，而不需要自平衡的操作。对于比较小的数据，这个二叉树通常能像完全二叉树一样，直接保存在一维数组中。

Posted in 算法与数据结构 | Tagged , , , | Comments Off

约瑟环问题-O(n)

Posted on 2010/09/02 by admin

约瑟环问题: 将n个孩子从1到n编上号，按序号围坐成一个圈，从1号孩子开始数，每数到m时，被数到的孩子即离开圈子，然后从下一个孩子开始，再从1开始数，如此不断地数下去，只到只剩下最后一个孩子，问剩下的孩子是几号？

Posted in C / C++, 算法与数据结构 | Tagged , , , | Comments Off