注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

云水居

云在青山水在天,人在江湖不得闲

 
 
 

日志

 
 

Trie字典树做个命令行小字典  

2010-10-08 11:47:24|  分类: Develop |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
用Trie字典树的数据结构,利用Ubuntu自带的words文件,做个小字典
首先将/usr/share/dict/words中的所有文件读入内存,并用Trie字典树的方式保存,用户从命令行输入单词前缀,程序定位字典树的位置,并输出所有此前缀的单词
注意:不支持特殊字符,所有特殊字符以?显示
运行结果:
./dict
>joker
joker
joker's
jokers
>popo
popover
popover's
popovers
可以发现原始字典将 <word> <word>'s <word>s三种形式分别存储为三个单词,如果在存储时判别这些情况,这可以节省大量存储空间。

源代码如下
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
#define N 600000
#define toint(c) (c=='\''?0: c>='a'&&c<='z'?26+c-'a'+1: c>='A'&&c<='Z'?c-'A'+1:53)
#define tochar(i) (i==0?'\'':i<=26?'A'+i-1: i<53?i-26+'a'-1:'?')

typedef struct node{
    struct node *son[54];
    bool isword;
}node;
node pool[N];
node *root = &pool[0];    //root
int nodei=0;

void add(char *word){//向字典中加入单词
    node *cur = root;
    for(char *p=word;*p;p++){
    if(cur->son[toint(*p)]==NULL)
        cur->son[toint(*p)]=&pool[++nodei];
    cur = cur->son[toint(*p)];
    }
    cur->isword=true;
}
char tmp[256];
void iter(node *cur,int level){//从第level层为cur处开始,遍历字典,输出所有单词
    if(cur->isword){
    tmp[level]='\0';
    cout<<tmp<<endl;
    }
    for(int i=0;i<54;i++){
    if(cur->son[i] != NULL){
        tmp[level]=tochar(i);
        iter(cur->son[i], level+1);
    }
    }
}
node* locate(int level){//定位长度为level,内容为tmp的前缀的位置,不存在则返回NULL
    node *cur=root;
    for(int i=0;i<level;i++){
    cur = cur->son[toint(tmp[i])];
    if(cur==NULL)
        return cur;
    }
    return cur;
}
ifstream fin("/usr/share/dict/words");
int main(){
    while(fin>>tmp){//读入字典
    if(tmp[0]==0) continue;
    add(tmp);
    }
    printf(">");
    //iter(root,0); //
    while(cin>>tmp){//用户输出
    node *pos=locate(strlen(tmp));//定位前缀
    if(pos==NULL)
        printf("No words\n");
    else
        iter(pos, strlen(tmp));//输出结果
    printf(">");
    }
    return 0;
}
  评论这张
 
阅读(840)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017