- 浏览: 604268 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
字典树 又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来节约存储空间,最大限度地减少无谓的字符串比较,查询效率比哈希表高。
它有3个基本特性:
1)根节点不包含字符,除根节点外每一个节点都只包含一个字符。
2)从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
3)每个节点的所有子节点包含的字符都不相同。
如用 ak ab ab ai oricon orish 所构造出来的字典树为:
例: POJ2001,题目大意:
给你很多个字符串,让你找每个字符串的最短前缀,但这么多字符串前缀不能有相同的,要能唯一标识一个字符串,而且前缀长度尽量小。
样例:
Sample Input
carbohydrate
cart
carburetor
caramel
caribou
carbonic
cartilage
carbon
carriage
carton
car
carbonate
Sample Output
carbohydrate carboh
cart cart
carburetor carbu
caramel cara
caribou cari
carbonic carboni
cartilage carti
carbon carbon
carriage carr
carton carto
car car
carbonate carbona
AC 代码:
后记:
题目虽然在北大PKU上AC了(说明解答没有错),但在自己电脑上DOS下运行时不能输出答案,问题在下面这段代码:(不然跳出循环)
网上也没有找到答案,到底如何处理本题的输入,请各位提出,谢谢!
它有3个基本特性:
1)根节点不包含字符,除根节点外每一个节点都只包含一个字符。
2)从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
3)每个节点的所有子节点包含的字符都不相同。
如用 ak ab ab ai oricon orish 所构造出来的字典树为:
例: POJ2001,题目大意:
给你很多个字符串,让你找每个字符串的最短前缀,但这么多字符串前缀不能有相同的,要能唯一标识一个字符串,而且前缀长度尽量小。
样例:
Sample Input
carbohydrate
cart
carburetor
caramel
caribou
carbonic
cartilage
carbon
carriage
carton
car
carbonate
Sample Output
carbohydrate carboh
cart cart
carburetor carbu
caramel cara
caribou cari
carbonic carboni
cartilage carti
carbon carbon
carriage carr
carton carto
car car
carbonate carbona
AC 代码:
import java.util.Scanner; import java.util.List; import java.util.ArrayList; public class Main{ private int SIZE = 26; private TrieNode root; //字典树的根 private List<String> l=new ArrayList<String>(); public Main() { //初始化字典树 root = new TrieNode(); } private class TrieNode { //字典树节点 private int num;//有多少字符通过这个节点. private TrieNode[] son;// 所有的儿子节点 private boolean isEnd;//是不是最后一个节点 private char val;// 节点的值 TrieNode() { num = 1; son = new TrieNode[SIZE]; isEnd = false; } } public void insert(String str) { //在字典树中插入一个单词 if (str == null || str.length() == 0) { return; } TrieNode node = root; char[] letters=str.toCharArray(); for (int i = 0, len = str.length(); i < len; i++) { int pos = letters[i] - 'a'; if (node.son[pos] == null) { node.son[pos] = new TrieNode(); node.son[pos].val = letters[i]; } else { node.son[pos].num++; } node = node.son[pos]; } node.isEnd = true; } // 在字典树中查找. public void search(String str) { if (str == null || str.length() == 0) { return ; } TrieNode node = root; char[] letters=str.toCharArray(); for (int i = 0, len = str.length(); i < len; i++) { int pos = letters[i] - 'a'; System.out.printf("%c",letters[i]); node=node.son[pos]; if( node.num==1) break;; } } private void go() { Scanner in = new Scanner(System.in); String s=null; int num=0; while(in.hasNext()){ s=in.next(); l.add(s); insert(s); num ++; } for(int i = 0; i < num; i++){ System.out.printf("%s ",l.get(i)); search(l.get(i)); System.out.println(); } } public static void main(String[] args) { Main ma=new Main(); ma.go(); } }
后记:
题目虽然在北大PKU上AC了(说明解答没有错),但在自己电脑上DOS下运行时不能输出答案,问题在下面这段代码:(不然跳出循环)
Scanner in = new Scanner(System.in); String s=null; int num=0; while(in.hasNext()){ s=in.next(); l.add(s); insert(s); num ++; }
网上也没有找到答案,到底如何处理本题的输入,请各位提出,谢谢!
评论
2 楼
quanminy
2012-12-23
int pos = letters[i] - 'a'; 这样得到的指针位置不保险,输入数字或大写字符或其他字符程序直接挂调。
1 楼
quanminy
2012-12-23
Java代码
Scanner in = new Scanner(System.in);
String s=null;
int num=0;
while(in.hasNext()){
s=in.next();
l.add(s);
insert(s);
num ++;
}
这个 部分是因为Scanner 不断的等待前台输入数据,所以会不断的循环。可以设置一些特殊的字符作为命令入口,结束循环。
Scanner in = new Scanner(System.in);
String s=null;
int num=0;
while(in.hasNext()){
s=in.next();
l.add(s);
insert(s);
num ++;
}
这个 部分是因为Scanner 不断的等待前台输入数据,所以会不断的循环。可以设置一些特殊的字符作为命令入口,结束循环。
发表评论
-
求二叉树上任意两个节点的最近公共父节点
2013-01-09 10:24 2404北大百练题2756: 如上图所示,由正整数1, 2 ... -
JAVA判断二叉树是否是二叉平衡树
2013-01-07 18:59 1988import java.util.*; ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1913POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1400接前文:二维树状数组学习之一:彻底理解http://128kj ... -
二维树状数组学习之一:彻底理解
2012-12-12 20:54 2472当要频繁的对数组元素进行修改,同时又要频繁的查询数组内 ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1843关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1845关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1823关于树状数组,请参考:http://128kj.iteye.c ... -
初步了解树状数组
2012-12-07 14:18 1791一、树状数组是干什么的? 平常我们会遇到一些对数组进 ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2122POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
利用线段树求逆序数(JAVA)
2012-12-04 22:46 2597设A[1…n]是一个包含n个不同数的数组。如果在i< ... -
线段树入门学习(三)懒操作(兼解POJ1823) JAVA
2012-12-02 15:37 2139继续上文"线段树入门学习(二)" ht ... -
线段树入门学习(二)(兼解POJ3468) JAVA
2012-11-30 16:55 2561继续上文http://128kj.iteye. ... -
线段树入门学习(兼解HDU1754)
2012-11-30 11:24 2729先看网上的介绍: 线段树也叫区间树,顾名思义,线段树是 ... -
AVL树及JAVA实现
2012-11-26 16:34 2307一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二 ... -
图解平衡二叉树
2012-11-26 11:34 2064形态匀称的二叉树 ... -
深度优先遍历字典树(统计单词出现的个数)
2012-11-23 22:18 2856例:给出一个字符文本,每行一个字符串,统计不同的字符串出现的百 ... -
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
2012-11-17 21:50 18735堆有最大堆和最小堆之分,最大堆就是每个节点的值都>= ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 4070一、什么是并查集 ... -
根据二叉树前序遍历和中序遍历的结果输出后序遍历(java)
2012-10-07 19:58 3335前序遍历的第一个元素为根节点,在中序遍历中找到这个根节点 ...
相关推荐
在IT领域,字典树(Trie,也称为前缀树或字首树)是一种用于存储动态集合或关联数组的数据结构。...同时,学习如何读取文件、构建字典树,以及执行插入、搜索和删除操作,都是提升Java编程技能的好方法。
这个实例是用Java语言实现的,我们将深入探讨字典树的工作原理和Java实现的关键点。 首先,字典树的核心概念是利用节点来存储字符串的字符,每个节点可能有多个子节点,对应于下一个可能的字符。根节点通常不包含...
下面将详细介绍Java如何实现字典树以及其在实际应用中的价值。 1. **字典树的基本结构** 字典树是一种树形数据结构,每个节点包含一个字符,并且指向若干个子节点,代表该字符后可能接续的下一个字符。根节点不...
在Java中,Trie.java文件很可能包含了一个字典树的实现,包含了基本的插入、查找和遍历等方法。 字典树在实际应用中非常常见,如搜索引擎的关键词索引、拼写检查、IP路由表、电话号码簿等。通过Trie,可以快速查找...
字典树,也被称为Trie或前缀树,是一种用于高效存储和检索字符串的...通过阅读和理解提供的"字典树"代码,你可以深入学习字典树的具体实现细节,包括节点的定义、插入和查找算法的实现,以及如何处理不同字符集的问题。
2. **数据结构**:字典程序可能使用到了字典树、哈希表或者数组来存储词汇,理解这些数据结构的特性和效率是必要的。 3. **字符串处理**:Java的String类提供了丰富的操作方法,如split()用于分词,indexOf()和...
- **数据结构**:为了高效地存储和访问词汇信息,可能需要设计合适的数据结构,如哈希表(HashMap)用于快速查找,或者Trie树(字典树)用于高效的前缀搜索。 - **异步处理**:考虑到查词、改错和联想可能涉及较重...
在本项目中,"大一下学期期末作业(字典树优化)"是一个针对学校管理系统的课程设计,其核心是...通过这个项目,学生不仅能学习到字典树的原理和实现,还能深入了解如何在实际的管理系统中优化数据操作,提升用户体验。
5. **数据结构与算法**:为了高效地存储和查找单词,可能需要使用特定的数据结构,如字典树(Trie)或哈希表。理解这些数据结构的特性及适用场景,将有助于优化查询性能。 6. **文件I/O**:如果数据库不在内存中,...
总结来说,快速单词拼写程序结合了JAVA编程语言、字典树数据结构、拼写检查算法、文件I/O操作以及错误提示机制,形成了一套实用的文本拼写校验工具。对于学习和理解这些知识点,该程序提供了很好的实践案例。通过...
描述中提到,这个Java字典实现了单词的查找功能,使用了数组查询。这意味着开发者可能创建了一个数组,其中每个元素代表一个单词,并通过某种方式(如直接索引或排序后二分查找)来查找单词。描述还指出有超过1万个...
为了实现高效的查找,可能会用到数据结构如哈希表或二分搜索树,这些数据结构的使用能显著提高搜索速度,减少用户的等待时间。 在软件结构设计上,Java的面向对象特性得到了充分体现。开发者可能创建了诸如`Word`类...
`TriTree.java`和`TriNode.java`可能是对字典树的实现,`TriNode`可能表示树中的一个节点,包含字符信息以及指向子节点的引用。 `Dictionary.java`可能是一个接口或抽象类,定义了词典的基本操作,如添加单词、删除...
9. **线程安全**: 如果字典应用是多线程的,那么源代码可能使用`synchronized`关键字或`java.util.concurrent`包中的工具类确保并发访问的安全。 10. **设计模式**: 源代码可能包含了单例模式(确保字典实例的唯一...
- 如果数量庞大,可能会考虑使用Trie树(字典树)结构,以提高查询效率。 3. **正则表达式**: - Java的`java.util.regex`包提供了强大的正则表达式支持。可能的实现方式是将所有违禁词组合成一个大的正则表达式...
因此,开发一个基于字典树的大学生交流社区具有重要的现实意义,能够极大地便利学生的日常生活和学习。 #### 技术选型与框架介绍 为了高效地实现这个项目,开发者选择了SSM框架(Spring、SpringMVC、MyBatis),这...
- `generateCodes()`:遍历哈夫曼树,生成哈夫曼编码,通常使用递归实现。 - `printCodes()`:打印哈夫曼编码表,便于查看和理解。 哈夫曼编码的效率在于,对于出现频率高的字符,其编码往往较短,从而可以减少存储...
这个压缩包“WPF 已知问题 资源字典树引用与资源寻找的坑.rar”包含了一个MD文件,很可能是详细的案例分析和解决方案,旨在帮助开发者避免这些常见问题。 在WPF中,资源字典可以存在于多个层次,如应用程序级别、...
《简单的中英文词典》是一款基于Java编程语言开发的应用,主要目标是帮助初学者在学习Java的过程中更好地理解和应用基础知识。这个项目将编程与实际应用相结合,使得理论学习更具实践意义。 1. Java基础:Java是一...
为了提高性能,可以使用Trie树(字典树)数据结构,它的优点在于可以快速地进行前缀匹配。在Java中,可以自己实现Trie树,或者使用现有的库如Apache Commons Lang的Trie类。 预测结果显示在GUI上,可以通过JList...