POJ 2503——Babelfish-蒲公英云

POJ 2503——Babelfish

这一题也没什么思路很直接，直接用字典树存储信息，在进行查找：

优点：思路直接，速度较快缺点：占用内存较大，建立的关系是单向的，代码较长

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
using namespace std;
struct Trie
{
    Trie *next[26];
    int sign;
    char eng[30];
};
Trie root;
void initial(Trie *t)
{
    for(int i=0;i<26;i++)
    t->next[i]=NULL;
}
void creatTrie(char *s1,char *s2)
{
    Trie *p=&root,*q;
    int len=strlen(s1),i;
    for( i=0;i<len;i++)
    {
        int id=s1[i]-'a';
        if(p->next[id]==NULL)
        {
            q=new Trie;
            initial(q);
            q->sign=0;
            p->next[id]=q;
            p=q;
        }
        else p=p->next[id];
    }
    p->sign=1;
    strcpy(p->eng,s2);
}
string search(char *s)
{
    Trie *p=&root;
    int len=strlen(s);
    for(int i=0;i<len;i++)
    {
        int id=s[i]-'a';
        if(p->next[id]==NULL)
        return "eh";
        else p=p->next[id];
    }    
    if(p->sign==1)
    return p->eng;
    else return "eh";
}
int main()
{
    char foreign[30],english[30],str[65];
    while(gets(str)&&str[0]!='\0')
    {
        sscanf(str,"%s %s",english,foreign);
        creatTrie(foreign,english);
    }
    while(scanf("%s",str)!=EOF)
    {
        cout<<search(str)<<endl;
    }
    return 0;
}

方法二：map容器，将两者建立对应关系；

优点：建立的关系是双向的，较省空间，代码量非常小缺点：查找速度较慢，查找时间复杂度为log n

#include <iostream>  
#include <cstdlib>  
#include <cstdio>  
#include <cstring>  
#include <string>  
#include <set>  
#include <map>  
using namespace std;  
map<string, string> Map;  
char str[60];  
char temp1[30], temp2[30];    
int main()  
{  
    Map.clear();   
    while(gets(str))  
    {  
        if(str[0] == '\0') break;  
        sscanf(str, "%s %s", temp1, temp2);  
        Map[temp2] = temp1;  
    }  
    while(gets(str))  
    {  
        if(Map.find(str) != Map.end()) cout<<Map[str]<<endl;  
        else cout<<"eh"<<endl;  
    }    
    return 0;
}