头文件
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> //（仅支持小写字母 // 字典树节点结构 typedef struct TrieNode { struct TrieNode* children[26]; // 26个小写字母 bool is_end; // 是否是单词结尾 int count; // 单词出现次数 } TrieNode; // 字典树结构 typedef struct { TrieNode* root; } Trie; // 创建新节点 TrieNode* create_node(); //1.创建字典树 Trie* trie_create(); //2.递归释放节点内存 void free_node(TrieNode* node); //4.字符转索引 (a-z -> 0-25) int char_to_index(char c); //5.索引转字符 (0-25 -> a-z) char index_to_char(int index); //6.插入单词 bool trie_insert(Trie* trie, const char* word); //7.搜索单词 bool trie_search(Trie* trie, const char* word); //8.检查前缀 bool trie_starts_with(Trie* trie, const char* prefix); //9.递归收集单词 void collect_words(TrieNode* node, char* current, int depth, char** results, int* result_count, int max_results); //10.自动补全 char** trie_autocomplete(Trie* trie, const char* prefix, int* result_count, int max_results); //11.释放自动补全结果 void free_autocomplete_results(char** results, int count); //12.删除单词 bool trie_delete(Trie* trie, const char* word); //13.获取单词频率 int trie_get_frequency(Trie* trie, const char* word); //14.打印字典树（调试用） void print_trie_helper(TrieNode* node, char* str, int level); //15.统计单词总数 int count_words_helper(TrieNode* node);
源文件
#include"字典树.h" //创建新节点 TrieNode* create_node() { TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode)); if (!node) { printf("内存分配失败！\n"); return NULL; } node->is_end = false; node->count = 0; for (int i = 0; i < 26; i++) { node->children[i] = NULL; } return node; } //1.创建字典树 Trie* trie_create() { Trie* trie = (Trie*)malloc(sizeof(Trie)); if (!trie) { printf("内存分配失败！\n"); return NULL; } trie->root = create_node(); if (!trie->root) { free(trie); return NULL; } return trie; } //2.递归释放节点内存 void free_node(TrieNode* node) { if (!node) return; for (int i = 0; i < 26; i++) { if (node->children[i]) { free_node(node->children[i]); } } free(node); } // 释放字典树内存 void trie_free(Trie* trie) { if (!trie) return; if (trie->root) { free_node(trie->root); } free(trie); } // ==================== 字符转换函数 ==================== // 字符转索引 (a-z -> 0-25) int char_to_index(char c) { if (c >= 'a' && c <= 'z') { return c - 'a'; } // 如果需要支持大写字母 if (c >= 'A' && c <= 'Z') { return c - 'A'; } // 其他字符返回-1表示无效 return -1; } // 索引转字符 (0-25 -> a-z) char index_to_char(int index) { if (index >= 0 && index < 26) { return 'a' + index; } return '?'; } // ==================== 基本操作 ==================== // 插入单词 bool trie_insert(Trie* trie, const char* word) { if (!trie || !word) return false; TrieNode* node = trie->root; for (int i = 0; word[i] != '\0'; i++) { int index = char_to_index(word[i]); if (index < 0 || index >= 26) { printf("无效字符: %c\n", word[i]); return false; } if (!node->children[index]) { node->children[index] = create_node(); if (!node->children[index]) { return false; } } node = node->children[index]; } node->is_end = true; node->count++; return true; } // 搜索单词 bool trie_search(Trie* trie, const char* word) { if (!trie || !word) return false; TrieNode* node = trie->root; for (int i = 0; word[i] != '\0'; i++) { int index = char_to_index(word[i]); if (index < 0 || index >= 26) { return false; } if (!node->children[index]) { return false; } node = node->children[index]; } return node->is_end; } // 检查前缀 bool trie_starts_with(Trie* trie, const char* prefix) { if (!trie || !prefix) return false; TrieNode* node = trie->root; for (int i = 0; prefix[i] != '\0'; i++) { int index = char_to_index(prefix[i]); if (index < 0 || index >= 26) { return false; } if (!node->children[index]) { return false; } node = node->children[index]; } return true; } // ==================== 高级操作 ==================== // 递归收集单词 void collect_words(TrieNode* node, char* current, int depth, char** results, int* result_count, int max_results) { if (!node || *result_count >= max_results) return; if (node->is_end) { current[depth] = '\0'; results[*result_count] = (char*)malloc(strlen(current) + 1); if (results[*result_count]) { strcpy(results[*result_count], current); (*result_count)++; } } for (int i = 0; i < 26 && *result_count < max_results; i++) { if (node->children[i]) { current[depth] = index_to_char(i); collect_words(node->children[i], current, depth + 1, results, result_count, max_results); } } } // 自动补全 char** trie_autocomplete(Trie* trie, const char* prefix, int* result_count, int max_results) { if (!trie || !prefix || !result_count || max_results <= 0) { return NULL; } *result_count = 0; // 分配结果数组 char** results = (char**)malloc(sizeof(char*) * max_results); if (!results) return NULL; // 定位到前缀节点 TrieNode* node = trie->root; for (int i = 0; prefix[i] != '\0'; i++) { int index = char_to_index(prefix[i]); if (index < 0 || index >= 26 || !node->children[index]) { free(results); return NULL; } node = node->children[index]; } // 准备当前字符串缓冲区 int prefix_len = strlen(prefix); char* current = (char*)malloc(prefix_len + 50); // 额外空间 if (!current) { free(results); return NULL; } strcpy(current, prefix); // 收集单词 collect_words(node, current, prefix_len, results, result_count, max_results); free(current); return results; } // 释放自动补全结果 void free_autocomplete_results(char** results, int count) { if (!results) return; for (int i = 0; i < count; i++) { if (results[i]) { free(results[i]); } } free(results); } // 删除单词 bool trie_delete(Trie* trie, const char* word) { if (!trie || !word || !trie_search(trie, word)) { return false; } return trie_delete_helper(trie->root, word, 0); } // 递归删除辅助函数 bool trie_delete_helper(TrieNode* node, const char* word, int depth) { if (!node) return false; // 到达单词末尾 if (word[depth] == '\0') { if (node->is_end) { node->is_end = false; node->count = 0; // 检查是否有子节点 for (int i = 0; i < 26; i++) { if (node->children[i]) { return false; // 有子节点，不能删除 } } return true; // 可以删除此节点 } return false; } int index = char_to_index(word[depth]); if (index < 0 || index >= 26 || !node->children[index]) { return false; } bool should_delete_child = trie_delete_helper(node->children[index], word, depth + 1); if (should_delete_child) { free(node->children[index]); node->children[index] = NULL; // 检查当前节点是否可以删除 if (!node->is_end) { for (int i = 0; i < 26; i++) { if (node->children[i]) { return false; // 有其他子节点 } } return true; // 可以删除当前节点 } } return false; } // 获取单词频率 int trie_get_frequency(Trie* trie, const char* word) { if (!trie || !word) return 0; TrieNode* node = trie->root; for (int i = 0; word[i] != '\0'; i++) { int index = char_to_index(word[i]); if (index < 0 || index >= 26 || !node->children[index]) { return 0; } node = node->children[index]; } return node->is_end ? node->count : 0; } // ==================== 工具函数 ==================== // 打印字典树（调试用） void print_trie_helper(TrieNode* node, char* str, int level) { if (node->is_end) { str[level] = '\0'; printf("%s (count: %d)\n", str, node->count); } for (int i = 0; i < 26; i++) { if (node->children[i]) { str[level] = index_to_char(i); print_trie_helper(node->children[i], str, level + 1); } } } void print_trie(Trie* trie) { if (!trie || !trie->root) { printf("字典树为空\n"); return; } char buffer[100]; printf("字典树内容:\n"); print_trie_helper(trie->root, buffer, 0); } // 统计单词总数 int count_words_helper(TrieNode* node) { if (!node) return 0; int count = node->is_end ? 1 : 0; for (int i = 0; i < 26; i++) { if (node->children[i]) { count += count_words_helper(node->children[i]); } } return count; } int trie_count_words(Trie* trie) { if (!trie || !trie->root) return 0; return count_words_helper(trie->root); } int main() { return 0; }
