Trie树之01编码的前缀性
/**字典树——检测01编码是否具有前缀性
*Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的
*使得查询单词就是查字典一样。插入和删除跟查询有关。
*/
#include
#include
#include
#define CHAR_COUNT 2/** 字符的种类，也即单个节点的子树的最大个数，这里是01编码 */
#define MAX_CODE_LEN 10/** 编码的最大长度. */
/** 字典树的最大节点个数.每个 code 不超过 10bit，因此最大节点个数为 2^11-1*/
#define MAX_NODE_COUNT ((1<<(MAX_CODE_LEN+1))-1)
typedef enum {FALSE,TRUE} BOOLEAN;
/** 字典树的节点，包含CHAR_COUNT个指针和一个布尔值 */
typedef struct trie_node_t
{
struct trie_node_t* next[CHAR_COUNT];
BOOLEAN is_tail; /** 标记当前字符是否位于某个串的尾部 */
/** 这里要特别注意，当is_tail为真且next数组里的指针全部为空时，当前结点才是叶节点 */
} trie_node_t;
/** 字典树. */
typedef struct trie_tree_t
{
trie_node_t *root; /** 树的根节点 */
int size; /** 树中实际出现的节点数 */
/**开一个大数组，加快速度，否则要给每一个结点malloc CHAR_COUNT个空间 */
trie_node_t nodes[MAX_NODE_COUNT];
} trie_tree_t;
/** 创建一棵字典树. */
trie_tree_t* trie_tree_create(void)
{
trie_tree_t *tree = (trie_tree_t*)malloc(sizeof(trie_tree_t));
tree->root = &(tree->nodes[0]);
memset(tree->nodes, 0, sizeof(tree->nodes));
tree->size = 1;
return tree;
}
/** 销毁. */
void trie_tree_destroy(trie_tree_t *tree)
{
free(tree);
tree = NULL;
}
/** 将当前字典树中的所有节点信息清空 */
void trie_tree_clear(trie_tree_t *tree)
{
memset(tree->nodes, 0, sizeof(tree->nodes));
tree->size = 1; // 清空时一定要注意这一步!
}
/** 在当前树中插入 word 字符串
*返回值表示，该字典是否具有前缀性
*/
BOOLEAN trie_tree_insert(trie_tree_t *tree, char *word)
{
int i;
BOOLEAN ok=TRUE;
trie_node_t *p = tree->root;
while (*word)
{
int curword = *word - '0';
if (p->next[curword] == NULL)
p->next[curword] = &(tree->nodes[tree->size++]);//代替一次malloc
p = p->next[curword];
if (p->is_tail) ok=FALSE; // 某个串是插入串的前缀
word++; // 指针下移
}