C語言字符串中的前綴樹（Trie）應用

前綴樹（Trie）是一種數(shù)據(jù)結(jié)構(gòu)，它可以高效地存儲和查詢字符串集合

下面是一個簡單的 C 語言實現(xiàn)：

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

typedef struct TrieNode {
    struct TrieNode* children[26]; // 26 個指向子節(jié)點的指針，對應 26 個英文字母
    int isEndOfWord; // 標記當前節(jié)點是否為一個單詞的結(jié)尾
} TrieNode;

// 創(chuàng)建新的 Trie 節(jié)點
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 結(jié)構(gòu)體，用于表示 Trie 中的每個節(jié)點。然后，我們實現(xiàn)了 createTrieNode 函數(shù)來創(chuàng)建新的 Trie 節(jié)點。接下來，我們實現(xiàn)了 insert 函數(shù)來將一個單詞插入到 Trie 中，以及 search 函數(shù)來在 Trie 中查找一個單詞。最后，我們編寫了一個簡單的測試程序來演示如何使用這些函數(shù)。