Posted on 2012-05-03 16:17
C小加 閱讀(457)
評論(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;
}