Trie树

Trie主要用于字符串快速匹配的数据结构。如果用来构建 Trie 树的这一组字符串中，前缀重复的情况不是很多，那 Trie 树这种数据结构总体上来讲是比较费内存的，是一种空间换时间的解决问题思路。尽管比较耗费内存，但是对内存不敏感或者内存消耗在接受范围内的情况下，在 Trie 树中做字符串匹配还是非常高效的，时间复杂度是 O(k)，k 表示要匹配的字符串的长度。Trie 树最有优势的是查找前缀匹配的字符串，比如搜索引擎中的关键词提示功能这个场景，就比较适合用它来解决，也是 Trie 树比较经典的应用场景。

Trie树的实现：

typedef struct TrieNode{
    int nCount;
    struct TrieNode *next[maxn];
}Trie;
Trie root;
void InitTrie(){
    for(int i=0;i<maxn;i++)
        root.next[i] = NULL;
}
//创建Trie树
void createTrie(char *str)
{
    int len = strlen(str);
    Trie *p=&root,*q;
    for(int i=0;i<len;i++){
        int k = str[i]-'a';
        if(p->next[k]==NULL){//root的指针数组的下标表示第一个字母
            q=(Trie*)malloc(sizeof(root));
            q->nCount = 1;
            for(int j=0;j<maxn;j++)
                q->next[j]=NULL;
            p->next[k]=q;
            p=p->next[k];
        }
        else {
            p->next[k]->nCount++;
            p=p->next[k];
        }
    }
}

循环向Trie树插入即可

查找字符串的代码如下

int findTrie(char *str)
{
    int len =strlen(str);
    Trie *p=&root;
    for(int i=0;i<len;i++){
        int k = str[i]-'a';
        if(p->next[k]==NULL) return 0;
        p=p->next[k]; 
    }
    return p->nCount;//nCount表示这个字符串在字符串组中有多少个
}

时间复杂度为O(k),k为待查字符串的长度