- 浏览: 196925 次
- 性别:
- 来自: 武汉
文章分类
- 全部博客 (137)
- c++ (74)
- c++,算法,回溯 (2)
- DP问题。 (9)
- DP问题,0/1背包问题 (3)
- 数学问题 (6)
- 贪心算法 (10)
- 排序 (16)
- 数据结构 (7)
- 容器 (2)
- 模拟问题 (2)
- 水题 (8)
- 并查集 (3)
- 非技术 (2)
- 素数问题 (1)
- DFS (3)
- 二叉树 (1)
- 递归 (1)
- 图论 (5)
- 最小生成树 (5)
- 最短路径 (6)
- bell_flaod算法 (2)
- hash (3)
- 二分查找 (1)
- 搜索 (5)
- BFS (5)
- STL (3)
- 字符串hash (1)
- 拓扑排序 (1)
- 字典树 (4)
- 哈弗曼树 (1)
- KMP (7)
- 线段树 (9)
- 树状数组 (6)
- 全排列 (2)
- DP问题 (2)
- LCS (1)
- 最长不下降子序列 (2)
- 面试经验 (3)
字典树,又称单词查找树,Trie树,是一种树形结构,典型应用是用于统计,排序和保存大量的字符串,所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来节约存储空间,最大限度的减少无谓的字符串比较,查询效率比哈希表高。Trie树示意图如附件图所示:该trie树存有abc、d、da、dda四个字符串,如果是字符串会在节点的尾部进行标记。没有后续字符的branch分支指向NULL。Trie的特点:1. 根结点不包含任何字母。2. 其余结点仅包含一个字母(非元素)3. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。 4. 每个结点的子节点包含字母不同。5. 采用标记的方法确定是否为字符串。Trie的缺点:动态建树时,用new很费时;静态建树时,预存节点数很费空间。 Trie树的模板一:静态建树:
Trie的模板二:动态建树 关于字典树的材料大多大同小异,需要自己进一步去理解去消化~~
#include<iostream>
using namespace std;
const int Max = 1000;
const int branchNum = 26;
struct tree_node{
int count;
bool isstr;
tree_node *next[branchNum];
}root, node[Max];
int p = 0; // 静态建树的特点,记录用了几个tree_node,则下一个节点为node[p]。
void insert(char *word){
tree_node *location = &root; // 起初先指向根,再一层层向下查找。
while(*word){
if(location->next[*word-'a'] == NULL){
node[p].count = 0; // 初始化新节点。
node[p].is = false;
memset(node[p].next, NULL, sizeof(node[p].next));
location->next[*word-'a'] = &node[p ++];
}
location = location->next[*word-'a'];
location->count ++;
word ++;
}
loaction->isstr = true;
}
bool search(char *word){
tree_node *loaction = &root;
while(*word && loaction){
loaction = loaction->[*word-'a'];
word ++;
}
return (location != NULL && location->isstr);
}
struct tree_node
{
bool isstr; // 记录此处是否构成一个串。
tree_node *next[branchNum]; // 指向各个子树的指针,下标0-25代表26字符
tree_node(){
isstr = false;
memset(next, NULL, sizeof(next));
}
}root;
void insert(char *word){ // 向以root为根结点的树中插入串word
tree_node *location = &root;
while(*word){
if(location->next[*word-'a'] == NULL){ // 不存在则建立
tree_node *tmp = new tree_node;
location->next[*word-'a'] = tmp;
}
location = location->next[*word-'a']; // 每插入一步,有一个新串经过,指针要向下移动
word ++;
}
location->isstr = true;
}
bool search(char *word){
tree_node *location = &root;
while(*word && location){
location = location->next[*word-'a'];
word ++;
}
return (location != NULL && location->isstr);
}
发表评论
-
虚函数、纯虚函数、虚基类、抽象类、虚函数继承、虚继承
2013-08-29 14:34 789虚函数:虚函数是C++中用于实现多态(polymorphis ... -
排序算法总结
2013-05-17 11:00 787选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法, ... -
poj 3122
2012-12-11 19:51 813题意:作者要开一个生日party,他现在拥有n块高度都为1 ... -
poj 3273
2012-12-11 16:49 949题意:给你天数n,和每天需要花的钱,让你把这些天分成m份(每份 ... -
poj 2503
2012-05-30 16:33 720大致题意: 输入一个字典,字典格式为“英语à外语”的 ... -
poj 3630
2012-05-30 15:43 889题意:给出n个数字串,问其中是否有一个串是另一个串的前 ... -
poj 2001
2012-05-30 14:54 808题意:给出n个单词(1<=n<=1000),求 ... -
poj 1159
2012-05-28 19:08 1398题目大意:给你一段字符串,让你求出在中间最少加入几个字符 ... -
poj 3176
2012-05-28 14:47 977大致题意: 输入一个n层的三角形,第i层有i个数,求从第 ... -
poj 1260
2012-05-28 09:54 1572题意解释: 有n个等级的珠宝,等级依次升高,等级越高价钱越高 ... -
poj 1836
2012-05-28 09:22 2673是POJ2533的扩展题。题意不难,令到原队列 ... -
poj 2533
2012-05-26 15:36 1207在做这道题目之前,首先让我们了解一下什么是LIS算法,LIS俗 ... -
poj 3267
2012-05-26 09:43 776从程序可以看出,第i个位置到L所删除的字符数,总是先取最坏情况 ... -
poj 1276
2012-05-25 16:20 2352题意: 这道题的意思是给你一堆钱,各种面值的都有,比 ... -
poj 1094
2012-05-25 13:54 1062题意:给出字母个数,和有限个有序对(a<b)求出能确定字 ... -
poj 3393
2012-05-23 17:00 1227大致题意: 科普文一篇,文章80%都是无用信息,因为 ... -
poj 3007
2012-05-14 10:21 949大致题意: 给定一个字符串,从任意位置把它切为两半, ... -
poj 3096
2012-05-10 21:09 964题意: 定义D-pairs表示取字符串s中相距为D的两个字母 ... -
poj 1426
2012-04-26 20:11 2117大致题意: 给出一个整数n,(1 <= n <= ... -
poj 1797
2012-04-24 15:05 1590题目大意是就是何处一个图,n个顶点和m条边,每个边都有最大承载 ...
相关推荐
字典树 树 图 算法 I II III IV V VI VII VIII IX X XI XII IX X 冒泡排序 选择排序 插入排序 希尔排序 归并排序 快速排序 堆排序 计数排序 桶排序 基数排序 递归 查找算法 贪心算法 分治算法 参考资料 JavaScript ...
操作可行性分析,系统的主要业务和业务流程分析,还包括数据字典的设计,管理信息系统的设计,IPO图和决策树设计,管理信息系统的实施和运行,还有部分源代码,该希望大家多多支持,欢迎大家哦评论,积极交流学习!
12 管理索引 目标 12-2 索引的分类 12-3 B 树索引 12-4 位图索引 12-6 B 树索引和位图索引的比较 12-7 创建普通 B 树索引 12-8 创建索引:指导 12-10 创建位图索引 12-11 修改索引的储存参数 12-12 分配和回收索引...
Python数据结构书籍是学习Python数据结构的重要参考资料,本文将介绍Python数据结构书籍的相关内容。 Python数据结构书籍主要包括以下内容: 1. 数据结构基础知识:介绍数据结构的基本概念、分类、特点等内容,包括...
贝叶斯、KNN、随机森林、决策树、支持向量机、SGD、逻辑回归、XGBoost、lightgbm,通过网格搜索进行参数优化,最终迭代出每个模型的最佳参数和准确率,最终返回一个最佳模型。 利用测试数据进行测试,分类模型的效果...
* 角色管理模块(包括资源授权树形列表加载、资源授权角色、资源权限拦截) * 资源管理模块 -------- 该资源内项目源码是个人的毕设,代码都测试ok,都是运行成功后才上传资源,答辩评审平均分达到96分,放心下载...
访谈的准备材料和资源 主题 [ML-标准] NN 中的优化: 基础知识和神经网络: 批量标准化: 决策树/随机森林:[ISLR 第 8 章] 主成分分析(PCA):[ISLR 10.2] 聚类:[ISLR 第 10 章] ICA/FA: 分类:[[ISLR-Chap4]] ...
1. 层次结构模型: 层次结构模型实质上是一种有根结点的定向有序树,IMS(Information Manage-mentSystem)是其典型代表。 2. 网状结构模型:按照网状数据结构建立的数据库系统称为网状数据库系统,其典型代表是DBTG...
为了生成树视图,我的计划是进行SQL查询以从BOM表中获取所有记录,并使用字典从树的根有效地构建树,其中根是没有父组件的组件名称。 我对datagridview的计划是,当用户在树形视图上选择一个节点时,一个函数将对...
包括加密Oracle子程序,存储应用程序用户名和口令,禁止修改删除数据库对象,Oracle数据加密以及丢失SYSMAN及资料档案库用户口令的解决方法。书中给出了丰富的图表,多数图例是作者根据多年实践总结出来的,图示简练...
包括加密Oracle子程序,存储应用程序用户名和口令,禁止修改删除数据库对象,Oracle数据加密以及丢失SYSMAN及资料档案库用户口令的解决方法。书中给出了丰富的图表,多数图例是作者根据多年实践总结出来的,图示简练...
知识字典 D 可用三元组表示如下: D = ( O , T , E ) 把三元组理解为 (实体entity,实体关系relation,实体entity),把实体看作是结点,把实体关系(包括属性,类别等等)看作是一条边,那么包含了大量三元组的知识库就...
数据库设计的典型案例 要点 学生选课管理系统的数据库设计 学习目标 学生选课管理系统的需求分析 学生选课管理系统的 ER 图 学生选课管理系统的关系数据库模式 学生选课管理系统数据库的建立 2 1 案例的系统需求简介...
(SPArse建模软件,),一种优化工具箱,开发用于解决各种稀疏估计问题,例如字典学习和矩阵分解(NMF,稀疏PCA等),还具有LARS稀疏分解问题,坐标下降, OMP,SOMP,近端方法和结构化稀疏分解问题(l1 / l2,l1 / ...
3、本项目适合作为计算机、数学、电子信息等专业的课程设计、期末大作业和毕设项目,作为参考资料学习借鉴。 4、本资源作为“参考资料”如果需要实现其他功能,需要能看懂代码,并且热爱钻研,自行调试。 基于...
我们将精力集中在HTML字典键值上,该键值包含大脚目击事件的第一手资料。 文字处理 -为了解析我们的数据,我们使用Beautiful soupHTML解析器在内容中找到“ p”,以分隔段落的开头和结尾。 -这给我们留下了4405个...
合同管理模块增加从员工资料导入合同信息的功能(右树菜单)(感谢Lucky Cat,我就是我) 员工福利体现分公司信息(感谢欢浪家园) 物品管理体现分公司信息(感谢我就是我) 人事合同增加时,同步员工档案(感谢Lucky ...
数据字典管理:支持中、英文信息,支持无限级别分类配置,动态控制是否可用等。 部门信息管理:支持中、英文无限级别部门信息增加,删除,修改操作,部门列表、树心查询等。 日志管理:系统日志列表查询、在线...
本文是由笔者2012年学习oracle数据库时编写的学习札记,其中的题目 多数为老师留下的思考题目。 我相信本文会对初学者使用oracle有一个初步的使用印象。右图为我所参 考的书籍。 目录 第一讲 Oacle关系数据库 ...