C++字典树

　　很多时候，学习总是止于实现，因为有很多这样或者那样的问题。即便是你理解了这种结构，但是实现起来却是另外一番天地，实践，看源码，然后继续实现是现阶段我应该完成的事情。

　　这次来学习一下字典树。

　　字典树，就是对树结构的一种特殊处理。对于英文词典来说，26个英文字母可以任意组合，那么这个树必然是26叉的。那么这个树有啥子作用，

　　1.字典树在串的快速检索中的应用。

　　给出N个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。在这道题中，我们可以用字典树，先把熟词建一棵树，然后读入文章进行比较，这种方法效率是比较高的。

　　2. 字典树在“串”排序方面的应用

　　给定N个互不相同的仅由一个单词构成的英文名，让你将他们按字典序从小到大输出用字典树进行排序，采用数组的方式创建字典树，这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可。

　　3. 字典树在最长公共前缀问题的应用

　　对所有串建立字典树，对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数，于是，问题就转化为最近公共祖先问题。

　　在看别人代码的过程中，我出现了很多疑问。第一个是封装类中类方法的调用，应该是分为静态类方法和实例类方法。实例类方法是需要先实例化的。另外一个问题是struct和class 在C++中的区别，区别不大只是缺省关键词public和private时，struct是pub，而class是pri。

//
//  main.cpp
//  yy
//
//  Created by MadMarical on 15/11/25.
//  Copyright (c) 2015年 com. All rights reserved.
//

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdexcept>

using namespace std;

struct Node
{
    bool isWord;//判断当前字母是否为单词的最后一个字母标识
    Node *next[26];//26叉
    Node()
    {
        isWord = false;
        for(int i = 0;i != 26; ++ i)
        {
            next[i] = NULL;//清空26叉
        }
    }
};
class DicTree
{
public:
    Node *root;//根节点
    DicTree()
    {
        root = NULL;//在构造函数中初始化
    }
    void Insert(string str)
    {
        if (!root)
        {
            root = new Node;//如果root现在不空，需要重新开辟一个根节点
        }
        Node *head = root;//根节点不能变，找一个新的指针指向根节点方便操作
        for(long int i = 0;i != str.length(); ++ i)
        {
            int num = str[i] - 'a';//获取当前字母应该存储的位置
            if (head ->next[num] == NULL)
            {
                head->next[num] = new Node;
            }
            head = head->next[num];
        }
        head->isWord = true;
    }
    bool Search(string str)
    {
        Node *head = root;
        for (long int i = 0; i != str.length(); ++ i)
        {
            int num = str[i] - 'a';
            if (head->next[num] == NULL)
            {
                return false;
            }
            else
            {
                head = head->next[num];
            }
        }
        return head->isWord;
    }
};

int main(int argc, const char * argv[])
{
    string inp1;
    cin>>inp1;
    DicTree A;
    A.Insert(inp1);
    
    string inp2;
    cin>>inp2;
    A.Search(inp2);
    return 0;
}

反思：

1.书到用时方恨少...快点读书...