字典树初识

谁践踏了优雅 2024-02-18 22:27 26阅读 0赞

又称**单词查找树**，**[Trie树][Trie]**，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。

![Trie1.jpg][]

字典树与字典很相似,当你要查一个单词是不是在字典树中,首先看单词的第一个字母是不是在字典的第一层,如果不在,说明字典树里没有该单词,如果在就在该字母的孩子节点里找是不是有单词的第二个字母,没有说明没有该单词,有的话用同样的方法继续查找.字典树不仅可以用来储存字母,也可以储存数字等其它数据。

已统计动物数量那题为列

\#include<iostream>  
\#include<stdio.h>  
\#include<string.h>  
\#include<stdlib.h>  
using namespace std;  
\#define N 26  
typedef struct k  
\{  
int count;  
k \*next\[N\];  
\}\*Trie;  
int M=0;  
char a\[20\];  
Trie base;  
Trie Creat()  
\{  
Trie p=(Trie)malloc(sizeof(k));  
for(int i=0;i<N;i++)  
\{  
p->next\[i\]=NULL;  
\}  
p->count=0;  
return p;  
\}  
void Insert(char \*s)  
\{  
Trie p=base;  
for(int i=0;i<strlen(s);i++)  
\{  
if(p->next\[s\[i\]-'a'\]==NULL) 如果该分支不存在，则新建该分支  
p->next\[s\[i\]-'a'\]=Creat();  
p=p->next\[s\[i\]-'a'\]; 更新p为新建分支  
\}  
p->count++; 当单词统计完毕后，该单词的计数加一；  
if(p->count>M) 如果他大于目前的最大值，则更新  
\{  
M=p->count;  
strcpy(a,s);  
\}  
\}  
int main()  
\{  
int i,j,n;  
char s\[30\];  
base=Creat();  
cin>>n;  
while(n--)  
\{  
scanf("%s",s);  
Insert(s);  
\}  
printf("%s %d\\n",s,M);  
return 0;  
\}

[Trie]: http://www.wutianqi.com/?p=1359
[Trie1.jpg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/6d735ca06bd94d16899f5cde70e5b576.png

发表评论取消回复

表情：

评论列表（有 0 条评论，26人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构与算法】初识树和二叉树

? 本文由程序喵正在路上原创，CSDN首发！? 系列专栏：数据结构与算法? 首发时间：2022年10月28日? 一以贯之的努力不得懈怠的人生。

骑猪看日落/ 2024年04月26日 02:23/ 0 赞/ 78 阅读

相关高级树结构之红黑树初识

文章目录一红黑树简介二探究变色、旋转操作的时机三总结一红黑树简介通过在插入几点时维护数的平衡，这样就不会出现极端情况，使

左手的ㄟ右手/ 2024年03月29日 15:04/ 0 赞/ 52 阅读

相关字典树初识

又称单词查找树，[Trie树][Trie]，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词

谁践踏了优雅/ 2024年02月18日 22:27/ 0 赞/ 27 阅读

相关初识二叉树

初识二叉树树形结构概念二叉树二叉树的基本形态两种二叉树满二叉树完

柔光的暖阳◎/ 2022年10月22日 09:16/ 0 赞/ 188 阅读

相关初识EasyExcel

1、为什么使用easyexcel > > java解析excel的框架有很多 poi jxl 存在问题：非常的消耗内存 > easyexcel 我们遇到再大的e

逃离我推掉我的手/ 2022年10月13日 02:48/ 0 赞/ 450 阅读

相关初识JAVA

Java的起源： Java之父：James Gosling 1995年5.23日正式诞生;Java的形象代表图标：“一杯热气腾腾的咖啡

水深无声/ 2022年08月09日 04:29/ 0 赞/ 377 阅读

相关初识java

新的学期初识Java，在这一周的Java学习中学习到了两种排序的方法：冒泡法和选择法排序首先说一下冒泡法例如一组数据5 9 3 1 6从小到大排列第一轮

骑猪看日落/ 2022年05月28日 04:55/ 0 赞/ 411 阅读

相关初识Java

今天算是从c++里脱身了，进入了Java程序员的行列，虽然之前对Java没有了解过，但是出于对c++编程的理解，除了刚开始对编辑环境以及对Java的语法不太熟悉

女爷i/ 2022年05月20日 09:57/ 0 赞/ 342 阅读

相关初识字典树

输入第一行输入动物名字的数量N(1<= N <= 4000000),接下来的N行输入N个字符串表示动物的名字（字符串的长度不超过10,字符串全为小写字母，并且只有一组测

桃扇骨/ 2022年01月28日 10:39/ 0 赞/ 145 阅读

相关 SQLMap-----初识

前言昨天收到一封来自客户网络中心发来的邮件，说是之前的一个项目存在sql注入漏洞，并附上了一张sqlmap检测结果的图片。记得第一次接触sql注入这些关于系统安全的问题

冷不防/ 2021年12月23日 02:43/ 0 赞/ 468 阅读