字典树的基本知识及使用C语言的相关实现
|
概念 如果我们有and,as,at,cn,com这些关键词，那么trie树（字典树）是这样的：
从上面的图中，我们或多或少的可以发现一些好玩的特性。 第一：根节点不包含字符，除根节点外的每一个子节点都包含一个字符。 第二：从根节点到某一节点，路径上经过的字符连接起来，就是该节点对应的字符串。 第三：每个单词的公共前缀作为一个字符节点保存。
使用范围 既然学Trie树，我们肯定要知道这玩意是用来干嘛的。 第一：词频统计。 可能有人要说了，词频统计简单啊，一个hash或者一个堆就可以打完收工，但问题来了，如果内存有限呢？还能这么 玩吗？所以这里我们就可以用trie树来压缩下空间，因为公共前缀都是用一个节点保存的。 第二: 前缀匹配 就拿上面的图来说吧，如果我想获取所有以"a"开头的字符串，从图中可以很明显的看到是：and,at，如果不用trie树， 你该怎么做呢？很显然朴素的做法时间复杂度为O(N2) ，那么用Trie树就不一样了，它可以做到h，h为你检索单词的长度， 可以说这是秒杀的效果。 数据结构定义
#define MAX 26 // 字符集大小
typedef struct trieNode {
struct trieNode *next[MAX];
int count; // 记录该字符出现次数
} trieNode;
初始化根结点
/**
* 初始化Trie树根结点
*/
void initTrie(trieNode **root)
{
int i;
*root = (trieNode *)malloc(sizeof(trieNode));
(*root)->count = 0;
for (i = 0; i < MAX; i ++) {
(*root)->next[i] = NULL;
}
}
插入单词到trie树
/**
* Trie树插入操作
*/
void insert(char *str,trieNode *root)
{
int i;
trieNode *p = root;
while (*str != ' ') {
if (p->next[*str - 'a'] == NULL) {
trieNode *tmp = (trieNode *)malloc(sizeof(trieNode));
for (i = 0; i < MAX; i ++) {
tmp->next[i] = NULL;
}
tmp->count = 1;
p->next[*str - 'a'] = tmp;
p = p->next[*str - 'a'];
} else {
p = p->next[*str - 'a'];
p->count ++;
}
str ++;
}
}
统计查找单词数量
/**
* 统计前缀出现次数
*/
int count(char *search,trieNode *root)
{
trieNode *p = root;
while (*search != ' ') {
if (p->next[*search - 'a'] == NULL) {
return 0;
} else {
p = p->next[*search - 'a'];
search ++;
}
}
return p->count;
}
/**
* 清理trie树
*/
void delTrie(trieNode *root)
{
int i;
for (i = 0; i < MAX; i ++) {
if (root->next[i] != NULL) {
delTrie(root->next[i]);
}
}
free(root);
}
时间复杂度 空间复杂度较高，O(26^n),典型空间换时间
ac代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 26 // 字符集大小
typedef struct trieNode {
struct trieNode *next[MAX];
int count; // 记录该字符出现次数
} trieNode;
/**
* 初始化Trie树根结点
*/
void initTrie(trieNode **root)
{
int i;
*root = (trieNode *)malloc(sizeof(trieNode));
(*root)->count = 0;
for (i = 0; i < MAX; i ++) {
(*root)->next[i] = NULL;
}
}
/**
* Trie树插入操作
*/
void insert(char *str,trieNode *root)
{
int i;
trieNode *p = root;
while (*str != ' ') {
if (p->next[*str - 'a'] == NULL) {
trieNode *tmp = (trieNode *)malloc(sizeof(trieNode));
for (i = 0; i < MAX; i ++) {
tmp->next[i] = NULL;
}
tmp->count = 1;
p->next[*str - 'a'] = tmp;
p = p->next[*str - 'a'];
} else {
p = p->next[*str - 'a'];
p->count ++;
}
str ++;
}
}
/**
* 统计前缀出现次数
*/
int count(char *search,trieNode *root)
{
trieNode *p = root;
while (*search != ' ') {
if (p->next[*search - 'a'] == NULL) {
return 0;
} else {
p = p->next[*search - 'a'];
search ++;
}
}
return p->count;
}
/**
* 清理trie树
*/
void delTrie(trieNode *root)
{
int i;
for (i = 0; i < MAX; i ++) {
if (root->next[i] != NULL) {
delTrie(root->next[i]);
}
}
free(root);
}
int main(void)
{
char str[15];
trieNode *root;
// 初始化根结点
initTrie(&root);
while (gets(str) && str[0] != ' ') {
// 插入Trie树
insert(str,root);
}
// 查找前缀出现次数
while (gets(str) && str[0] != ' ') {
printf("%dn",count(str,root));
}
delTrie(root);
return 0;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
