返回顶部

收藏

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

更多

实现根据单词快速找到对应的解释```cpp / 字典树应用,快速单词查找

/

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;  
        }  
}

```

标签:c/c++

收藏

0人收藏

支持

0

反对

0

相关聚客文章
  1. yuer 发表 2018-07-27 08:46:07 coredump之百米之内必有解药
  2. hev 发表 2018-04-28 06:11:38 一个简单、轻量的 Linux 协程实现
  3. hev 发表 2017-10-19 15:56:11 FSH – 助你接入私有网络中的 Linux 终端
  4. gonwan 发表 2015-04-15 08:03:07 Database Access Layer in C++
  5. gonwan 发表 2015-12-28 08:41:13 Basic Usage of Boost MultiIndex Containers
  6. gonwan 发表 2016-01-19 03:37:54 Coroutines in C++/Boost
  7. Haoxiang Li 发表 2017-10-25 20:29:02 MXNet C++ Deployment
  8. yuer 发表 2017-10-20 07:52:47 基于leveldb的持久消息队列SDK
  9. yuer 发表 2017-10-07 07:51:32 c++11完美转发
  10. 博主 发表 2016-09-03 00:00:00 C++编译期类型信息的利用
  11. yuer 发表 2017-09-06 03:03:29 libcurl访问unix socket
  12. yuer 发表 2017-09-07 08:14:58 valgrind检测php扩展的warning

发表评论