Trie

Tire树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。

说白了，就是一棵大树，这棵树的每个除了根节点的结点都存储了一个字符。

说在前面

字典树有两种实现方式，一种是利用指针实现，也就是一个实实在在的二十六叉树；另一种就是利用数组实现。（在这里分别称之为指针版字典树和数组版字典树）

两种实现方式各有优劣，指针版本的清晰明了，空间占用率相对较小（空间占用小就可以用剩下的空间干其他很多事）；而数组版字典树就是一次性把空间开好了，比较方便。

指针版字典树

结构体定义：

#define datatype int
typedef struct node{
    bool isEnd;
    datatype data;		//一般是计数
    struct node *letter[27];
}Node,*List;

新建一个结点的初始化：

List Initial(){
    List p = (List)malloc(sizeof(Node));
    memset(p,0,sizeof(Node));
    p->isEnd = false;
    return p;
}

当然，一种更加推荐的方式是使用calloc()函数，malloc()有更多自己操控的空间

List Initial(){
    List p = (List)calloc(sizeof(Node));
    return p;
}

创建一棵Trie:

#define MAXSIZE 1000
void createStopTrie(List *root, FILE *in) {
    int pos = 0;
    int len = fread(buffer, sizeof(char), MAXSIZE, in);
    char ch;
    int depth = 0;
    List end = *root;
    while (pos < len) {
        ch = tolower(buffer[pos]);
        if (islower(ch)) {
            if (end->letter[ch - 'a'] == NULL) {
                end->letter[ch - 'a'] = Initial();
            }
            end = end->letter[ch - 'a'];
            pos++;
            depth++;
        } else {
            end->isEnd = true;
            pos++;
            end = *root;
            if (depth > Depth) Depth = depth;
            depth = 0;
        }
    }
}

调用前需要

Root = Initial();
createArticleTrie(&Root,fp);

三个基本性质：

• 根节点不包含字符，除根节点的每一个节点都只包含一个字符。
• 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
• 每个节点的所有子节点包含的字符都不相同

我觉得这个像是一个26叉树，也有一点想26进制的一个东西。

我们这里存储的都是小写字母，如果包含又大写字母的话可能就是一个52叉树了。一般不会出现这种情况吧，出现了也不怪我

主要实现单词的高效存储与高效查找

利用cout[i]来记录以i为编号的字符结尾的字符串的个数。

就有两个基本操作

#include <stdio.h>
const int N = 1e5 + 5;
int tr[N][27], cou[N], idx;
char str[N];

void insert(char *s)
{
  int p = 0;
  for (int i = 0; s[i]; i++)
  {
    int u = (s[i] - 'a');
    if (!tr[p][u])
      tr[p][u] = ++idx;
    p = tr[p][u];
  }
  cou[p]++;
}

int query(char *s)
{
  int p = 0;
  for (int i = 0; s[i]; i++)
  {
    int u = (s[i] - 'a');
    if (!tr[p][u])
      return 0;
    p = tr[p][u];
  }
  return cou[p];
}

参考资料：

1. https://blog.csdn.net/forever_dreams/article/details/81009580
2. https://zhuanlan.zhihu.com/p/28891541
3. https://blog.csdn.net/weixin_42815609/article/details/102692411
4. 用C++讲得很清楚：https://blog.csdn.net/weixin_44176696/article/details/104716191
5. 这个有头文件诶，高级！：https://blog.csdn.net/A951860555/article/details/108716487