有关字典树的问题
代码如下:#include <iostream>
using namespace std;
const int branchNum = 26;?
int i;
struct Trie_node
{
bool isStr;?
Trie_node *next[branchNum];
/*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,int length);?
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,int length)
{
? Trie_node *location = root;
? int len = 0;
? while(*word && location)
? {
? if (location->next[*word-'a'])
? {
location = location->next[*word-'a'];
len++;
? }
? else{
len = 0;
}
? word++;
}
? return(location!=NULL && location->isStr&&len==length);
??
}
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) == 1){
point_sor[i] = sor;
}
else{
cout<<sor<<"关键字输入不合法"<<endl;?
}
? ?
? }?
? for(int i=0;i<count;i++){
? if(t.search(text,strlen(point_sor[i]))== true){
cout<<"文中含关键字"<<point_sor[i]<<endl;
}
else{
cout<<"文中不含关键字"<<point_sor[i]<<endl;
}?
? }?
? ?
? system("pause");
? return 1;
}
不好意思,代码有点长了,我第一次接触字典树相关内容,然后老师发给了一段代码,是错的,我也能看出来肯定不对,可是第一次接触不知道怎么修改,而且网上找到的正确的又看不大懂
辛苦大家指点我下,多谢了
[解决办法]
楼主,我要怎样输入数据,给个参考
[解决办法]
而且还没注释
有关字典树的有关问题
有关字典树的问题代码如下:#include iostreamusing namespace stdconst int branchNum 26? int ist
