Trie树与翻译

What Are You Talking About
指针多叉树

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <malloc.h>
using namespace std;
struct Trie{
    Trie *next[26];
    char *trans;  //定义一个指向一维数组的指针
    Trie()  //构造函数
    {
        int i;
        for(i=0;i<26;i++){
            next[i]=NULL;
        }
        trans = NULL;
    }
};
struct Trie *root = new Trie();
void put(char trans[],char word[])   //将单词word插入到字典树中，并在最后加上翻译trans
{
    Trie *p = root;
    int i;
    for(i=0;trans[i];i++){
        int n = trans[i]-'a';
        if(p->next[n]==NULL)
            p->next[n] = new Trie();
        p = p->next[n];
    }
    p->trans = (char*)malloc(sizeof(char)*11);
    strcpy(p->trans,word);
}
void research(char str[])   //找到对应的翻译并输出，没找到则输出原来的字符串
{
    Trie *p = root;
    for(int i=0;str[i];i++){
        int n = str[i]-'a';
        if(p->next[n]==NULL){
            printf("%s",str);
            return ;
        }
        p = p->next[n];
    }
    if(p->trans==NULL)
        printf("%s",str);
    else
        printf("%s",p->trans);
}
int main()
{
    char word[11],trans[11];
    scanf("%s",word);
    while(scanf("%s",word)!=EOF){   //输入字典
        if(strcmp(word,"END")==0)   //遇到结束标记
            break;
        scanf("%s",trans);
        put(trans,word); //将单词word插入到字典树中，并在最后加入其翻译
    }
    scanf("%s",word);
    getchar();
    char str[3001];
    while(gets(str)){
        if(strcmp(str,"END")==0)
            break;
        int i,j=0;
        char t[3001]={0};
        for(i=0;str[i];i++){
            if('a'<=str[i] && str[i]<='z'){ //检测到的是小写字母
                t[j++] = str[i];
            }
            else{
                t[j] = '\0';
                if(t[0]!='\0'){ //不是空的
                    research(t);    //找到对应的翻译并输出，没找到则输出原来的字符串
                    t[0]='\0',j=0;  //初始化t
                }
                printf("%c",str[i]);
            }
        }
        printf("\n");
    }
    return 0;
}

Babelfish
数组多叉树

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int MAXN=4000010;
const int BASE=26;
struct Node
{
    char *trans;
    int next[26];
};
Node trie[MAXN];
int trie_s;
void insert(char *trans,char *str)
{
    int p=0;
    int len=strlen(str);
    for(int i=0;i<len;i++)
    {
        int pos=str[i]-'a';
        if(!trie[p].next[pos]) trie[p].next[pos]=trie_s++;
        p=trie[p].next[pos];
    }
    trie[p].trans=new char[strlen(trans)];
    strcpy(trie[p].trans,trans);
}
void research(char *str)
{
    int p=0;
    int len=strlen(str);
    for(int i=0;i<len;i++)
    {
        int pos=str[i]-'a';
        if(!trie[p].next[pos])
        {
            printf("eh\n");
            return;
        }
        p=trie[p].next[pos];
    }
    printf("%s\n",trie[p].trans);
}
int main()
{
    char trans[11],str[11];
    trie_s=1;
    int index;
    char c;
    while(true)
    {
        c=getchar();
        if(c=='\n') break;
        index=0;
        trans[index++]=c;
        while(true)
        {
            c=getchar();
            if(c==' ') break;
            trans[index++]=c;
        }
        trans[index]=0;
        scanf("%s",str);
        getchar();
        insert(trans,str);
    }
    while(scanf("%s",str)!=EOF)
    {
            research(str);
    }
    return 0;
}

左儿子右兄弟树

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int MAXN=4000010;
const int BASE=26;
struct Node
{
    char *trans;
    int son;
    int right;
    char c;
}trie[MAXN];
int trie_s;
void init()
{
    trie[0].trans=NULL;
    trie[0].right=trie[0].son=-1;
    trie_s=1;
}
void insert(char *trans,char *str)
{
    int u=0,v;
    int len=strlen(str);
    bool flag;
    for(int i=0;i<len;i++)
    {
        char c=str[i];
        flag=true;
        v=trie[u].son;
        for(v=trie[u].son;v!=-1;v=trie[v].right)
        {
            if(trie[v].c==c)
            {
                flag=false;
                break;
            }
        }
        if(flag)
        {
            v=trie_s++;
            trie[v].c=c;
            trie[v].right=trie[u].son;
            trie[v].son=-1;
            trie[u].son=v;
        }
        u=v;
    }
    trie[u].trans=new char[strlen(trans)];
    strcpy(trie[u].trans,trans);
}
void research(char *str)
{
    int u=0,v;
    bool flag;
    int len=strlen(str);
    for(int i=0;i<len;i++)
    {
        char c=str[i];
        flag=true;
        for(v=trie[u].son;v!=-1;v=trie[v].right)
        {
            if(trie[v].c==c)
            {
                flag=false;
                break;
            }
        }
        if(flag)
        {
            printf("eh\n");
            return;
        }
        u=v;
    }
    printf("%s\n",trie[u].trans);
    return;
}
int main()
{
    char trans[11],str[11];
    init();
    int index;
    char c;
    while(true)
    {
        c=getchar();
        if(c=='\n') break;
        index=0;
        trans[index++]=c;
        while(true)
        {
            c=getchar();
            if(c==' ') break;
            trans[index++]=c;
        }
        trans[index]=0;
        scanf("%s",str);
        getchar();
        insert(trans,str);
    }
    while(scanf("%s",str)!=EOF)
    {
            research(str);
    }
    return 0;
}