字典树的应用 单词意义查找-C语言实现

2018-07-20    来源:open-open

容器云强势上线!快速搭建集群,上万Linux镜像随意使用
实现根据单词快速找到对应的解释
    /* 
    字典树应用,快速单词查找  
    */  
      
    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;  
            }  
    }  

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点!
本站所提供的图片等素材,版权归原作者所有,如需使用,请与原作者联系。

上一篇:C# WinForm获取当前路径汇总

下一篇:c# xml操作类 比较齐全