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