[POJ][1451][字典树] T9

题目大意：

模拟手机T9输入法。先给出n个单词和其出现概率，根据用户按下的数字键，选择相应概率最大的单词输出。

思路：

首先根据给出的单词建树，然后根据按下的数字进行广搜。

代码：

#include
#include
#include
using namespace std;
struct trie
//利用结构体来封装字典树的节点。
{
    trie* next[26];
    trie* pre;
    //指针指向父节点，用于回溯输出单词。 
    int total;
    //total用于记录概率。 
    char letter;
    trie()
    //构造函数。 
    {
        for(int i=0;i<26;i++)
            next[i]=NULL;
        pre=NULL;
        total=0;
        letter='\0';
    }
};
void insert(char* s,int n,trie* root)
//将字符串s所表示的单词插入到字典树中。 
{
    trie *p=root;
    for(int i=0;s[i]!='\0';i++)
    {
        if(p->next[s[i]-'a']==NULL)
        {
            p->next[s[i]-'a']=new trie;
            p->next[s[i]-'a']->pre=p;
            p->next[s[i]-'a']->letter=s[i];
        }
        p=p->next[s[i]-'a'];
        p->total+=n;
    }
}
void output(trie* point)
//从point开始回溯至root，输出途径节点的字母，达到输出单词的目的。 
{
    if(point->pre->pre!=NULL)
        output(point->pre);
    printf("%c",point->letter);
}
char T9[10][5]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
void bfs(char* num,trie* root)
//根据按键广搜 
{
    queue q;
    q.push(root);
    for(int i=0;num[i]!='1';i++)
    {
        int size=q.size(),max=0;
        //max记录最大概率。 
        trie* now=NULL;
        //now指向表示概率最大的词的最后一个字母的节点。 
        while(size--)
        {
            trie *head=q.front();
            q.pop();
            for(int j=0;jnext[T9[num[i]-'0'][j]-'a'];
                if(temp!=NULL)
                //若树中存在此单词 
                {
                    if(temp->total>max)
                    {
                        max=temp->total;
                        now=temp;
                    }
                    q.push(temp);
                }
            }
        }
        if(now==NULL)
        //now==NULL说明没有单词对应现在的按键序列 
            printf("MANUALLY");
        else
            output(now);
        printf("\n");
    }
    printf("\n");
}
int main()
{
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        printf("Scenario #%d:\n",i);
        trie root;
        //字典树的根节点。 
        int w,m;
        for(scanf("%d",&w);w>0;w--)
        {
            char str[101];
            int p;
            scanf("%s%d",str,&p);
            insert(str,p,&root);
        }
        for(scanf("%d",&m);m>0;m--) 
        {
            char num[101];
            scanf("%s",num);
            bfs(num,&root);
            //对每个按键序列进行广搜。 
        }
        printf("\n");
    }
}