字典樹的應用 單詞意義查找-C語言實現

實現根據單詞快速找到對應的解釋

    / 
    字典樹應用，快速單詞查找  
    /


const int M = 1000000;  
char word[1000000][11];  
int wp; // 單詞列表的下標   
struct node{  
    int next[26];  
    int value;  
    bool end;  
} tree[M]; // 可用節點數組，相當于內存池   
int pi = 1; // 代表空閑的節點位置   
void init(){  
    memset(tree,0,sizeof(tree));  
    pi = 1; // 頭節點占用0，空閑節點從1開始   
    wp = 0;  
}  
void insert(char * keyword,int value){  
    int index,p,i; // p代表當前的節點，開始為根節點   
    for(i=p=0;keyword[i];i++){  
        index = keyword[i] - 'a';  
        if(tree[p].next[index] == 0)  
            tree[p].next[index] = pi++;  
        p = tree[p].next[index];   
    }  
    tree[p].value = value;  
    tree[p].end = 1;  
}  
bool query(char * keyword, int &value){  
    int index,p,i;  
    for(i=p=0;keyword[i];i++){  
        index = keyword[i] - 'a';         
        if(tree[p].next[index] == 0)  
            return 0;  
        p = tree[p].next[index];  
    }  
    if(tree[p].end){  
        value = tree[p].value;  
        return 1;   
    }  
    return 0;  
}  
int main(){  
    char s1[15],s2[15],s[30];  
    int i,value;  
    while(gets(s)){  
        if(!strlen(s))  
            break;  
        for(i=0;i<strlen(s);i++){  
            if(s[i]==' ')  
                break;  
        }  
        strncpy(s1,s,i); // say speak ==> say  
        s1[i] = 0;  
        strcpy(s2,s+i+1);  
        strcpy(word[wp],s1); // 單詞數組（二維）   
        insert(s2,wp++); // 含義插入字典樹，應用時根據含義找單詞，用下標wp進行關聯   
    }  
    while(scanf("%s",s)!=EOF){  
        if(query(s,value))  
            cout<<word[value]<<endl;  
        else  
            cout<<"no the word"<<endl;  
        }  
}  </pre>