转自 http://blog.csdn.net/topcoder1234/article/details/5887653。
注意:在这里并没有专门一个CHAR来存储字符,而是通过位置来确定是哪个字符,num = str[i] - 'a';
struct node
{
bool isWord;
node *next[26];
node()
{
isWord = false;
for(int i=0;i<26;i++)
next[i] = NULL;
}
};
class Trie
{
public:
node *root;
Trie(){root = NULL;}
void insert(string str)
{
if(!root)
root = new node;
node *location = root;
for(int i=0;i<str.length();i++)
{
int num = str[i] - 'a';
if(location->next[num] == NULL)
{
location->next[num] = new node;
}
location = location->next[num];
}
location->isWord = true;
}
bool search(string str)
{
node *location = root;
for(int i=0;i<str.length();i++)
{
int num = str[i] - 'a';
if(location->next[num] == NULL)
return false;
location = location->next[num];
}
return location->isWord;
}
};
分享到:
相关推荐
采用的是c++11实现,用数据结构 Trie(字典树),AVL(平衡树),Hush(散列表)分别进行相应的类,没个类里面分别实现了insert(插入),delete(删除),search(查找操作) 。对于三种数据结构的具体操作会在之后进行具体说明...
Trie树(字典树) 字典树又叫前缀树,是处理字符串常用的数据结构,最近和朋友一起粗略写了一下关于字典树的词频统计。 一、功能介绍 文件流读写单词; 将读到的单词插入树中; 打印树,打印出单词和个数以及词频;...
Algorithms 本次README修订为算法仓库Algorithms的第100次commit,首先我们庆祝自2016年8月4日本仓库建立以来Dev-XYS在算法学习方面取得的显著进步! 这里有各种算法的C++...指针版的字典树 Trie(Pointer)
内含资源如下: 1.基本数据结构 1.1.Array .............. 字典树 3.17.QuickFind ............................ 并查集_基于数组实现 3.18.QuickUnion ......................... 并查集_基于树思想实现
它比用于存储文本数据的红黑树要快,但是与哈希表不同的是,保留了元素的字典顺序。 patricia树最初是由Donald R. Morrison描述的,用于文本处理。 这里的实现是经过稍微修改的形式,通常用于在IP网络中存储CIDR...
Radix Trie(有时称为Trie,数字树或前缀树)是树形的确定性自动机(DFA)。 这是一种serach trie,用于存储动态集或关联数组,其中键通常是字符串。 与二进制搜索不同,树中没有与特定关键字关联的节点。 相反,它...
韩文弢 -《论C++语言在信息学竞赛中的应用》 ## 2005 龙 凡 -《序的应用》 魏 冉 -《浅谈“跳跃表”的相关操作及其应用》 任 恺 -《图论的基本思想及方法》 杨 俊 -《二分策略在信息学竞赛中的应用》 张...
java lru leetcode leetcode Description My leetcode solutions. Statistics language num C++ 308 Python3 46 JavaScript 4 Java 2 SQL 2 Template ...Trie ...Trie ...字典树 Double Linked List 双向链表
字典存储在一个 trie(前缀树)中。 对字典进行类似遍历的 DFS 以查找单词。 对于每个单词,我们使用动态规划技术来确定板子是否包含该单词。 该算法的运行时间为 O(字典大小 * 版面尺寸 * 版面尺寸 * 字典中的...
leetcode 316 LeetCode、剑指Offer刷题笔记(C++实现) LeetCode 题目按类型分类 Hash 链表 双指针 快慢指针 滑动窗口 区间合并 字符串操作 ...字典树(Trie) 树的遍历 二叉查找树 并查集 前缀和 剑指Offer
Trie(前缀树) 如果概念已知,则直截了当。 目标金额 基本 dfs 被接受,记忆化有不错的加速。 最优解使用子集和,应该研究。 生成括号 对于 n > 0,总是最左边有一个左括号。 如果最左边括号内的表达式及其补码有 i...
使用 trie 树存储字典,并提供接口以通过最大匹配策略快速搜索所有匹配的分段 使用 hmm 模型来评估每场比赛的得分,并利用得分最高的那个。 hmm 模型是通过统计训练的,em 训练算法会尽快更新。 这种分割方法对于...
5)Trie树 81 8.其他. 1)主定理与复杂度 81 2)静态存储与动态存储… 82 3)字符串匹配 主主面主主主 ….82 四 数据与计算机通信… 85 1 OSI 85 2.TCP协议 85 1.通路的建立 .86 2.数据传输 86 3....