`

字典树Trie-C++实现

 
阅读更多

转自 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++使用字典树,平衡树,散列表实现英汉字典源代码,数据结构课程设计

    采用的是c++11实现,用数据结构 Trie(字典树),AVL(平衡树),Hush(散列表)分别进行相应的类,没个类里面分别实现了insert(插入),delete(删除),search(查找操作) 。对于三种数据结构的具体操作会在之后进行具体说明...

    C++词频统计,数据结构期末大作业,包含源码,附带思维导图讲解

    Trie树(字典树) 字典树又叫前缀树,是处理字符串常用的数据结构,最近和朋友一起粗略写了一下关于字典树的词频统计。 一、功能介绍 文件流读写单词; 将读到的单词插入树中; 打印树,打印出单词和个数以及词频;...

    全面的算法代码库

    Algorithms   本次README修订为算法仓库Algorithms的第100次commit,首先我们庆祝自2016年8月4日本仓库建立以来Dev-XYS在算法学习方面取得的显著进步!   这里有各种算法的C++...指针版的字典树 Trie(Pointer)

    数据结构实现(C++版)

    内含资源如下: 1.基本数据结构 1.1.Array .............. 字典树 3.17.QuickFind ............................ 并查集_基于数组实现 3.18.QuickUnion ......................... 并查集_基于树思想实现

    patricia:C ++ patricia trie

    它比用于存储文本数据的红黑树要快,但是与哈希表不同的是,保留了元素的字典顺序。 patricia树最初是由Donald R. Morrison描述的,用于文本处理。 这里的实现是经过稍微修改的形式,通常用于在IP网络中存储CIDR...

    Radix-Tree:C + +模块使用字典为确定性有限自动机状态实现基数树

    Radix Trie(有时称为Trie,数字树或前缀树)是树形的确定性自动机(DFA)。 这是一种serach trie,用于存储动态集或关联数组,其中键通常是字符串。 与二进制搜索不同,树中没有与特定关键字关联的节点。 相反,它...

    IOI国家集训队论文集1999-2019

    韩文弢 -《论C++语言在信息学竞赛中的应用》 ## 2005 龙 凡 -《序的应用》 魏 冉 -《浅谈“跳跃表”的相关操作及其应用》 任 恺 -《图论的基本思想及方法》 杨 俊 -《二分策略在信息学竞赛中的应用》 张...

    javalruleetcode-leetcode:leetcode

    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 双向链表

    boggle-solver:Boggle 游戏的 trie + 动态编程解决方案

    字典存储在一个 trie(前缀树)中。 对字典进行类似遍历的 DFS 以查找单词。 对于每个单词,我们使用动态规划技术来确定板子是否包含该单词。 该算法的运行时间为 O(字典大小 * 版面尺寸 * 版面尺寸 * 字典中的...

    leetcode316-leetcode_and_swordoffer:LeetCode分类题解,语言为C++

    leetcode 316 LeetCode、剑指Offer刷题笔记(C++实现) LeetCode 题目按类型分类 Hash 链表 双指针 快慢指针 滑动窗口 区间合并 字符串操作 ...字典树(Trie) 树的遍历 二叉查找树 并查集 前缀和 剑指Offer

    leetcode走楼梯-Leetcode-Patterns-Cpp:Leetcode-Patterns-Cpp

    Trie(前缀树) 如果概念已知,则直截了当。 目标金额 基本 dfs 被接受,记忆化有不错的加速。 最优解使用子集和,应该研究。 生成括号 对于 n &gt; 0,总是最左边有一个左括号。 如果最左边括号内的表达式及其补码有 i...

    hmmseg:嗯用于分割

    使用 trie 树存储字典,并提供接口以通过最大匹配策略快速搜索所有匹配的分段 使用 hmm 模型来评估每场比赛的得分,并利用得分最高的那个。 hmm 模型是通过统计训练的,em 训练算法会尽快更新。 这种分割方法对于...

    PaperTest Q&amp;A笔试综述

    5)Trie树 81 8.其他. 1)主定理与复杂度 81 2)静态存储与动态存储… 82 3)字符串匹配 主主面主主主 ….82 四 数据与计算机通信… 85 1 OSI 85 2.TCP协议 85 1.通路的建立 .86 2.数据传输 86 3....

Global site tag (gtag.js) - Google Analytics