html5 网站开发软件,免费设计图网站,数据系统网站建设必要性,网站建设试题 jsp字典树的概念
字典树#xff08;Trie#xff09;#xff0c;又称为前缀树或单词查找树#xff0c;是一种树形数据结构#xff0c;主要用于存储具有相同前缀的字符串集合。它特别适合用于词典中的单词查找、自动补全、拼写检查等应用。 字典树算法的核心思想就是每层存入…字典树的概念
字典树Trie又称为前缀树或单词查找树是一种树形数据结构主要用于存储具有相同前缀的字符串集合。它特别适合用于词典中的单词查找、自动补全、拼写检查等应用。 字典树算法的核心思想就是每层存入单词的字符顺着树节点依次往下排布用bool judge变量来标记此字符处是否构成单词某个单词的结尾字符还可以用一个int counter变量来累计某个前缀出现的次数。
字典树的特点
根节点不包含字符通常为空。每个节点表示一个字符串中的字符。从根节点到某一节点的路径表示一个字符串。每个节点的所有子节点包含的字符都不相同。
字典树的操作
插入操作将一个字符串逐字符插入字典树。对于每个字符从根节点开始检查是否存在对应的子节点。如果不存在则创建一个新的节点。查找操作检查一个字符串是否在字典树中。类似于插入操作逐字符检查是否存在对应的节点。删除操作从字典树中删除一个字符串。需要小心处理节点的删除以确保不影响其他字符串的存储。
字典树的优点
快速查找查找的时间复杂度为O(m)其中m为待查找字符串的长度。节省空间通过共享相同前缀的方式节省了存储空间。
字典树的缺点
空间消耗大在最坏的情况下字典树可能需要大量的节点和指针。实现复杂性相对于哈希表字典树的实现相对复杂。
字典树在很多应用中表现出色尤其是在需要处理大量字符串并进行快速查找的场景中。
C代码实现字典树
在C中实现字典树Trie通常包括以下几个步骤
定义 TrieNode 类每个节点包含若干子节点和一些必要的信息比如标记是否是某个单词的结尾。定义 Trie 类主要提供插入、查找和删除等功能。
下面是一个简单的字典树Trie的C实现
1. 定义 TrieNode 类
#include iostream
#include unordered_mapusing namespace std;// TrieNode 节点结构
class TrieNode {
public:unordered_mapchar, TrieNode* children; // 子节点映射bool isEndOfWord; // 是否是一个单词的结尾TrieNode() : isEndOfWord(false) {}
};2. 定义 Trie 类
class Trie {
private:TrieNode* root; // 根节点public:// 构造函数Trie() {root new TrieNode();}// 插入一个单词到字典树void insert(const string word) {currentNode root;for (char c : word) {if (currentNode-children.find(c) currentNode-children.end()) {currentNode-children[c] new TrieNode();}currentNode currentNode-children[c];}currentNode-isEndOfWord true; // 标记单词的结尾}// 查找一个单词是否存在于字典树中bool search(const string word) {TrieNode* currentNode root;for (char c : word) {if (currentNode-children.find(c) currentNode-children.end()) {return false; // 如果有任何字符找不到返回 false}currentNode currentNode-children[c];}return currentNode-isEndOfWord; // 返回当前节点是否是单词的结尾}// 查找是否有任何单词以给定的前缀开始bool startsWith(const string prefix) {TrieNode* currentNode root;for (char c : prefix) {if (currentNode-children.find(c) currentNode-children.end()) {return false; // 如果前缀中的某个字符找不到返回 false}currentNode currentNode-children[c];}return true; // 如果前缀存在返回 true}
};3. 使用字典树
int main() {Trie trie;// 插入单词trie.insert(apple);trie.insert(app);trie.insert(banana);// 查找单词cout search(\apple\): trie.search(apple) endl; // 输出 1 (true)cout search(\app\): trie.search(app) endl; // 输出 1 (true)cout search(\banana\): trie.search(banana) endl; // 输出 1 (true)cout search(\bat\): trie.search(bat) endl; // 输出 0 (false)// 查找前缀cout startsWith(\app\): trie.startsWith(app) endl; // 输出 1 (true)cout startsWith(\ban\): trie.startsWith(ban) endl; // 输出 1 (true)cout startsWith(\bana\): trie.startsWith(bana) endl; // 输出 1 (true)cout startsWith(\cat\): trie.startsWith(cat) endl; // 输出 0 (false)return 0;
}4. 代码解析 TrieNode 类 使用 unordered_map 存储子节点映射unordered_map 是 C 中一个哈希表实现用来存储每个字符对应的子节点。isEndOfWord 用来标记当前节点是否是某个单词的结尾。 Trie 类 insert通过遍历单词的每个字符将它们插入到字典树中。如果字符不存在就创建新的节点。最后标记该节点为单词的结尾。search查找一个单词是否在字典树中。如果路径上的任何字符不存在直接返回 false。最终检查最后一个节点是否是单词的结尾。startsWith查找是否有任何单词以给定前缀开始。只要能够找到前缀的所有字符就返回 true。
5. 输出示例
search(apple): 1
search(app): 1
search(banana): 1
search(bat): 0
startsWith(app): 1
startsWith(ban): 1
startsWith(bana): 1
startsWith(cat): 06. 优化
字典树的空间复杂度较高特别是当字典中的单词较多时。为了节省空间可以使用更紧凑的结构如 压缩字典树Radix Tree或者使用 字符数组 替代 unordered_map减少指针的开销。
总结
这个 C 实现展示了一个基本的字典树Trie数据结构支持插入、查找和前缀查找等操作。它适用于需要高效查找大量字符串的场景比如自动补全、词典查询等。
