首页 > 代码库 > 【POJ】2418 Hardwood Species
【POJ】2418 Hardwood Species
简单字典树。
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 5 #define MAXN 128 6 7 typedef struct Trie { 8 int count; 9 Trie *next[MAXN];10 Trie() {11 count = 0;12 for (int i=0; i<MAXN; ++i)13 next[i] = NULL;14 }15 } Trie;16 17 Trie root;18 char buf[35];19 double n = 0;20 21 void create(char str[]) {22 int i = 0, id;23 Trie *p = &root, *q;24 25 while (str[i]) {26 id = str[i];27 ++i;28 if (p->next[id] == NULL) {29 q = new Trie();30 p->next[id] = q;31 }32 p = p->next[id];33 }34 p->count++;35 }36 37 void dfs(Trie *t, int d) {38 int i;39 40 if (t->count) {41 buf[d] = ‘\0‘;42 printf("%s %.4lf\n", buf, t->count*100.0/n);43 }44 for (i=0; i<MAXN; ++i) {45 if (t->next[i]) {46 buf[d] = i;47 dfs(t->next[i], d+1);48 }49 }50 }51 52 int main() {53 while (gets(buf) != NULL) {54 create(buf);55 n += 1.0;56 }57 dfs(&root, 0);58 return 0;59 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。