这篇文章主要介绍了字典树的基本知识及使用C语言的相关实现,这也是ACM等计算机考试和竞赛题目的基本知识,需要的朋友可以参考下
概念
如果我们有and,as,at,cn,com这些关键词，那么trie树（字典树）是这样的：
从上面的图中，我们或多或少的可以发现一些好玩的特性。
第一：根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
第二：从根节点到某一节点，路径上经过的字符连接起来，就是该节点对应的字符串。
第三：每个单词的公共前缀作为一个字符节点保存。
使用范围
既然学Trie树，我们肯定要知道这玩意是用来干嘛的。
第一：词频统计。
可能有人要说了，词频统计简单啊，一个hash或者一个堆就可以打完收工，但问题来了，如果内存有限呢？还能这么
玩吗？所以这里我们就可以用trie树来压缩下空间，因为公共前缀都是用一个节点保存的。
第二: 前缀匹配
就拿上面的图来说吧，如果我想获取所有以”a”开头的字符串，从图中可以很明显的看到是：and,as,at，如果不用trie树，
你该怎么做呢？很显然朴素的做法时间复杂度为O(N2) ，那么用Trie树就不一样了，它可以做到h，h为你检索单词的长度，
可以说这是秒杀的效果。
数据结构定义
#define MAX 26 // 字符集大小 typedef struct trieNode { struct trieNode *next[MAX]; int count; // 记录该字符出现次数 } trieNode;
next数组表示每层有多少类的数，如果只是小写字母，26即可
实现方法
搜索字典项目的方法：
- 从根节点开始一次搜索
- 获取要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索
- 在相应的子树上，获取要查找关键词的第二个字母，并进一步选择对应的子树进行检索
- 迭代过程
- 在某个节点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找
其他操作类似
实现模板
初始化根结点
/** * 初始化Trie树根结点 */ void initTrie(trieNode **root) { int i; *root = (trieNode *)malloc(sizeof(trieNode)); (*root)->count = 0; for (i = 0; i next[i] = NULL; } }
插入单词到trie树
/** * Trie树插入操作 */ void insert(char *str, trieNode *root) { int i; trieNode *p = root; while (*str != '\0') { if (p->next[*str - 'a'] == NULL) { trieNode *tmp = (trieNode *)malloc(sizeof(trieNode)); for (i = 0; i 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 != '\0') { if (p->next<b style="color:transparent">来源gao@dai!ma.com搞$代^码网</b>[*search - 'a'] == NULL) { return 0; } else { p = p->next[*search - 'a']; search ++; } } return p->count; }
清理trie树
/** * 清理trie树 */ void delTrie(trieNode *root) { int i; for (i = 0; i next[i] != NULL) { delTrie(root->next[i]); } } free(root); }
时间复杂度
插入、查找的时间复杂度均为O(n),n为字符串的长度
空间复杂度较高，O(26^n),典型空间换时间
参考题目
ac代码：
#include #include #include #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 next[i] = NULL; } } /** * Trie树插入操作 */ void insert(char *str, trieNode *root) { int i; trieNode *p = root; while (*str != '\0') { if (p->next[*str - 'a'] == NULL) { trieNode *tmp = (trieNode *)malloc(sizeof(trieNode)); for (i = 0; i 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 != '\0') { 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 next[i] != NULL) { delTrie(root->next[i]); } } free(root); } int main(void) { char str[15]; trieNode *root; // 初始化根结点 initTrie(&root); while (gets(str) && str[0] != '\0') { // 插入Trie树 insert(str, root); } // 查找前缀出现次数 while (gets(str) && str[0] != '\0') { printf("%d\n", count(str, root)); } delTrie(root); return 0; }
以上就是字典树的基本知识及使用C语言的相关实现的详细内容，更多请关注gaodaima搞代码网其它相关文章！
转载请注明原文链接：字典树的基本知识及使用C语言的相关实现
