返回信息流一个trie树的简单应用.
先在此谢谢啦.
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std ;
class trie
{
private :
int sum;
trie* next[26];
public :
trie():sum(0)
{
for(int i=0;i<26;i++)
next[i]=NULL;
}
~trie ()
{
int i ;
for ( i = 0 ; i < 26 ; i++ )
{
delete next[i] ;
}
}
void insert(string& str)
{
trie* tmp=this;
for(int i=0;i<str.size();i++)
{
str[i]|=0x20;
tmp=tmp->next[str[i]-'a'];
if(tmp==NULL)
{
tmp=new trie;
}
else
tmp->sum++;
}
}
int quary ( string& str )
{
trie* tmp=this;
int n=0;
for(int i=0;i<str.size();i++)
{
str[i]|=0x20;
tmp=tmp->next[str[i]-'a']; //这里tmp为什么总是NULL???????
n++;
if(tmp->sum==0) //导致这里出现段错误
break;
}
return n;
}
};
int main ()
{
string word;
trie t;
word=string("abcd");
t.insert(word);
t.quary(word);
return 0 ;
}
这是一条镜像帖。来源：北邮人论坛 / cpp / #38025同步于 2010/4/16
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
一个语法问题,困扰了一个上午
kmplayer
2010/4/16镜像同步2 回复
订阅后，新回复会通过你的通知中心匿名送达。
2 条回复
这样改
void insert(string& str)
{
trie* tmp=this;
for(int i=0;i<str.size();i++)
{
str[i]|=0x20;
if(tmp->next[str[i]-'a']==NULL) //你原来的代码压根没修改next[key]
{
tmp->next[str[i]-'a']=new trie;
}
tmp = tmp->next[str[i]-'a'];
tmp->sum++;
}
}
int quary ( string& str )
{
trie* tmp=this;
int n=0;
for(int i=0;i<str.size();i++)
{
printf("%d ",i);
str[i]|=0x20;
//这里要先判断有没有对应 key 的儿子
if(tmp->next[str[i]-'a'] == NULL){
//没这个词, 终止查询
}
tmp=tmp->next[str[i]-'a'];
n++;
if(tmp->sum==0)
break;
}
return n;
}
哦,明白了.
谢谢,非常感谢.
【 在 wolf5x 的大作中提到: 】
: 这样改
: void insert(string& str)
: {
: ...................