Let the Balloon Rise（hdu 1004）（trie tree）

本文主要是介绍Let the Balloon Rise（hdu 1004）（trie tree），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Let the Balloon Rise（hdu 1004）

ACM比赛，裁判们最大的乐趣就是猜所有队伍做出哪道题的数量最多。比赛结束时，他们开始数挂出的哪种颜色气球的数量最多，即知道了他们猜测的结果。
今年，他们决定将这个有趣的工作交给你。 

输入：

输入包括多组数据。每组数据以一个整数N (0 < N <= 1000) 开始，下面N行每行为一个气球的颜色。气球的颜色为一个只包含小写英文字母的字符串，且字符串长度不超过15。
当 N = 0 时，测试数据结束，且该组数据不用处理。

输出：

对于每组测试数据，你应该输出出现次数最多的气球颜色。每组数据其结果一定是惟一的。

输入样例：

5 

green 

red 

blue 

red 

red 

3 

pink 

orange 

pink 

0

输出样例：

red 

pink

分析：

把每个单词插入到Trie树里，记录单词出现的次数。再查找Trie树，那个单词出现的次数最多即为输出结果。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;typedef struct node//节点结构
{struct node * next[26];int value;int num;
}*trie, node;
trie root;void init_trie(trie &p)//trie树初始化
{p = (trie) malloc ( sizeof(node) );for(int i = 0; i < 26; i++)p->next[i] = 0;p->value = p->num = 0;
}void insert(trie p,char s[])//插入操作
{int k = 0;while(s[k] != '\0'){if( ! p->next[s[k]-'a']){trie q;init_trie(q);p->next[s[k]-'a'] = q;}p = p->next[s[k]-'a'];p->num ++;k++;}p->value = 1;
}int find(trie p,char s[])//插找
{int k = 0;while(s[k] != '\0' && p->next[s[k]-'a']){p = p->next[s[k]-'a'];k++;}if(s[k]=='\0')return p->num;return 0;
}int main()
{int n;while(scanf("%d",&n) != EOF && n){init_trie(root);char ch[1005][17];for(int i = 0; i < n; i++){cin>>ch[i];insert(root, ch[i]);}int max = 0, tem, f;for(int i = 0; i < n; i++){tem = find(root, ch[i]);if(tem > max){max = tem;f = i;}}cout<< ch[f] << "\n";}return 0;

这篇关于Let the Balloon Rise（hdu 1004）（trie tree）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---