記得一年前 跑去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 閱讀(349)
評論(0) 編輯 收藏 引用 所屬分類:
數據結構 、
字典樹