参考了人家的代码,还是写转载吧。
#include<iostream>
#include<cstring>
#define num_chars 26
//只能插入英文字母
using namespace std;
class Trid_node
{ private: char* words;int n;Trid_node* branch[num_chars];public:Trid_node(){ words=NULL;n=0;//匹配次数for(int i=0;i<num_chars;i++)branch[i]=NULL;}friend class Trid_Tree;
};
class Trid_Tree
{ private: Trid_node* root;char s[10];public:bool TTinsert(Trid_node* root,char* word);bool TTsearch(Trid_node* root,char* word);void TTprintall(Trid_node* root);Trid_Tree(){s[0]='\0';}
} ;
bool Trid_Tree::TTinsert(Trid_node* root,char* word)
{ if(word==NULL || root==NULL) return 0;char c;c=*word;int len=strlen(s);s[len]=c;s[len+1]='\0';if( c>='A' && c<='Z' ) c=c-'A';else if(c>='a' && c<='z') c=c-'a';if(root->branch[c]==NULL) { Trid_node* t=new(Trid_node);root->branch[c]=t;}word++;if( *word!='\0') {return TTinsert(root->branch[c],word);}else { (root->n)++; int i=strlen(s);root->words= new char[i+1];*(root->words)='\0';strcat(root->words,s);s[0]='\0';return 1; }
}
bool Trid_Tree::TTsearch(Trid_node* root,char *word)
{ if(!root)return 0;//保证word不空char c=*word;if(c>='A' && c<='Z') c=c-'A';else if(c>='a' && c<='z') c=c-'a';if(root->branch[c]==NULL)return 0;//不存在这个关键字word++;if(*word){ return TTsearch(root->branch[c],word); }//word不空,深入查else { if( root->n>0) return 1; //word空了else return 0;}
}
void Trid_Tree::TTprintall(Trid_node* root)
{ if(!root) return;if(root->words&& root->n) cout<<root->words<<endl;for(int i=0;i<26;i++)if(root->branch[i]) TTprintall(root->branch[i]);
}
int main()
{ Trid_node* root=new(Trid_node);Trid_Tree tt;tt.TTinsert(root,"green");tt.TTinsert(root,"blue");tt.TTinsert(root,"yellow");tt.TTinsert(root,"red");tt.TTinsert(root,"orange");tt.TTprintall(root);char s1[]="abcdedddddd";for(int i=0;i<=5;i++){ cin>>s1;cout<<tt.TTsearch(root,s1);}
}