首页 > 开发 > C++ > 正文

关于用C从txt文件查找单词的搜索算法优化问题

2017-09-11 21:35:44  来源: 网友分享

用C或C++实现从一个比较大的txt文件里查找一个单词,txt文件里每行一个单词,按a~z从上到下排列,有什么好的算法,用什么数据结构可以提高查询的速度和效率??

解决方案

这种情况考虑下面这种数据结构: 字典树(DictTree)

typedef struct _dict_tree_
{
    struct _dict_tree_ * dt[TREENODENUM];
    char    c ;
    char    flag ;
}DT ;

具体操作就是

所谓的26叉树,按照每个字母对应的子节点存储。 然后逐行读取单词后插入到树中,比如说: 单词:abandon 插入树的顺序就是 a->b->a->n->d->o->n 插入每个字母对应这个树的子节点

int len = strlen(str);
while( i < len )
{
    index = str[i] - 97 ;u3000u3000u3000u3000u3000u3000u3000u3000/*通过 index 来找到子节点*/
    if( pt->dt[index] == NULL )
    {
        pt->dt[index] = ( DT *)malloc( sizeof( DT) );
        pt->dt[index]->c = str[i] ;
        pt->dt[index]->flag = EMPTY ;
        for( j = 0 ; j < TREENODENUM ; j++ )
        {
            pt->dt[index]->dt[j] = NULL ;
        }
    }
    pt = pt->dt[index] ;
    i++;
}

查找就是顺着字母判断子节点是否为空

int len = strlen(str);
while( i != len )
{
    index = str[i] - 97 ;
    if( pt->dt[index] == NULL )
        return 0 ;
    pt = pt->dt[index] ;
    i++;
}