题目大意：
模拟手机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;inext[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;i0;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");
}
}