poj 3630(Phone List)

单纯的trie树。

code:

#include<cstring>
#include<cstdio>

char str[100] ;//模式串#define MAX 26 //字符集大小
typedef struct TrieNode{
    int count ; //记录该字符出现次数
    bool f ;
    struct TrieNode *next[MAX] ;
}TrieNode ;

TrieNode Memory[1000000] ;
int allocp = 0 ;

/*初始化*/
void InitTrieRoot(TrieNode **pRoot){
    *pRoot = NULL ;
}

/*创建新结点*/
TrieNode *CreateTrieNode(){
    int i ;
    TrieNode *p ;

    p = &Memory[allocp++] ;
    p->count = 1 ;
    p->f = false ;
    for(i=0; i<MAX; i++){
        p->next[i] = NULL ;
    }
    return p ;
}

/*插入*/
bool InsertTrie(TrieNode **pRoot, char *s){
    int i, k, c ;
    TrieNode *p ;
    if(!(p=*pRoot)){
        p = *pRoot = CreateTrieNode() ;
    }
    i = c = 0 ;
    while(s[i]){
        k = s[i++] - '0' ; //确定branch
        if(p->next[k]){
            p->next[k]->count ++ ;
            if(p->next[k]->f)    return false ;
            c ++ ;
        }
        else
            p->next[k] = CreateTrieNode() ;
        p = p->next[k] ;
    }
    p->f = true ;
    if(c==strlen(s))    return false ;
    return true ;
}

//查找
int SearchTrie(TrieNode **pRoot, char *s){
    TrieNode *p ;
    int i , k ;

    if(!(p=*pRoot))
        return 0 ;
    i = 0 ;
    while(s[i]){
        k = s[i++] - '0' ;
        if(p->next[k]==NULL)    return 0 ;
        p = p->next[k] ;
    }
    return p->count ;
}
int main(){
    int n , i, t ;
    bool f ;
    scanf("%d", &t) ;
    while(t--){
        allocp = 0 ;
        TrieNode *root = NULL ;
        InitTrieRoot(&root) ;
        scanf("%d", &n) ;
        f = true ;
        for(i=0; i<n; i++){
            getchar() ;
            scanf("%s", str) ;
            if(f)
                f = InsertTrie(&root, str) ;
        }
        if(f)   printf("YES\n") ;
        else    printf("NO\n") ;
    }
    return 0 ;
}