字符串处理的方法有很多比如说Hash,Trie,但主要还是想说三叉树,这里有篇博文讲的挺好

     Hash主要是通过一个hash函数来建立一个字符串与目标的映射,Hash函数的选择与查找效率有很大关系,网上很多这方面的介绍。

     Trie树是一种树状结构,这里有说明当然网上还可以找到更好的介绍。其没扩展一个节点会,会扩展出26(若是只处理普通字符,不区分大小写)个节点,大大的浪费了存储空间。其代码如下:
 1 const int M=26;
 2 const char CH='A';
 3 struct node
 4 {
 5     bool isend;
 6     node* child[M];
 7     node()
 8     {
 9         isend=false;
10         for(int i=0;i<M;++i)
11             child[i]=NULL;
12     }
13 };
14 node *root;
15 void Insert(char str[],node* &root)
16 {
17     if(root==NULL)
18         root=new node;
19     node* p=root;
20     int i=0;
21     while(str[i]!='\0')
22     {
23         if(p->child[str[i]-CH]==NULL)
24             p->child[str[i]-CH]=new node;
25         p=p->child[str[i]-CH];
26         ++i;
27     }
28     p->isend=true;
29 }
30 bool Seach(char str[],node* root)
31 {
32     node* p=root; 
33     int i=0;
34     while(str[i]!='\0')
35     {
36         if(p->child[str[i]-CH]==NULL)
37             return false;
38         else p=p->child[str[i]-CH];
39         ++i;
40     }
41     if(p->isend) return true;
42     else return false;
43     
44  }

    三叉树有trie的优点,却又比trie占用的空间小,好像这个东西比trie更加实用,并且效率不赖,很多网站的实时补充单词(即,输入单词的前缀会自动补充后半部分单词)就是用它。三叉树的每个节点会有一个key,左子树,右子树,中间子树。查找或是插入类似于二叉树,若是插入的数据大于key就插入左子树,若是大于key就插入右子树,等于key插入中间子树(好像叫起来不顺口),当然反之亦可。其具体实现代码如下:
 1 struct node
 2 {
 3     node* l;
 4     node* r;
 5     node* mid;
 6     char key;
 7     bool isend;
 8     node():l(NULL),r(NULL),mid(NULL),isend(false),key(0){}
 9 };
10 void insert(char *str,node* &root)
11 {
12     if(root==NULL)
13     {
14         root=new node;
15         root->key=str[0];
16     }
17     node* p=root;
18     node* t=p;
19     while(*str)
20     {
21         if(*str>p->key)
22         {
23             if(p->r==NULL)
24             {
25                 p->r=new node;
26                 p->r->key=*str;
27             }
28             p=p->r;
29         }
30         else if(*str<p->key)
31         {
32             if(p->l==NULL)
33             {
34                 p->l=new node;
35                 p->l->key=*str;
36             }
37             p=p->l;
38         }
39         else 
40         {
41             ++str;
42             if(*str=='\0'break;
43             if(p->mid==NULL)
44             {
45                 p->mid=new node;
46                 p->mid->key=*str;
47             }
48             p=p->mid;
49         }
50     }
51     p->isend=true;
52 }
53 bool search(char *str,node* root)
54 {
55     while(*str)
56     {
57         if(*str> root->key)
58         {
59             root=root->r;
60         }
61         else if(*str<root->key)
62         {
63             root=root->l;
64         }
65         else 
66         {
67             ++str;
68             if(*str!='\0')
69                 root=root->mid;    
70         }
71         if(root==NULL) return false;
72     }
73     if(root->isend)  return true;
74     else return false;
75 }