字符串处理 Hash、Trie、三叉树

小城★徘徊 — Tue, 02 Feb 2010 16:33:00 GMT

     字符串处理的方法有很多比如说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 }

小城★徘徊 2010-02-03 00:33 发表评论

高精度计算 BigInt

小城★徘徊 — Sat, 30 Jan 2010 11:59:00 GMT

摘要: Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1 #include 2 #include 3 ... 阅读全文

小城★徘徊 2010-01-30 19:59 发表评论

C++博客-dhx123

字符串处理 Hash、Trie、三叉树

高精度计算 BigInt