字典树实现

一、字典树

字典树（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;

// 初始化字典树节点
TrieNode* createNode() {
    TrieNode *node = (TrieNode*)malloc(sizeof(TrieNode));
    node->isEndOfWord = 0;
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        node->children[i] = NULL;
    }
    return node;
}

// 在字典树中插入单词
void insertWord(TrieNode *root, char *word) {
    TrieNode *current = root;
    int len = strlen(word);

    for (int i = 0; i < len; i++) {
        int index = word[i] - 'a';
        if (current->children[index] == NULL) {
            current->children[index] = createNode();
        }
        current = current->children[index];
    }

    current->isEndOfWord = 1;
}

//打印字符串
void printSubstring(const char *str, int start, int length) {  
    for (int i = start; i < start + length && str[i] != '\0'; i++) {  
        putchar(str[i]);  
    } 
    putchar('\n'); 
}  

// 在字符串中查找字典树中的单词
void searchWords(TrieNode *root, char *text) {
    int len = strlen(text);
    TrieNode *current = root;
    int wordLen = 0;

    for (int i = 0; i < len; i++) {
        int index = text[i] - 'a';
        if (current->children[index]) {
            current = current->children[index];
            ++wordLen;
            if (current->isEndOfWord) {
                printf("Word found starting at position: %d, len: %d word is ", i - wordLen + 1, wordLen);
                printSubstring(text, i - wordLen + 1, wordLen); 
            }
        } else {
            current = root;
            wordLen = 0;

        }
    }
}

int main() {
    TrieNode *root = createNode();
    char words[][10] = {"insert", "delete", "update", "select", "create", "drop"};
    int wordsCount = sizeof(words)/sizeof(words[0]);
    char text[] = "deletedeinsertlete";

    // 构建字典树
    for (int i = 0; i < wordsCount; i++) {
        insertWord(root, words[i]);
    }

    // 在文本中查找单词
    searchWords(root, text);

    return 0;
}
//编译 gcc -o tire_tree tire_tree.c

运行结果：