有关字典树的有关问题
有关字典树的问题
代码如下:#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 <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;
}
不好意思,代码有点长了,我第一次接触字典树相关内容,然后老师发给了一段代码,是错的,我也能看出来肯定不对,可是第一次接触不知道怎么修改,而且网上找到的正确的又看不大懂
辛苦大家指点我下,多谢了
------解决方案--------------------
楼主,我要怎样输入数据,给个参考
------解决方案--------------------
而且还没注释