Posted on 2012-05-03 16:17
C小加 阅读(451)
评论(0) 编辑 收藏 引用 所属分类:
解题报告
以前学数据结构的时候吧字典树忽视了，导致到现在才学到。
字典树是一种树形的数据结构，插入的复杂度为单词的平均长度。本题只需要写一个插入函数就可以了。
由于过几天就要省赛了，等到省赛后总结一下字典树。
// trietree.cpp : 定义控制台应用程序的入口点。
//
#include<cstdio>
#include<iostream>
#include<string.h>
using namespace std;
const int num_chars = 26; //关键码最大位
int _max;
char ans[12];
class Trie
{
public:
Trie();
Trie(Trie& tr);
virtual ~Trie();
//int trie_search(const char* word, char*entry) const;
bool insert(const char* word);
protected:
struct Trie_node //关键码类型
{
bool isfin;
int cnt; //关键码当前位数
Trie_node* branch[num_chars]; //关键码存放数组
Trie_node();
};
Trie_node* root;
};
Trie::Trie_node::Trie_node() //结点定义
{
isfin = false;
cnt = 0;
for(int i = 0; i < num_chars;++i)
branch[i] = NULL;
}
Trie::Trie():root(NULL)
{
}
Trie::~Trie()
{
}
bool Trie::insert(const char*word)
{
int result = 1,position = 0;
if(root == NULL)
root = new Trie_node;
char char_code;
Trie_node *location = root;
while(location != NULL && *word != 0)
{
if(*word >= 'a'&& *word <= 'z')
char_code = *word - 'a';
if(location->branch[char_code] == NULL)
location->branch[char_code] = new Trie_node;
location = location->branch[char_code];
position++;
word++;
}
++location->cnt;
if(location->cnt>_max)
{
_max=location->cnt;
return true;
}
else
return false;
}
int main()
{
Trie t;
int n;
while(scanf("%d",&n)!=EOF)
{
_max=0;
char s[12];
for(int i=0;i<n;++i)
{
scanf("%s",s);
if(t.insert(s))
{
strcpy(ans,s);
}
}
printf("%s %d\n",ans,_max);
}
return 0;
}