例:给出一个字符文本,每行一个字符串,统计不同的字符串出现的百分比,最后按ASCII排序输出不同字符串和出现的百分比。
分析:对输入字符串建立字典树,在叶子结点记录该字符串出现的次数。这样的话,最后DFS搜索就可以查找每个字符串出现的次数。
样例:
Sample Input
Red Alder
Ash
Aspen
Basswood
Ash
Beech
Yellow Birch
Ash
Cherry
Cottonwood
Ash
Cypress
Red Elm
Gum
Hackberry
White Oak
Hickory
Pecan
Hard Maple
White Oak
Soft Maple
Red Oak
Red Oak
White Oak
Poplan
Sassafras
Sycamore
Black Walnut
Willow
exit
Sample Output
Ash 13.7931
Aspen 3.4483
Basswood 3.4483
Beech 3.4483
Black Walnut 3.4483
Cherry 3.4483
Cottonwood 3.4483
Cypress 3.4483
Gum 3.4483
Hackberry 3.4483
Hard Maple 3.4483
Hickory 3.4483
Pecan 3.4483
Poplan 3.4483
Red Alder 3.4483
Red Elm 3.4483
Red Oak 6.8966
Sassafras 3.4483
Soft Maple 3.4483
Sycamore 3.4483
White Oak 10.3448
Willow 3.4483
Yellow Birch 3.4483
import java.util.Scanner;
import java.text.DecimalFormat;
class Trie{ //字典树
Trie next[] = new Trie[128];//所有儿子节点
int cnt;/* 用于记录单词出现的次数,若cnt大于0,说明
从根节点到此节点的父节点构成了一个单词,这个
单词的次数就是cnt */
public Trie(){
cnt = 0;
}
}
public class Main{
Trie root = new Trie();
String res;
int all = 0;
DecimalFormat a = new DecimalFormat("0.0000");
void solve() {
Scanner cin = new Scanner(System.in);
String input;
while(cin.hasNext()){//用所有字符串,构造字典树
input = cin.nextLine();
// if(input.equals("exit")) break;
insert(input.toCharArray());
}
res = "";
dfs(root);//深度优先搜索字典树
}
void insert(char[] str){//将一个字符串插入字典树
int len = str.length;
int k = 0, t;
Trie p = root;
while(k!=len){
t = str[k++];
if(p.next[t] == null) p.next[t] = new Trie();
p = p.next[t];
}
p.cnt++;//字符串的最后一个节点,根节点到此节点构成了一个单词,此单词的个数加1
all++;//字符串总数加1
}
void dfs(Trie p){
if(p.cnt!=0) System.out.println(res + " " + a.format(p.cnt*100.0/all));
for(int i=0;i< 128;i++){//遍历p的所有儿子节点(邻接点)
if(p.next[i] != null){
res+=(char)i;
dfs(p.next[i]);
res = res.substring(0, res.length()-1);//恢复现场
}
}
}
public static void main(String[] args) {
Main test = new Main();
test.solve();
}
}
源码:
分享到:
相关推荐
要求采用邻接矩阵作为无向图的存储结构,邻接表作为有向图的存储结构,完成无向图和有向图的建立,并对建立好的图进行深度和广度优先遍历。具体实现要求: 1. 通过键盘输入图的顶点和边信息,分别构造一个无向图的...
POINTERS ON C 第九章编程练习11统计某个单词出现的个数,示例为单词the。VC6.0编译通过
统计文章中单词的个数,并且输出最多的15个单词
(4)输出深度优先遍历和广度优先遍历的结点访问序列; (5)并给出相应生成树的边集。 (6)给出至少3组测试数据,其中图顶点的个数大于10小于30。 较高要求:建立深度和广度生成树,按凹入表或树形打印生成树。
统计文本单词的个数,VB6.0源代码编写
二叉树的各种遍历(前序、中序、后序、层序),以及计算树的叶子树和树的深度
在eclipse上用java实现统计一句话或一段话中单词出现的个数,并按照字母表顺序输出,并利用treemap实现
用二叉搜索树实现统计一个文件中单词的个数
二叉排序树实现单词的统计!将准备好的.txt文件中的读入,统计其中各个单词出现的次数。
统计C程序单词的个数 ——Hash技术 数据结构”是计算机程序设计的重要理论技术基础,本次数据结构课程设计的内容主要是考察数据结构中的查找,查找是数据结构中很重要的一章,其实在日常生活中我们,我们几乎每天都...
void dfs(linkmap *maps,int i)//i用来指定深度优先遍历的起始值 { edgenode *pp; printf("%c",maps->maplist[i].element); v[i]=1; pp=maps->maplist[i].firstedge; while(pp) { if(!v[pp->adress]) ...
输入一串还有空格的字符,就能统计出单词的个数
/*建立二叉树后写出各种遍历算法,统计各类结点个数并求树的深度 (1)仅输出中序遍历第K个元素算法(奖励1分) (2)编写求某个结点在树中层数算法(奖励2分) (3)已知中序和后序建立树结构(奖励3分)*/
该资源可以简单计算文本中单词个数
统计所需搜索的文件的每个单词的数量和单词的名字,直观反映在桌面
//num 用来统计单词的个数 //state 用来记录程序当前是否处于一个单词之中,初值为0,表示不在单词中,值为1,表示正处于在一个单词中 printf("Please input the number of lines for English passage:"); scanf...
实现统计一段文章的每个单词的个数 其中CountDemo使用STL中的Map来实现的 CountDemo2是用一般语言实现,没有用到STL实现的; MapCount是用STL中的Vector和Map共同实现的 此题目是学习STL中的Map和Vector必练的经典...
字典树又叫前缀树,是处理字符串常用的数据结构,最近和朋友一起粗略写了一下关于字典树的词频统计。 一、功能介绍 文件流读写单词; 将读到的单词插入树中; 打印树,打印出单词和个数以及词频; 单个单词的个数和...
对读入的某个文本文件input.txt中,拆出英文单词,输出一个按字典顺序排列的单词表,结果输出在文本文件output.txt中,每个单词一行,并在单词后输出该单词出现的个数,两个字段之间用逗号分隔。约定单词仅由英文...