/**********************************************************
数据结构:
Trie树,又称单词查找树或字典树,是一种树形结构,是一种哈希树的变种;
基本原理:
Trie树的核心思想是空间换时间,利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的;
应用:
用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计;
优点:
最大限度地减少无谓的字符串比较,查询效率比哈希表高;
基本特性:
(1)根节点不包含字符,除根节点外每一个节点都只包含一个字符;
(2)从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串;
(3)每个节点的所有子节点包含的字符都不相同;
***********************************************************/
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<climits>
#include<algorithm>
using namespace std;
const int MAX=26;
struct Trie //Trie结点声明
{
bool isStr;//标记该结点处是否构成一个串
Trie *next[MAX];//一个指针数组,存放着指向各个儿子节点的指针
};
void insert(Trie *root,const char *s) //将单词s插入到字典树中
{
if(root==NULL||*s=='\0')
return;
Trie *p=root;
while(*s)
{
if(p->next[*s-'a']==NULL)//如果不存在存储该字符的节点,则建立结点
{
Trie *temp=new Trie;
for(int i=0; i<MAX; i++)
{
temp->next[i]=NULL;
}
temp->isStr=false;
p->next[*s-'a']=temp;
p=p->next[*s-'a'];
}
else
{
p=p->next[*s-'a'];
}
s++;//让指针s指向下一个字符
}
p->isStr=true;//单词结束的地方标记此处可以构成一个串
}
int search(Trie *root,const char *s)//查找某个单词s是否已经存在
{
Trie *p=root;
while(p&&*s)
{
p=p->next[*s-'a'];
s++;
}
return (p&&p->isStr); //在单词结束处的标记为true时,单词才存在
}
void del(Trie *root)//释放整个字典树占的堆区空间
{
for(int i=0; i<MAX; i++)
{
if(root->next[i]!=NULL)
{
del(root->next[i]);
}
}
delete root;
}
int main()
{
//freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin);
char s[100];
Trie * root = new Trie;
for(int i=0; i<MAX; i++)
{
root->next[i]=NULL;
}
root->isStr=false;
int n,m; //n为建立Trie树输入的单词数,m为要查找的单词数
scanf("%d",&n);
getchar();
for(int i=0; i<n; i++) //先建立字典树
{
scanf("%s",s);
insert(root,s);
}
while(~scanf("%d",&m))
{
if(!m)
break;
for(int i=0; i<m; i++) //查找
{
scanf("%s",s);
if(search(root,s))
printf("YES\n");
else
printf("NO\n");
}
printf("\n");
}
del(root); //释放空间很重要
return 0;
}
- 浏览: 141661 次
- 性别:
- 来自: 北京
最新评论
-
java_web_hack1:
HashMap和HashTable区别 几乎是百分之百会出现老 ...
面试 java -
hj01kkk:
剖析地很深入,谢谢!!
Java:单例模式的七种写法 -
hj01kkk:
很不错
Java:单例模式的七种写法 -
sunway00:
Map<Integer, String> ha ...
为KeySet遍历HashMap辟谣---效率问题 -
Shen.Yiyang:
ddlgyq 写道lyplyz 写道如果你在循环中只用key, ...
为KeySet遍历HashMap辟谣---效率问题
相关推荐
BoostGSOC项目的trie数据结构实现
Prefix Trie数据结构的Java实现。 介绍 尝试是类似于基于有序树的数据结构的地图,可快速搜索O(k)的顺序,其中k是键的长度。 阅读有关trie的更多信息。 动机 它最初是为在我的Android应用程序T9 App Launcher中使用...
允许模糊字符串匹配的 Trie 数据结构 这是 Steve Hanov 在他的编写的 Python 程序的 Go 版本 这已经完成了,但没有测试。 ###这个怎么运作 这是一个基本的 。 您可以搜索作为字符串后缀的所有单词。 您还可以...
该项目包含一个Java类(StringTrie),该类实现了用于存储字符串的trie数据结构,以及一个用于操纵StringTrie对象的基于菜单的控制台应用程序。 描述 StringTrie支持包含英文字母(A-Za-z),撇号('),连字符/破...
使用trie数据结构的低级原始自动完成 特征 该自动完成库具有手动插入单词,根据查询获取单词建议,用单词的字典数组填充数据结构以及删除不需要的单词的能力。 注意:默认情况下,库中不填充任何单词。 插入方式 ...
数字树一个trie数据结构实现。 全面测试实用程序:可克隆和可序列化(到/来自json) 通过前缀搜索值安装npm install --save digital-tree2.0.0版几乎是一个完整的重写,并且大多数不向后兼容APIcreate()/ Ctor ...
Louds-Trie 在 D 和 Python 中实现 Trie 数据结构。 ##Test D 实现 $cd d$dmd test.d bitarray.d lib/exception.d lib/random/random.d lib/random/string.d queue.d trie.d -unittest$./test##运行Python实现 $cd ...
用C ++编写的可扩展且压缩的trie数据结构。
带有测试的Java中的Trie API 与Trie数据结构相关的API集合,以Java实现,并经过严格的测试支持,以及一个示例问题,该问题通过通过(依赖项注入框架)向其中注入Trie服务来使用Trie。使用的框架/库- -Google的依赖...
QTrie Java中的trie数据结构
lighter-tree模块是轻量级的trie数据结构实现。 它可用于构建值的结构,并对所有非空值(包括不是树实例的叶子)执行预遍历。 安装 在您的项目目录中,安装并另存为依赖项: npm install --save lighter-tree 原料...
特里 自定义实现的Trie数据结构。
rust_sequence_trie:符合人体工程学的trie数据结构
特里Java专案使用动态Trie数据结构来组织带有commin前缀的单词的字典
Troogle 通过npm提供的CLI(命令行界面),允许用户与Global Trie数据结构进行交互什么是特里? Trie是一种有效的单词re Trieval数据结构。 这种树结构可以在O(M)时间(M是最长的单词长度)中搜索单词。 安装请...
Contacts_Manager 一个非常简单的联系人管理器桌面应用程序,它使用trie数据结构来有效地搜索联系人。 用Java编写。 该应用程序通过运行ContactsListGUI.Java启动。
安装您可以通过以下方式手动安装它: gem install rambling-trie 或者,将其包含在您的Gemfile并将其捆绑: gem 'rambling-trie'使用Rambling Trie 创建要创建一个新的特里,请像这样初始化它: trie = Rambling :: ...
@ datastructures-js / trie 尝试在javascript中实现。 每个Trie节点都包含一个单词的一个字符。 特里目录 .forEach(cb) .toArray() .wordsCount() .nodesCount() 。清除() Trie.fromArray(列表) 特里...
图书馆尝试C ++ 数据结构实现
hat-trie, 一种有效的trie实现 hat 这是Askitis和Sinha的hat trie数据结构的ANSI实现,它是一个非常高效的( 空间和时间) 现代变体。这里实现的版本将字节数组映射到单词( 。例如,无符号的longs ),它可以以用来存储...