一 题意:输入很多棵树(单词),统计每种树所占的百分比
二 算法:用trie树轻松解决,trie树的典型应用就是统计单词出现的个数。
三 代码如下,ps:清华大学《数据结构-C语言版》的trie树实现很傻逼,我不知道它如何
解决前缀字符串的问题,比如统计aaa和aaabb的出现次数
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//#define DEBUG
#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__)
#else
#define debug(...)
#endif
struct trie_node {
struct trie_node *child[256]; /* 分支节点的孩子指针 */
int count; /* 用于记录单词出现的次数,若count大于0,说明
从根节点到此节点的父节点构成了一个单词,这个
单词的次数就是count */
};
int n; /* 树的总数 */
struct trie_node *init_trie_tree()
{
return (struct trie_node *)calloc(1, sizeof(struct trie_node));
}
void insert(struct trie_node *root, char *word)
{
struct trie_node *node;
char *p;
node = root;
debug("%s.......\n", word);
for (p = word; *p; p++) {
debug("开始插入%c\n", *p);
if (node->child[*p] == 0) {
debug("%c不存在,创建新节点\n", *p);
node->child[*p] = (struct trie_node *)calloc(1, sizeof(struct trie_node));
}
else {
debug("%c存在\n", *p);
}
node = node->child[*p];
}
//到达记录统计单词次数的节点
node->count++;
debug("%s有%d个\n\n", word, node->count);
}
/* 借助pos指针来遍历每个单词,初始时pos指向worddump的第一个位置
* 若往孩子节点走,则pos后移,若往兄弟节点走,则pos保持不动
*/
void dfs_travel(struct trie_node *root)
{
static char worddump[31];
static int pos;
int i;
if (root->count) { /* 如果count不为0,则肯定找到了一个单词 */
worddump[pos] = '\0';
if (worddump[0]) {
printf("%s %0.4f\n", worddump, ((float)root->count*100)/(float)n);
}
}
for (i = 0; i < 256; i++) {
if (root->child[i]) {
debug("找到%c\n", i);
worddump[pos++] = i; /* 往下遍历,pos跟着后移,供孩子节点使用 */
dfs_travel(root->child[i]);
pos--; /* 恢复位置,供下一个兄弟节点使用 */
debug("回退1个位置\n");
}
}
}
int main()
{
char line[31];
struct trie_node *root;
n = 0;
root = init_trie_tree();
while (gets(line)) {
insert(root, line);
n++;
}
dfs_travel(root);
return 0;
}
分享到:
相关推荐
二叉树的应用,二叉树的应用,二叉树的应用,
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2525-Text Formalization【TrieTree】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/XW4FQ3
北大POJ2513-Colored Sticks【TrieTree+MergeSet+EulerPath】 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
NULL 博文链接:https://200830740306.iteye.com/blog/603493
LeetCode判断字符串是否循环 :bookmark_tabs:Plan 动态规划 背包问题 动态规划 POJ 3267 POJ 1260 POJ ...POJ ...POJ ...POJ ...POJ ...POJ ...POJ ...POJ ...POJ ...POJ ...POJ ...POJ ...POJ ...POJ ...POJ ...POJ ...POJ ...POJ ...POJ ...trie树 POJ 251
poj 2763 程序 线段树 LCA 2000MS AC
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
poj2342,树形dp,dp[i][0]表示i不参加party,其下属(包括非直接下属)能得到的最优值。dp[i][1]表示i参加的其下属和他能得到的最优值。
北大POJ1159-Palindrome 解题报告+AC代码
POJ题解 个人写法 线段树每个人都不一样
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友