随笔-20  评论-16  文章-36  trackbacks-0
可以申请静态的结点数组,则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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理