Babelfish 解题报告--第一次用字母树，效果非常不错

文章来源：http://blog.csdn.net/harder2005/archive/2008/08/21/2807042.aspx

字符串映射，查找，个人觉得这个字母树可以被更好的实现

题目链接：

    

    

题目大意：输入将给你一系类一一对应的字符串，称之为字典；之后将输入一个个单词，你需要在字典中查找是否存在该词的映射，如果存在输出对应的词，否则输出 "eh”

基本思路：很自然的想法是使用STL的map，通过map将字典词建立映射关系；经验证，这样的做法行得通，而且，对这个可以AC；但是，考虑到，题目描述中，每个词是由长度不超过10个的小写字母组成，这样一来更经典的想法是采用字母数。通过字母树建立映射，然后再通过字母树进行查找；可能你会想，ｍａｐ这么简单好用，还用字母树做甚，我不多说，看看下面便知：

3869000

Harder

2503

Accepted

15444K

2016MS

G++

523B

3868993

Harder

2503

Accepted

16888K

391MS

C++

1346B

基本算法实现：接受映射的输入，建立字母树；接受查询输入，在字母树上查询该词是否存在映射；字母树的实现很简单，通过简单的结构体即可，每个节点包含２６个子节点，分别代表ａ，ｂ，ｃ．．．ｚ２６个字母，这样就可以形成一颗树

AC代码：

1. #include
2. #include
3. using namespace std;
4. int main()
5. {
6.     map dic;
7.     char *a,*b;
8.     char line[1001];
9.     while(1)
10.     {
11.        gets(line);
12.        if(strlen(line)==0|| (strlen(line)>1&&line[0]==' ') ) break;
13.        a=strtok(line, " ");
14.        b=strtok(NULL, " ");
15.        dic[string(b)]=string(a);          
16.     }
17.     string word;
18.     while(cin>>word)
19.     {
20.        string mean = dic[word];
21.        if(mean=="")  mean="eh";
22.        cout<
23.     }
24.     return 0;
25. }

1. /*字母树*/
2. #include"stdio.h"
3. #include"string.h"
4. char NotFound[10]={'e','h',0};
5. struct WordNode
6. {//字母数节点
7.     WordNode* word[26];//子节点指针，分别表示下一个字母为a,b,c...z
8.     char refer[10];
9.     WordNode(){memset(word,NULL,sizeof(word));}
10. };
11. WordNode* root;//字母树根结点,每次查询或创建均从此节点开始
13. void BuildNode(const char* s,const char* s1)
14. {//创建字母树子节点，构造s->s1的映射
16.     WordNode* begin=root;
17.     int i=0,n=0;
18.     for(i=0;i<(int)strlen(s);i++)
19.     {
20.         n=(s[i]-'a');
21.         if(begin->word[n]==NULL)
22.             begin->word[n]=new WordNode;
23.         begin=begin->word[n];
24.     }
25.     strcpy(begin->refer,s1);//此处创建了映射
26. }
27. void Find(const char* s)
28. {//在字母树上查询字符串 s
29.     WordNode* begin=root;
30.     int i=0,n=0;
31.     for(i=0;i<(int)strlen(s);i++)
32.     {
33.         n=(s[i]-'a');
34.         if(begin->word[n] == NULL)
35.         {//没有查到
36.             puts(NotFound);
37.             return ;
38.         }
39.         begin = begin->word[n];
40.     }//查到该字符串在树上的位置
41.     puts(begin->refer);//输出其映射的字符串
42. }
43. void Dispose(WordNode* node)
44. {//释放内存
45.     if(node==NULL)
46.         return ;
47.     for(int i=0;i<26;i++)
48.     {
49.         if(node->word[i]==NULL)
50.             continue;
51.         Dispose(node->word[i]);//递归
52.     }
53.     delete node;node = NULL ;
54. }
56. int main()
57. {
58.     root=new WordNode;
59.     char in[30],w1[10],w2[10];
60.     while(gets(in)&&*in)
61.     {//按行读入数据，如为空行退出次循环
62.         sscanf(in,"%s%s",w2,w1);//从字符串in中读出字符串w2,w1
63.         BuildNode(w1,w2);//创建w1，w2的映射节点
64.     }
65.     while(gets(in)&&*in)//按行接受查询输入
66.             Find(in);//在字母树上查找映射节点
67.     //Dispose(root);//释放内存
68.     return 0;
69. }