记得一年前 跑去CSDN问HDU1251（
http://acm.hdu.edu.cn/showproblem.php?pid=1251）的写法，飞雪写了个很精简的代码，数组模拟字典树。问题是那个代码只适用于那道题目。
后来有道开了一次网络邀请赛，当时就有那么一道字典树的题，我对着它无解。。今天，我去看了一下字典树，仅仅是靠自己理解了一下字典树的图。
图片地址：
http://baike.baidu.com/view/1436495.htm居然就写出了1251，相比与当年飞雪的代码他的时间是46MS 我今天写的是93MS。可是让我开心的是，我觉得我写的这个扩展性强，我似乎有感觉我能解决当年那题有道邀请赛的题目~~好开心呀~~
当年一个人在寝室一个劲的学习链表~~后来很长一段时间觉得链表似乎没什么用。。。直到上次的线段树，现在的trie树，或者以后的红黑树~B树~？呵呵。如果没有链表的基础我不可能只看图就能写出字典树，基础如此的重要。
贴下代码：
1
/**//*
2
3957388 2011-05-15 13:59:22 Accepted 1251 93MS 43768K 1163B C++ test
3 so happy learning sth by myself,share this happiness with you ^ ^
4
*/
5
6
7
8#include <iostream>
9#include <cstdlib>
10#include <cstdio>
11#include <algorithm>
12#include <cstring>
13using namespace std;
14
15typedef struct tree
16
{
17 int num;
18 struct tree *br[26];
19}Node;
20
21void insert(char *str,Node *root) // 插入字典
22{
23 for(;*str;++str)
24
{
25 int id = *str-'a';
26 if (root->br[id]!=NULL)
27 {
28 root->br[id]->num++;
29
}
30 else
31 {
32 root->br[id] = (Node *)malloc(sizeof(Node));
33 root->br[id]->num=1;
34 for (int j=0;j<26;++j)
35 {
36 root->br[id]->br[j]=NULL;
37 }
38 }
39 root=root->br[id];
40 }
41}
42
43
44int find(char *str,Node *root) // 查找单词数
45{
46 for(;*str;++str)
47 {
48 int id = *str-'a';
49 if (root->br[id]==NULL)
50 {
51 return 0;
52 }
53 else
54 {
55 if(*(str+1)==0)
56 {
57 return root->br[id]->num;
58 }
59 root=root->br[id];
60 }
61 }
62 return 0;
63}
64
65void freeM(Node *root) // 释放内存，其实OJ上不释放不影响结果
66{
67 for(int i=0;i<26;++i)
68 {
69 if(root->br[i]!=NULL)
70 {
71 freeM(root->br[i]);
72 }
73 }
74 free(root);
75}
76int main()
77{
78 char str[10];
79 //freopen("data1.in", "r", stdin);
80 //freopen("data1.out", "w+", stdout);
81 Node *root=(Node *)malloc(sizeof(Node));;
82 int i;
83 for (i=0;i<26;++i)
84 {
85 root->br[i]=NULL;
86 }
87 while (gets(str))
88 {
89 if (str[0]==0)break;
90 insert(str,root);
91 }
92 while (gets(str))
93 {
94 printf("%d\n",find(str,root));
95 }
96 //fclose(stdout);
97 //fclose(stdin);
98 freeM(root);
99 return 0;
100}
posted on 2011-05-15 14:16
mr_chen 阅读(312)
评论(0) 编辑 收藏 引用 所属分类:
数据结构 、
字典树