可以申请静态的结点数组,则Delete操作只要把数组的指针置为首地址/*内*/
#define keyNum 26
#define maxSize 10000
struct TrieNode{
TrieNode *link[keyNum];
int num[keyNum];
bool iselement[keyNum];
void init(){
memset(link,0,sizeof(link));
memset(num,0,sizeof(num));
memset(iselement,0,sizeof(iselement));
}
};
/**//*
TrieNode tn[maxSize];
TrieNode *cnt= tn;
*/
class TrieTree{
public:
TrieNode* root;
TrieTree(){
root= 0;
}
void Init(){
root= new TrieNode;
/**//*root= cnt++;*/
root->init();
}
bool Search( char *x ){
if( *x==0 ) return false;
TrieNode* current= root;
while( *x ){
if( current->link[*x-'a'] )
current= current->link[*x-'a'];
else break;
x++;
}
if( current->iselement[*x-'a'] || *x==0 )
return true;
else
return false;
}
void Insert( char x[] ){
TrieNode *current= root;
int i= 1;
while( x[i] ){
if( current->link[x[i-1]-'a']==NULL ){
current->link[x[i-1]-'a']= new TrieNode;
/**//*current->link[x[i-1]-'a']= cnt++;*/
(current->link[x[i-1]-'a'])->init();
}
current= current->link[x[i-1]-'a'];
i++;
}
(current->num[x[i-1]-'a'])++;
current->iselement[x[i-1]-'a']= true;
}
void Delete( TrieNode* t ){
int i;
for( i= 0; i<keyNum; i++ )
if( t->link[i] ) Delete(t->link[i]);
memset( t->num,0,sizeof(t->num) );
memset( t->iselement,0,sizeof(t->iselement) );
delete(t);
/**//*cnt= tn;*/
}
};
posted on 2009-03-17 22:14
古月残辉 阅读(294)
评论(0) 编辑 收藏 引用 所属分类:
Template