C++实现字典树数据结构 |21xrx.com

C++实现字典树数据结构

2023-07-05 13:35:51 深夜i -- --

C++ 字典树数据结构实现

字典树是一种非常重要的数据结构，它是一种树形结构，用于存储字符串数据。它的主要优势在于能够快速的查找、插入、删除以及匹配字符串。

C++是一种最流行的编程语言之一，其简洁性和高效性使其成为了实现字典树的理想选择。下面，我们将介绍C++如何实现字典树数据结构。

首先，我们需要定义节点类型。节点包括一个值和一组指针，指向其子节点。我们定义了一个类TrieNode，其包括一个isWord标志和一个指向TrieNode对象的指针数组，数组的大小为26，因为我们只考虑字母表中的小写字母。


class TrieNode {
public:
  bool isWord;
  TrieNode* children[26];
  TrieNode() : isWord(false) {
    memset(children, NULL, sizeof(TrieNode*) * 26);
  }
};

接下来，我们需要实现添加字符串的功能。添加字符串需要从根节点开始查找当前字符是否存在。如果不存在，则需要创建新的节点插入到Trie中。如果已经存在，则直接移动到下一节点。最后，将最后一个节点标记为单词的结束。


void addWord(string word, TrieNode* root) {
  TrieNode* node = root;
  for (char c : word) {
    if (!node->children[c - 'a']) {
      node->children[c - 'a'] = new TrieNode();
    }
    node = node->children[c - 'a'];
  }
  node->isWord = true;
}

接下来，我们实现查找字符串的功能。查找从根节点开始，如果当前字符存在就移动到下一节点。如果不存在，则说明该字符串不存在。如果扫描完成，并且最后一个节点被标记为单词的结束，则说明该字符串存在。


bool searchWord(string word, TrieNode* root) {
  TrieNode* node = root;
  for (char c : word) {
    if (!node->children[c - 'a'])
      return false;
    
    node = node->children[c - 'a'];
  }
  return node->isWord;
}

最后，我们需要实现删除字符串的功能。删除字符串需要从根节点开始查找字符串中的每个字符。如果找到了最后一个字符，我们将其标志为非单词节点。如果被删除的节点没有任何孩子，则需要将其从Trie中删除。


bool removeWord(string word, TrieNode* root) {
  TrieNode* node = root;
  queue<TrieNode*> q;
  for (char c : word) {
    if (!node->children[c - 'a'])
      return false;
    
    q.push(node);
    node = node->children[c - 'a'];
  }
  node->isWord = false;
  if (nodeIsLeaf(node)) {
    while (!q.empty() && q.front()->children[word.back() - 'a'] == node) {
      node = q.front();
      q.pop();
      node->children[word.back() - 'a'] = nullptr;
      if (nodeIsLeaf(node) && !node->isWord)
        delete node;
      
    }
  }
  return true;
}
bool nodeIsLeaf(TrieNode* node) {
  for (int i = 0; i < 26; i++) {
    if (node->children[i])
      return false;
    
  }
  return true;
}

总结一下，本篇文章介绍了如何使用C++实现字典树数据结构。我们定义了一个TrieNode类，包含一个isWord标志和一个指向TrieNode对象的指针数组。接着，我们实现了添加、查找和删除字符串的功能。这些算法对于处理字符串操作有很大帮助，可以在计算机程序设计的各个领域得以广泛应用。

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

下一篇: C++ STL List 字节

评论区

()

相似文章