字典树(Trie树)

1.trie基础(1) 是什么?Trie,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。(2) 性质根节点不包含字符,除根节点外每一个节点都只包含一个字符从

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

1. trie基础

 

(1) 是什么?

Trie,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。

 

(2) 性质

  • 根节点不包含字符,除根节点外每一个节点都只包含一个字符
  • 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串
  • 每个节点的所有子节点包含的字符都不相同

 

例如,单词序列a, to, tea, ted, ten, i, in, inn,对应的trie。

字典树(Trie树)

(3) 应用

用于统计和排序大量的字符串,但不仅限于字符串,所以经常被搜索引擎系统用于文本词频统计。

 

(4) 优点

  • 最大限度地减少无谓的字符串比较
  • 查询效率比哈希表高

 

2. 一个例子

 

  1 #include <stdio.h>  
  2 #include <string.h>  
  3 #include <stdlib.h>  
  4   
  5 #define MAX 256//ascii码有256个字符,故每棵树的子节点最多有256个  
  6 #define MAXLEN 256//单词最长为256  
  7   
  8 typedef struct TrieNode  
  9 {  
 10     int count;  
 11     struct TrieNode *next[MAX];  
 12 }TrieNode;    
 13   
 14 //插入一个单词  
 15 void Insert(char *word,TrieNode *root)  
 16   
 17 {  
 18     int i;  
 19     TrieNode *cur;  
 20     if(word[0]=='\0')  
 21         return;  
 22     cur=root;  
 23     for(i=0;word[i]!='\0';i++)  
 24     {  
 25         if(cur->next[word[i]]==NULL)  
 26         {  
 27             TrieNode *newNode = (TrieNode *)malloc(sizeof(TrieNode));  
 28             memset(newNode,0,sizeof(TrieNode));  
 29             cur->next[word[i]]=newNode;  
 30         }  
 31         cur=cur->next[word[i]];  
 32     }  
 33   
 34     cur->count++;  
 35     return;  
 36 }  
 37   
 38 //创建树输入每个单词,以回车结束,则单词被插入树中,碰到*停止树的创建  
 39 void Construct(TrieNode *&root)  
 40 {  
 41      char inStr[MAXLEN];  
 42      int size=0;  
 43      root = (TrieNode *)malloc(sizeof(TrieNode));  
 44      memset(root,0,sizeof(TrieNode));  
 45      while(1)  
 46      {  
 47          scanf("%s",inStr);  
 48          if(strcmp(inStr,"*")==0)  
 49              break;  
 50          Insert(inStr,root);  
 51      }  
 52      return;  
 53 }  
 54   
 55 //遍历整棵树  
 56 void Traverse(TrieNode *curP)  
 57 {  
 58     static char theWord[MAXLEN];  
 59     static int pos=0;   
 60     int i;  
 61     if(curP==NULL)  
 62         return;  
 63     if(curP->count)  
 64     {  
 65         theWord[pos]='\0';  
 66         printf("%s:%d\n",theWord,curP->count);  
 67     }  
 68     for(i=0;i<MAX;i++)  
 69     {  
 70         theWord[pos++]=i;   
 71 //从这句话可以看出在递归调用子节点前,子节点的值已经加入到单词中了  
 72         Traverse(curP->next[i]);   
 73         pos--;    
 74     }  
 75     return;  
 76 }  
 77   
 78 //查找一个单词是不是在树中  
 79 bool Find(TrieNode *root,char *word)  
 80 {  
 81     int i;  
 82     TrieNode *cur;  
 83     cur=root;  
 84     for(i=0;word[i]!='\0';i++)  
 85     {  
 86         if(cur->next[word[i]]==NULL)  
 87         {  
 88             return false;  
 89         }  
 90         cur=cur->next[word[i]];  
 91     }  
 92   
 93     if(cur->count)  
 94         return true;  
 95     else  
 96         return false;  
 97 }  /* 何问起 hovertree.com */
 98   
 99 int main()    
100 {    
101     TrieNode *root;  
102     char str[MAXLEN];  
103     Construct(root);    
104     printf("\n");    
105     Traverse(root);    
106     printf("\n");    
107     while(1)  
108     {  
109         scanf("%s",str);  
110         if(strcmp(str,"*")==0)  
111             break;  
112         printf("%s:%d\n",str,Find(root,str));   
113     }  
114   
115     return 0;    
116 }  

推荐:http://www.cnblogs.com/roucheng/p/wendang.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/120417.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • linux下打包命令_linux常用命令全集

    linux下打包命令_linux常用命令全集linux系统中遇到要打包文件的时候我们该使用什么命令呢?下面由秋天网Qiutian.ZqNF.Com小编为大家整理了linux系统中打包文件的命令详解的相关知识,希望对大家有帮助!linux系统中打包文件的命令详解tartar的选项与参数非常的多!我们只讲几个常用的选项,更多选项您可以自行mantar查询啰![[emailprotected]~]#tar[-j|-z][cv]…

  • AndroidJNI 通过C++调用JAVA

    1. JNIEnv对象    对于本地函数   JNIEXPORT void JNICALL Java_video1_TestNative_sayHello(JNIEnv * env, jobject obj)   {        cout   }           JNIEnv类型代表Java环境。通过这个JNIEnv*指针,就可以对Java端的代码进行操作。如,创建Java类得对象,调用J

  • layer 弹出层传递参数

    layer 弹出层传递参数layer弹出层轻量好用,一直喜欢用,但是却没有弹出层传参的接口,迫于无奈只能Url地址传参,总所周知,这个可是限制大小的,百度一番,看看大神们怎么处理,结果就感觉所有回答都是Ctrl+C加Ctrl+V,全是地址栏传参,页面缓存、cookie、localstorage,本着不甘心的原则,就想为什么不能在open的时候把参数一起作为属性传递了,强行看了layer源码(扒光慢慢看),于是乎…

  • shell 编译和执行java文件

    shell 编译和执行java文件

  • TTL门电路工作原理_TTL门电路和CMOS有什么特点

    TTL门电路工作原理_TTL门电路和CMOS有什么特点CMOS门电路、TTL门电路基础CMOS门电路简介MOS管简介合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注脚注释也是必不可少的KaTeX数学公式新的甘特图功能,丰富你的文章UML图表FLowchart流程图导出与导入导出导入CMOS门电路简介CMOS门电路(ComplementaryMetal-Oxide-Semiconductor)是指利用P沟道

    2022年10月26日
  • unbuntu版 pycharm2021.9 激活码【2021免费激活】[通俗易懂]

    (unbuntu版 pycharm2021.9 激活码)这是一篇idea技术相关文章,由全栈君为大家提供,主要知识点是关于2021JetBrains全家桶永久激活码的内容https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~83PVI25FMO-eyJsaWNlb…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号