字典树的基本知识及使用C语言的相关实现
概念
如果我们有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 < MAX; i ++) { (*root)->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 < 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 != '\0') { if (p->next[*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 < MAX; i ++) { if (root->next[i] != NULL) { delTrie(root->next[i]); } } free(root); }
时间复杂度
插入、查找的时间复杂度均为O(n),n为字符串的长度
空间复杂度较高,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 != '\0') { 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 != '\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 < 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] != '\0') { // 插入Trie树 insert(str, root); } // 查找前缀出现次数 while (gets(str) && str[0] != '\0') { printf("%d\n", count(str, root)); } delTrie(root); return 0; }
相关文章
- 这篇文章主要介绍了c++中system("pause")的作用和含义,非常不错,具有参考借鉴价值,需要的朋友参考下吧...2020-04-25
基于BootStrap Metronic开发框架经验小结【八】框架功能总体界面介绍
这篇文章主要介绍了基于BootStrap Metronic开发框架经验小结【八】框架功能总体界面介绍 的相关资料,需要的朋友可以参考下...2016-05-14- 这篇文章主要介绍了C# 16 进制字符串转 int的方法,非常不错,具有参考借鉴价值,需要的朋友可以参考下...2020-06-25
InterlliJ IDEA2020新建java web项目找不到Static Web的解决
这篇文章主要介绍了InterlliJ IDEA2020新建java web项目找不到Static Web的解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-09-02- 这篇文章主要介绍了C#判断一个字符串是否是数字或者含有某个数字的方法,本文给大家介绍的非常详细,具有一定的参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了C#类中static变量用法,实例分析了static变量使用技巧与相关注意事项,需要的朋友可以参考下...2020-06-25
- 这篇文章主要给大家介绍C# winform快捷键设置技巧,涉及到C winform快捷键相关知识,对C winform知识感兴趣的朋友可以参考下本篇文章...2020-06-25
- 最近项目不多忙,于是抽点时间巩固下切换窗口问题,感兴趣的朋友跟着小编一起学习吧...2020-06-25
- 这篇文章主要介绍了基于Ionic3实现选项卡切换并重新加载echarts,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-09-24
pytorch绘制并显示loss曲线和acc曲线,LeNet5识别图像准确率
今天小编就为大家分享一篇pytorch绘制并显示loss曲线和acc曲线,LeNet5识别图像准确率,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-05-02- 这篇文章主要为大家详细介绍了PC蓝牙通信C#代码实现,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-06-25
- 这篇文章主要介绍了C#实现带进度条的ListView 的相关资料,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了SpringMVC文件上传原理及实现过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-07-15
基于BootStrap Metronic开发框架经验小结【六】对话框及提示框的处理和优化
这篇文章主要介绍了基于BootStrap Metronic开发框架经验小结【六】对话框及提示框的处理和优化的相关知识,主要对比说明在Bootstrap开发中用到的这些技术要点,对此文感兴趣的朋友一起学习吧...2016-05-14- 这篇文章主要介绍了C#向线程中传递多个参数的解决方法(两种)的相关资料,非常不错,具有参考借鉴价值,需要的朋友可以参考下...2020-06-25
C# MVC模式中应该怎样区分应用程序逻辑(Controller层)和业务逻辑(Model层)?
这篇文章主要介绍了C# MVC模式中应该怎样区分应用程序逻辑(Controller层)和业务逻辑(Model层)?,这也小编做.NET项目时经常思考和让人混乱的一个问题,这篇文章写的挺好,一下清晰了许多,需要的朋友可以参考下...2020-06-25ShardingSphere jdbc集成多数据源的实现步骤
本文主要介绍了ShardingSphere jdbc集成多数据源的实现步骤,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-10-21- 这篇文章介绍的是利用C#设置自定义文件图标,然后实现双击启动的功能,文章给出了示例代码,介绍的很详细,有需要的可以参考借鉴。...2020-06-25
基于BootStrap的Metronic框架实现页面链接收藏夹功能按钮移动收藏记录(使用Sortable进行拖动排序)
这篇文章主要介绍了基于BootStrap的Metronic框架实现页面链接收藏夹功能按钮移动收藏记录(使用Sortable进行拖动排序)的相关资料,非常不错,需要的朋友可以参考下...2016-09-01基于Bootstrap的Metronic框架实现页面链接收藏夹功能
本文给大家介绍基于Metronic的Bootstrap开发框架实现页面链接收藏夹功能,非常不错,具有参考借鉴价值,感兴趣的朋友一起学习吧...2016-09-01