读书人

有关字典树的有关问题咋就没人指点小

发布时间: 2012-05-02 15:36:04 作者: rapoo

有关字典树的问题,咋就没人指点我恁
#include <iostream>
using namespace std;
const int branchNum = 26; //声明常量
int i;
struct Trie_node
{
bool isStr; //记录此处是否构成一个串。
Trie_node *next[branchNum];//指向各个子树的指针,下标0-25代表26字符
/*Trie_node():isStr(false)
{
memset(next,NULL,sizeof(next));
}*/
Trie_node();
};
Trie_node::Trie_node(){
isStr = false;
for(int i=0;i<branchNum;i++){
next[i] = NULL;
}


}
class Trie
{
public:
Trie();
int insert(const char* word);
bool search(char* word);
void deleteTrie(Trie_node *root);
private:
Trie_node* root;
};

Trie::Trie()
{
root = new Trie_node();
}

int Trie::insert(const char* word)
{
Trie_node *location = root;
int pos = -1;
while(*word)
{
if(*word>='a'&&*word<='z'){
pos = *word-'a';
}
else if(*word>='A'&&*word<='Z'){
pos = *word-'A';
}
else return 0;
if(location->next[pos] == NULL)//不存在则建立
{
Trie_node *tmp = new Trie_node();
location->next[pos] = tmp;
}
location = location->next[pos]; //每插入一步,相当于有一个新串经过,指针要向下移动
word++;
}
location->isStr = true; //到达尾部,标记一个串
return 1;
}
bool Trie::search(char *word)
{
Trie_node *location = root;
while(*word && location)
{
if (location->next[*word-'a'])
{
location = location->next[*word-'a'];
}

word++;
}
return(location!=NULL && location->isStr);

}

void Trie::deleteTrie(Trie_node *root)
{
for(i = 0; i < branchNum; i++)
{
if(root->next[i] != NULL)
{
deleteTrie(root->next[i]);
}
}
delete root;
}

int main() //简单测试
{
Trie t;
char text[200000];
char sor[10];
char* point_sor[20];
cout<<"请输入需要检索的文章:"<<endl;
cin>>text;
int count;
cout<<"请输入需要查询的次数:"<<endl;
cin>>count;
for(int i=0;i<count;i++){
cout<<"请输入检索关键字:"<<endl;
cin>>sor;
if(t.insert(sor)){//?????传过去的sor数组,是开辟了一段多叉树空间,可是也没见insert函数对空间里面存数组值啊???
//?????而且为什么要传关键字去插入呢?按照逻辑不是应该在插入时候传text,在查询时传sor么?
point_sor[i] = sor;
}
else{
cout<<sor<<"关键字输入不合法,请检查"<<endl;
}


}
cout<<"开始检索。。。。"<<endl;
for(int i=0;i<count;i++){
if(t.search(text)== true){//????既然是查找text里面是否还有sor,怎么只传递一个text参数呢????
cout<<"此文章含有关键字:"<<point_sor[i]<<endl;
}
else{
cout<<"此文章不含有关键字:"<<point_sor[i]<<endl;
}

}

system("pause");
return 1;
}

问题就是在注释里加了问号的,虽然我能把这个程序的流程看了一遍,也看了点字典树的原理,可是还是看不懂这个程序到底怎么就找关键字了,觉得参数啥的跟我想的都不一样。


还有我画了一张自己理解的图,发上来,大家看看我对这个树的建立想的对不对哦

[解决办法]
网上一搜一大堆,有时候别人说的还不如自己去看资料来的详细深刻。何况这种数据结构是别人无法用文字来说明的,还要结合图形,百度吧,上面有很多

读书人网 >软件架构设计

热点推荐