C语言前缀树实战指南（Trie树实现与字符串高效查找）

前缀树的核心特点

• 相同前缀的字符串共享路径，节省空间
• 插入和查找的时间复杂度为 O(m)，其中 m 是字符串长度
• 天然支持前缀匹配，非常适合实现搜索建议

用C语言实现前缀树

下面我们用C语言来实现一个简单的前缀树。我们将支持插入单词、查找单词、以及查找以某前缀开头的所有单词。

1. 定义Trie节点结构

#include <stdio.h>#include <stdlib.h>#include <string.h>#define ALPHABET_SIZE 26  // 假设只处理小写英文字母typedef struct TrieNode {    struct TrieNode* children[ALPHABET_SIZE];    int isEndOfWord;  // 标记是否为单词结尾} TrieNode;

2. 创建新节点

TrieNode* createNode() {    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));    if (!node) return NULL;        node->isEndOfWord = 0;    for (int i = 0; i < ALPHABET_SIZE; i++) {        node->children[i] = NULL;    }    return node;}

3. 插入单词

void insert(TrieNode* root, const char* word) {    TrieNode* current = root;        for (int i = 0; word[i] != '\0'; i++) {        int index = word[i] - 'a';        if (index < 0 || index >= ALPHABET_SIZE) continue; // 忽略非法字符                if (current->children[index] == NULL) {            current->children[index] = createNode();        }        current = current->children[index];    }    current->isEndOfWord = 1; // 标记单词结束}

4. 查找单词

int search(TrieNode* root, const char* word) {    TrieNode* current = root;        for (int i = 0; word[i] != '\0'; i++) {        int index = word[i] - 'a';        if (index < 0 || index >= ALPHABET_SIZE ||             current->children[index] == NULL) {            return 0; // 单词不存在        }        current = current->children[index];    }    return current->isEndOfWord; // 必须是完整单词}

5. 查找前缀

int startsWith(TrieNode* root, const char* prefix) {    TrieNode* current = root;        for (int i = 0; prefix[i] != '\0'; i++) {        int index = prefix[i] - 'a';        if (index < 0 || index >= ALPHABET_SIZE ||             current->children[index] == NULL) {            return 0; // 前缀不存在        }        current = current->children[index];    }    return 1; // 前缀存在}

6. 主函数测试

int main() {    TrieNode* root = createNode();        // 插入单词    insert(root, "apple");    insert(root, "app");    insert(root, "application");        // 测试查找    printf("search('app'): %s\n", search(root, "app") ? "true" : "false");    printf("search('appl'): %s\n", search(root, "appl") ? "true" : "false");        // 测试前缀匹配    printf("startsWith('app'): %s\n", startsWith(root, "app") ? "true" : "false");    printf("startsWith('ban'): %s\n", startsWith(root, "ban") ? "true" : "false");        return 0;}

应用场景与优势

通过上面的代码，你已经掌握了前缀匹配算法的基本实现。前缀树在实际开发中有广泛用途：

• 搜索引擎自动补全：用户输入“app”，系统可快速返回“apple”、“app”等建议
• IP路由查找：路由器使用类似结构快速匹配最长前缀
• 拼写检查器：快速判断单词是否在字典中

总结

本文详细介绍了C语言前缀树的原理与实现方法。通过构建Trie树，我们可以高效地完成字符串的插入、查找和前缀匹配操作。虽然本文示例仅处理小写字母，但你可以轻松扩展以支持大小写、数字甚至Unicode字符。

掌握这一Trie树实现技巧，不仅能提升你的C语言编程能力，还能为解决实际工程问题打下坚实基础。赶快动手试试吧！