字典树 POJ2001
首次认识到Trie树的强大之处！简单易懂，只要对建立一般的树的方法有所了解就OK了。Trie树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
它有3个基本特性：
1）根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2）从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3）每个节点的所有子节点包含的字符都不相同。
http://poj.org/problem?id=2001
1 #include<iostream>
2 using namespace std;
3 const int chars = 26;
4 struct Trinode{
5 int num;
6 Trinode *next[chars];
7 Trinode(){
8 num = 0;
9 memset(next,0,sizeof(next));
10 }
11 };
12
13 Trinode *root = new Trinode;
14
15 void insert(char* str){
16 int i = 0;
17 Trinode *temp = root;
18 while(str[i]){//字符串遇到/0退出循环
19 int nextPos = str[i]-a;
20 if(temp->next[nextPos]==0)
21 temp->next[nextPos] = new Trinode;
22
23 temp = temp->next[nextPos];
24 temp->num++;
25 i++;
26 }
27 }
28
29 void search(char *str){
30 int i = 0;
31 Trinode*temp = root;
32 while(str[i]){
33补充：综合编程 , 其他综合 ,上一个：数据结构与算法（6）——哈希表
下一个：算法与数据结构（5）——二叉查找树CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络，
