C语言字符串中的前缀树（Trie）应用

前缀树（Trie）是一种数据结构，它可以高效地存储和查询字符串集合

下面是一个简单的 C 语言实现：

#include<stdio.h>
#include <stdlib.h>
#include<string.h>

typedef struct TrieNode {
    struct TrieNode* children[26]; // 26 个指向子节点的指针，对应 26 个英文字母
    int isEndOfWord; // 标记当前节点是否为一个单词的结尾
} TrieNode;

// 创建新的 Trie 节点
TrieNode* createTrieNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    memset(node->children, 0, sizeof(node->children));
    node->isEndOfWord = 0;
    return node;
}

// 插入一个单词到 Trie 中
void insert(TrieNode* root, const char* word) {
    TrieNode* node = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int index = word[i] - 'a';
        if (!node->children[index]) {
            node->children[index] = createTrieNode();
        }
        node = node->children[index];
    }
    node->isEndOfWord = 1;
}

// 在 Trie 中查找一个单词
int search(TrieNode* root, const char* word) {
    TrieNode* node = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int index = word[i] - 'a';
        if (!node->children[index]) {
            return 0;
        }
        node = node->children[index];
    }
    return node->isEndOfWord;
}

// 测试代码
int main() {
    TrieNode* root = createTrieNode();
    insert(root, "hello");
    insert(root, "world");
    printf("Search 'hello': %d\n", search(root, "hello"));
    printf("Search 'world': %d\n", search(root, "world"));
    printf("Search 'apple': %d\n", search(root, "apple"));
    return 0;
}

这个示例展示了如何使用前缀树（Trie）来存储和查询字符串。首先，我们定义了一个 TrieNode 结构体，用于表示 Trie 中的每个节点。然后，我们实现了 createTrieNode 函数来创建新的 Trie 节点。接下来，我们实现了 insert 函数来将一个单词插入到 Trie 中，以及 search 函数来在 Trie 中查找一个单词。最后，我们编写了一个简单的测试程序来演示如何使用这些函数。