作者在 2012-03-22 13:27:25 发布以下内容
在美丽大兴安岭原始森林中存在数量繁多的物种，在勘察员带来的各种动物资料中有未统计数量的原始动物的名单。科学家想判断这片森林中哪种动物的数量最多，但是由于数据太过庞大，科学家终于忍受不了，想请聪明如你的ACMer来帮忙。
输入第一行输入动物名字的数量N(1<= N <= 10000),接下来的N行输入N个字符串表示动物的名字（字符串的长度不超过10,字符串全为小写字母，并且只有一组测试数据）。输出输出这些动物中最多的动物的名字与数量，并用空格隔开（数据保证最多的动物不会出现两种以上）。样例输入10 boar pig sheep gazelle sheep sheep alpaca alpaca marmot mole样例输出sheep 3#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct tree //定义字典树
{
struct tree *a[26];
int num;
}node,*Node;
Node root=(Node)malloc(sizeof(node));
void cls(Node root) //初始化字典树
{
for(int i=0;i<26;i++)
root->a[i]=NULL;
}
int insert(char *in) //对输入的字符串分别对应存入字典树内
{
int i,len=strlen(in);
Node current,new_node;
current=root;
for(i=0;i<len;i++)
{
int co=in[i]-'a';
if(current->a[co]==NULL) //下一个节点为空，建立新的节点
{
new_node=(Node)malloc(sizeof(node));
current->a[co]=new_node;
current=new_node;
current->num=0;
cls(current);
}
else
current=current->a[co];
}
current->num++;
return current->num; //返回与这个字符串相等的字符串的个数
}
int main()
{
int n,max=0;
char animal_1[11],animal_2[11];
scanf("%d%*c",&n);
cls(root);
while(n--)
{
gets(animal_1);
int su=insert(animal_1);//返回的字符串的个数与上一个字符串个数相比较
if(su>max)
{
strcpy(animal_2,animal_1);//把个数多的字符串存储到animal_2这个数组中
max=su;
}
}
printf("%s %d\n",animal_2,max);//输出
return 0;
}
#include <string.h>
#include <stdlib.h>
typedef struct tree //定义字典树
{
struct tree *a[26];
int num;
}node,*Node;
Node root=(Node)malloc(sizeof(node));
void cls(Node root) //初始化字典树
{
for(int i=0;i<26;i++)
root->a[i]=NULL;
}
int insert(char *in) //对输入的字符串分别对应存入字典树内
{
int i,len=strlen(in);
Node current,new_node;
current=root;
for(i=0;i<len;i++)
{
int co=in[i]-'a';
if(current->a[co]==NULL) //下一个节点为空，建立新的节点
{
new_node=(Node)malloc(sizeof(node));
current->a[co]=new_node;
current=new_node;
current->num=0;
cls(current);
}
else
current=current->a[co];
}
current->num++;
return current->num; //返回与这个字符串相等的字符串的个数
}
int main()
{
int n,max=0;
char animal_1[11],animal_2[11];
scanf("%d%*c",&n);
cls(root);
while(n--)
{
gets(animal_1);
int su=insert(animal_1);//返回的字符串的个数与上一个字符串个数相比较
if(su>max)
{
strcpy(animal_2,animal_1);//把个数多的字符串存储到animal_2这个数组中
max=su;
}
}
printf("%s %d\n",animal_2,max);//输出
return 0;
}