C++实现字典树：原理和应用 |21xrx.com

C++实现字典树：原理和应用

2023-06-28 10:23:00 深夜i -- --

C++ 字典树原理应用

字典树（Trie Tree），也成为单词查找树或键树，是一类特殊的多叉树数据结构，用于实现快速中定查找与统计大量字符串的数据结构。字典树是一种树型数据结构，通常在统计和排序大量字符串（但不仅限于字符串）时，效率优于其他数据结构。

字典树主要应用于字符串匹配、统计前缀词频以及字符串排序。它的核心是将字符串中的每个字符作为树节点，每个单词构成的路径上标记相应的节点，并以特殊的叶子节点表示单词结束。这样通过遍历树的路径，可以输出所有匹配查询条件的单词，同时统计每个单词出现的次数。

使用C++实现字典树非常简单。先定义字典树节点的数据结构，包含一个字符类型和指向其他子节点的指针数组。然后定义字典树类，包含建立字典树的函数（Insert），匹配单词的查找函数（Search）、统计单词前缀词频的函数（PrefixCount）、输出所有单词的函数（Print）等。

下面给出一个简单的C++实现代码：


const int MAX_N = 26;
struct TrieNode {
  char val;
  int count;
  TrieNode* child[MAX_N];
  TrieNode(char v) : val(v), count(0) {memset(child, NULL, sizeof(child));}
};
class TrieTree {
private:
  TrieNode* root;
public:
  TrieTree() {root = new TrieNode('*');}
  void Insert(const char* word) {
    TrieNode* cur = root;
    while (*word) {
      int idx = *word - 'a';
      if (cur->child[idx] == NULL)
        cur->child[idx] = new TrieNode(*word);
      cur = cur->child[idx];
      word++;
    }
    cur->count++;
  }
  bool Search(const char* word) {
    TrieNode* cur = root;
    while (*word) {
      int idx = *word - 'a';
      if (cur->child[idx] == NULL)
        return false;
      cur = cur->child[idx];
      word++;
    }
    return (cur != NULL && cur->count > 0);
  }
  int PrefixCount(const char* prefix) {
    TrieNode* cur = root;
    while (*prefix) {
      int idx = *prefix - 'a';
      if (cur->child[idx] == NULL)
        return 0;
      cur = cur->child[idx];
      prefix++;
    }
    return (cur != NULL ? cur->count : 0);
  }
  void PrintWords(TrieNode* node, string prefix) {
    if (node == NULL)
      return;
    if (node->count > 0)
      cout << prefix << " : " << node->count << endl;
    for (int i = 0; i < MAX_N; i++) {
      if (node->child[i] != NULL)
        PrintWords(node->child[i], prefix + node->child[i]->val);
    }
  }
  void Print() {
    PrintWords(root, "");
  }
};

字典树因其高效的查询与统计能力在许多场景中得到了广泛的应用。比如，搜索引擎中的关键词匹配，输入法中的词库，DNA序列在生物信息学中的序列比对，以及字符串排序等场景中都使用到了字典树。通过理解字典树的基本原理并掌握C++的实现，我们可以更加灵活地应用该数据结构来解决实际的问题。

上一篇: idea打包java可执行jar包

下一篇: C++中交换所有其它值

评论区

()

相似文章