字典树的基础，以及在实际项目中对于敏感词的替换的应用

最近刷题时连续遇到两道字典树的题目，所以做一下这个数据结构的总结。

首先什么叫做字典树？

叫

是

我想

看

听

这种树结构并且把文字或者英文放在里面组成的叫做字典树。

那么字典树有什么用呢？

通过几道题目的练习我发现，字典树主要应用在，对于字符串的分级匹配和查询。

比如在我们如果有三句话，1：我是人，2：我是男人，3：我是中国人

如果一般的我们用三个字符串去存放他们，然后当我们要寻找在这些字符串中是否存在我是中国人的时候，那么就需要一句句匹配过来，如果有1000条这样的数据，那么匹配的速度可想而知。

当我们用字典树去存放的时候，我们可以存放成这样

人

我是男人

中国人

这样我们从树的根部一直寻找下去，一个个字去寻找，如果有，那么就找下去，如果没有就不存在，这样寻找速度也是可想而知的。

然后下面是字典树在C中的定义，以及简单的应用

typedef struct Node
{
    int number;
    char word[120];
    Node *next[26];
    void init()
    {
        number = 0;
        memset(next,NULL,sizeof(next));
    }
}NODE,*PNODE;

当然一般的题目都是英文的，所以存放的是英文的字符串，所以其中的next用了26长度的数组

PNODE setNode()
{
    PNODE pNew = (PNODE) malloc(sizeof(NODE));
    pNew->init();
    return pNew;
}

创建一个新的节点

void insertNode(char st[120], int number)
{
    char temp[120];
    PNODE pNew = pHead;
    int length = strlen(st);
    int i,j;
    for (i = 0; i < length; i++)
    {
        j = st[i] - 'a';
        if(pNew->next[j] == NULL)
        {
            pNew->next[j] = setNode();
        }
        pNew = pNew->next[j];
        pNew->number += number;
        temp[i] = st[i];/*把每一段到这个节点为止的字符串赋值，并在最后赋值、0否则打印时会出错*/
        temp[i+1] = '

字典树的基础，以及在实际项目中对于敏感词的替换的应用

相关推荐