字典树的基本知识及使用C语言的相关实现

字典树的基本知识

字典树，英文名为Trie树，又称单词查找树或键树，是一种树形数据结构，用于表示关联数组或映射。它的优点是，可以大大减少无谓的字符串比较，查询效率比哈希表高。

字典树的核心概念是节点，每个节点包含一个字符和指向子节点的指针。根节点为空字符，每个字符串以一个独立的路径插入节点。如果一个字符串是另一个字符串的前缀，那么这个字符串的节点是另一个字符串节点的祖先节点。字典树的实现有多种，我们接下来主要介绍C语言实现。

C语言实现

字典树的结构体

typedef struct Trie {
    int isEnd;
    struct Trie* next[26];
} Trie;

上述代码中的Trie结构体包含一个布尔类型的isEnd成员和26个指向子节点的指针。如果isEnd为1，则当前字符串存在于字典树中。

字典树的插入操作

Trie* trieCreate() {
    Trie* node = (Trie*)malloc(sizeof(Trie));
    memset(node, 0, sizeof(Trie));
    return node;
}

void trieInsert(Trie* obj, char* word) {
    while (*word) {
        if (!obj->next[*word - 'a'])
            obj->next[*word - 'a'] = trieCreate();
        obj = obj->next[*word++ - 'a'];
    }
    obj->isEnd = 1;
}

上述代码中的trieCreate()函数负责创建一个新节点。trieInsert()函数负责插入一个新字符串到字典树中。具体做法是遍历字符串，若下一个字符对应的节点不存在，则创建一个新节点。最后将当前节点的isEnd成员设置为1，表示该字符串已插入到字典树中。

字典树的查询操作

bool trieSearch(Trie* obj, char* word) {
    while (*word) {
        if (!obj->next[*word - 'a'])
            return false;
        obj = obj->next[*word++ - 'a'];
    }
    return obj->isEnd;
}

上述代码中的trieSearch()函数负责查询一个字符串是否存在于字典树中。具体做法是遍历字符串，判断下一个字符对应的节点是否存在。如果节点不存在，则字符串不存在于字典树中；如果遍历完成后当前节点的isEnd成员为1，则表示字符串存在于字典树中。

示例演示

接下来我们用两个示例分别演示字典树的使用。

示例一

int main() {
    Trie* trie = trieCreate();
    trieInsert(trie, "apple");
    printf("%d\n", trieSearch(trie, "apple"));   // 1
    printf("%d\n", trieSearch(trie, "app"));     // 0
    printf("%d\n", trieSearch(trie, "applf"));   // 0
    trieInsert(trie, "app");
    printf("%d\n", trieSearch(trie, "app"));     // 1
    return 0;
}

上述代码中，我们首先创建一个新的字典树。然后插入一个单词"apple"。接下来进行多次查询，分别查询"apple"、"app"、"applf"是否存在于字典树中，结果分别是1、0、0。最后插入一个新单词"app"，再次查询"app"是否存在于字典树中，结果为1。

示例二

int main() {
    Trie* trie = trieCreate();
    trieInsert(trie, "cat");
    trieInsert(trie, "dog");
    trieInsert(trie, "car");
    trieInsert(trie, "card");
    printf("%d\n", trieSearch(trie, "cat"));    // 1
    printf("%d\n", trieSearch(trie, "cards"));  // 0
    printf("%d\n", trieSearch(trie, "car"));    // 1
    return 0;
}

上述代码中，我们创建一个新的字典树，并插入4个字符串。接下来进行多次查询，分别查询"cat"、"cards"、"car"是否存在于字典树中，结果分别是1、0、1。

至此，我们完成了字典树的基本知识及使用C语言的相关实现。