Trie树,又称单词查找树,典型用于统计和排序大量字符串,查询效率比哈希表高。(空间复杂度高)
它有3个基本特性:
1)根节点不包含字符,除根节点外每一个节点都只包含一个字符。
2)从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
3)每个节点的所有子节点包含的字符都不相同。
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
Trie树的结构体:
struct Trie_Node
{
int id;//数据域
Trie_Node *next[26];//孩子结点
Trie_Node()
{
id = -1;
memset(next,0,sizeof(next));
}
}*root;
Trie树的更新操作(插入、查询某字符串的数据)
int getNum(char *t)
{
Trie_Node *p = root;
int i = 0,del;
while(t[i] != '\0')
{
del = t[i] - 'a';
if(p->next[del] == NULL)
p->next[del] = new Trie_Node();//动态建树,也可以换成静态
p = p->next[del];
i++;
}
if(p->id == -1)
p->id = num++;
return p->id;
}
POJ2513
题目大意:有n根筷子(n=250000),每根筷子两头涂有颜色。现在问能否将所有筷子连起来,并且每两根筷子的连接点颜色都相同。
分析:题意不难理解,现在做一个转换:将每种颜色作为一个结点,每根筷子两头的颜色之间连有一条边。这样,就形成了下面的图:
这样问题就转化为:要求全部走完且经过每条边一次且仅一次,即一笔画问题。 这就成了欧拉路的判断:
1.判断该图是否连通;
2.该图的每个点的度要么全为偶数,要么有且仅有两个度为奇数。
判断图是否是连通图,可以用并查集。计算每个点的度,就是统计单词出现的次数。因此联想到用Trie树统计单词出现的次数,每次将单词在Trie树中查找,若该单词在trie树中第一次出现,则给它一个标号(相当于hash)。
POJ3630(1056)
题目大意:给出n个电话号码(n=10000),每个电话号码长度不超过10。要求是否满足:每个电话号码不能是其它号码的前缀。
分析:在Trie树中放置一个标志位,表示从根节点到该结点是否是已经输入的号码。
bool findAndInsert(char *t)
{
Trie_Node *p = root;
int i = 0,del;
while(t[i] != '\0')
{
if(p->exist)
return true; //别的字符串是当前字符串的前缀
del = t[i] - '0';
if(p->next[del] == NULL)
{
p->next[del] = &node[nodeNum];
nodeNum++;
}
p = p->next[del];
i++;
}
for(i = 0; i < 10; i++) //当前字符串是别的字符串的前缀
{
if(p->next[i] != NULL)
return true;
}
p->exist = true;
return false;
}
POJ2001
题目大意:现在人们喜欢用缩写,比如carbon可以缩写为carb,但不能缩写为car。因为有car这个准确的单词。给你n个单词(n=1000),每个单词长度不超过20。求出每个单词的最短缩写。
分析:在Trie树中加入一个计数器num,表示以这个字符串为前缀的单词有几个。在查询时,根据传入的单词一层层的往下找,找到num=1就说明这个是第一次被使用,停止输出。
#include <iostream>
const int MAX = 1001;
char str[MAX][21];
int nodeNum;
struct Trie_Node
{
int num; //to remember how many words can reach here
Trie_Node *next[26];
Trie_Node()
{
num = 0;
memset(next,NULL,sizeof(next));
}
};
Trie_Node node[MAX*10],head;
void insert(char *t)
{
int i=0,del;
Trie_Node *p = &head;
while(t[i] != '\0')
{
del = t[i] - 'a';
if(p->next[del] == NULL)
{
p->next[del] = &node[nodeNum];
nodeNum++;
}
p->next[del]->num++;
p = p->next[del];
i++;
}
}
void query(char *t)
{
int i = 0;
Trie_Node *p = &head;
while(t[i] != '\0')
{
printf("%c",t[i]);
p = p->next[t[i]-'a'];
if(p->num == 1)
break;
i++;
}
printf("\n");
}
int main()
{
int i = 0;
nodeNum = 1;
while(scanf("%s",str[i]) != EOF)
{
insert(str[i]);
i++;
}
for(int j = 0; j < i; j++)
{
printf("%s ",str[j]);
query(str[j]);
}
return 0;
}
- 大小: 14.9 KB
分享到:
相关推荐
数据结构课程设计 树的遍历 两江大学出版社
很常见的字符串处理数据结构……参考博客:字符串统计神器——Trie树以前没有怎么认真学过Trie,现在重新打了一遍用了指针实现,感觉好看多了。
Linqer 那点所谓的分布式(2)那点所谓的分布式——memcache 那点所谓的分布式——redis 树结构专题(5)6天通吃树结构—— 第五天 Trie树 6天通吃树结构—— 第四天 伸展树 6天通吃树结构—— 第三天 Treap树 6天通吃树...
Step1 设计结点——数据结构 Step2 实现相应的操作方法——增删改查 Step1 设计结点 我们需要该结点能够存储以下数据: 该结点代表的单个字符->>字节 该结点是否为词语结尾(叶子结点)->>布尔 该结点的子结点串->>...
数据结构 —— 代码模板链接 常用代码模板2——数据结构 链表与邻接表:树与图的存储 栈与队列:单调队列、单调栈 kmp Trie 并查集 堆 Hash表 搜索与图论 —— 代码模板链接 常用代码模板3——搜索与图论 DFS与BFS...
数据结构 —— 代码模板链接 常用代码模板2——数据结构 链表与邻接表:树与图的存储 栈与队列:单调队列、单调栈 kmp Trie 并查集 堆 Hash表 搜索与图论 —— 代码模板链接 常用代码模板3——搜索与图论 DFS与BFS...
SWMiner算法使用基于前缀树的结构来压缩存储生成的树模式,并且使用trie merging机制有效地更新子树模式的支持度。实验结果表明,SWMiner算法在滑动窗口模型中的性能优于目前现有的常用算法,能有效地挖掘最近时间段...
陈 宏 -《数据结构的选择与算法效率——从IOI98试题PICTURE谈起》 来煜坤 -《把握本质,灵活运用——动态规划的深入探讨》 齐 鑫 -《搜索方法中的剪枝优化》 邵 铮 -《数学模型的建立、比较和应用》 石润婷 -...
国家集训队2006论文集 陈启峰:《“约制、放宽”方法在解题中的应用》 陈首元:《维护森林连通性——动态树》 ...朱晨光:《基本数据结构在信息学竞赛中的应用》 朱泽园:《半平面交的新算法及其实用价值》
基数树(也称为 patricia trie、radix trie或紧凑前缀树)是一种空间优化的树数据结构,它允许仅使用键的前缀插入键(以及与这些键相关联的可选值)以供后续查找而不是整个密钥。 基数树在字符串或文档索引和扫描...
常用代码模板2——数据结构 链表与邻接表:树与图的存储 栈与队列:单调队列、单调栈 kmp Trie 并查集 堆 Hash表 C++ STL使用技巧 搜索与图论 —— 代码模板链接 常用代码模板3——搜索与图论 DFS与BFS 树与图的遍历...
该项目是一个简单的 IR 系统,具有以下组成部分 - 1) 高效的文档索引数据结构2) 一种排序算法,用于检索与查询最相关的文档3) 页面排序算法,根据检索到的文档的“重要性”对其进行排序4) 摘要算法,用于显示每个...
数组、栈、队列、链表、二分搜索树、集合、映射、优先队列、堆、线段树、Trie、并查集、AVL、红黑树、哈希表 数据处理典型案例,逐渐更新 :hot_beverage: Java 、、基本概念、面向对象、基本数据类型与运算、字符串...