动物统计加强版
时间限制：3000 ms | 内存限制：150000 KB
难度：4
- 描述
- 在美丽大兴安岭原始森林中存在数量繁多的物种，在勘察员带来的各种动物资料中有未统计数量的原始动物的名单。科学家想判断这片森林中哪种动物的数量最多，但是由于数据太过庞大，科学家终于忍受不了，想请聪明如你的ACMer来帮忙。
- 输入
- 第一行输入动物名字的数量N(1<= N <= 4000000),接下来的N行输入N个字符串表示动物的名字（字符串的长度不超过10,字符串全为小写字母，并且只有一组测试数据）。
- 输出
- 输出这些动物中最多的动物的名字与数量，并用空格隔开（数据保证最多的动物不会出现两种以上）。
- 样例输入
-
10 boar pig sheep gazelle sheep sheep alpaca alpaca marmot mole
- 样例输出
-
sheep 3
字典树的应用
字典树：是一种用于快速检索的多叉树结构。字典树把要查找的关键词看作一个字符序列，并根据构成关键词字符的先后顺序构造用于检索的树结构；一棵m度的字典树树或者为空，或者由m棵m度的Trie树构成。
特点：
利用串的公共前缀->节约内存
根结点不包含任何字母
其余结点仅包含一个字母(非元素)
每个结点的子节点包含字母不同
字典树的查找（最主要的操作）
(1)在trie树上进行检索总是始于根结点。
(2)取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索。
(3)在某个结点处，关相应的子树上，取得要查找关键词的第二个字母，并进一步选择对应的子树进行检索。
(4) ...
键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。
Trie的数据结构定义
struct dictree
{
dictree *child[26];
int n; //根据需要变化
};
dictree *root;
特点：数据量大
主要任务：查找单词
解决方法：字典树
字典树结构（除指针）：单词信息（英文）
HDOJ-1075 What Are You Talking About
HDOJ-1251 统计难题
HDOJ-1298 T9
HDOJ-1800 Flying to the Mars
ZOJ-1109 Language of FatMouse
第一步：1.建立字典树，
第一次思想（错误）：
从第一层向下统计，每次都找到每层次数最多的（这里错误！！）
如测试数据：
5
abc
ade
afr
bb
bb
错误代码：
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
using namespace std;
typedef struct dictree
{
dictree * child[26];
int cnt;
}dictree;
void find(dictree * root)
{
int i,j;
int flag = 1;
for(i=0;i<26;i++) if(root->child[i]) flag = 0;
if(flag){
printf(" %d\n",root->cnt);
return;
}
dictree *p;
dictree *q;
q = root;
int index;
int max = 0;
for(i=0;i<26;i++)//寻找该层次数最大的然后向下查找，！！！这里错误 r如： abc acd aef bb bb 则先从a向下找了，错误！！！！
{
p=q->child[i];
if(p)
{
if(max<p->cnt)
{
max=p->cnt;
index = i;
}
}
}
p = q->child[index];
if(p)
{
printf("%c",index+'a');
find(p);
}
}
void insert(dictree * &root,char s[])//建立字典树
{
int j,i;
dictree *p;
dictree *q;
q = root;
for(i=0;i<strlen(s);i++)
{
if(q->child[s[i]-'a'])
{
q = q->child[s[i]-'a'];
q->cnt++;
}
else
{
p = (dictree * )malloc(sizeof(dictree));//分配p
p->cnt = 1;
for(j=0;j<26;j++) p->child[j] = NULL;
q->child[s[i]-'a'] = p;
q = p;
}
}
}
int main()
{
int i;
dictree * root;
root=(dictree *)malloc(sizeof(dictree));
for(i=0;i<26;i++) root->child[i] = NULL;
int n;
char s[11];
scanf("%d",&n);
while(n--)
{
scanf("%s",s);
insert(root,s);
}
find(root);
return 0;
}
第二次：
统计每个单词最后一个字母的出现次数，找最多的，但是找的过程中错误
建树过程中只统计最后一个单词出现次数，不能每个字母都统计次数
如：
5
abcde
abcde
abcde
ab
ab
此时b是5词，但ab不是最多的，所以会出错。。。！！！！
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
using namespace std;
typedef struct dictree
{
dictree * child[26];
int cnt;
}dictree;
char str[12];
int num;
void insert(dictree * &root,char s[])
{
int j,i;
dictree *p;
dictree *q;
q = root;
for(i=0;i<strlen(s);i++)
{
if(q->child[s[i]-'a'])
{
q = q->child[s[i]-'a'];
q->cnt++;//这里错误，应该放到外面++
}
else
{
p = (dictree * )malloc(sizeof(dictree));//分配p
p->cnt = 1;
for(j=0;j<26;j++) p->child[j] = NULL;
q->child[s[i]-'a'] = p;
q = p;
}
}
if(q->cnt>num) {//单词结束后，看最后一个字母出现次数
num = q->cnt;
strcpy(str,s);
}
}
int main()
{
int i;
dictree * root;
root=(dictree *)malloc(sizeof(dictree));
for(i=0;i<26;i++) root->child[i] = NULL;
int n;
char s[12];
scanf("%d",&n);
num=0;
while(n--)
{
scanf("%s",s);
// puts(s);
insert(root,s);
}
printf("%s %d\n",str,num);
return 0;
}
最后AC代码：
将前面的都改进
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
using namespace std;
typedef struct dictree
{
dictree * child[26];
int cnt;
}dictree;
char str[11];
int num;
void insert(dictree * &root,char s[])
{
int j,i;
dictree *p;
dictree *q;
q = root;
for(i=0;i<strlen(s);i++)
{
if(q->child[s[i]-'a'])
{
q = q->child[s[i]-'a'];
}
else
{
p = (dictree * )malloc(sizeof(dictree));//分配p
p->cnt = 0;
for(j=0;j<26;j++) p->child[j] = NULL;
q->child[s[i]-'a'] = p;
q = p;
}
}
q->cnt++;//这里放到外面，只统计最后一个字母出现次数
if(q->cnt>num) {
num = q->cnt;
strcpy(str,s);
}
}
int main()
{
int i;
dictree * root;
root=(dictree *)malloc(sizeof(dictree));
for(i=0;i<26;i++) root->child[i] = NULL;
int n;
char s[11];
scanf("%d",&n);
while(n--)
{
scanf("%s",s);
insert(root,s);
}
printf("%s %d\n",str,num);
return 0;
}