如何在 C++ 中使用 map 查找前缀 |21xrx.com

如何在 C++ 中使用 map 查找前缀

2023-07-14 17:57:38 深夜i -- --

C++ map 前缀查找

C++ 是一门非常强大的编程语言，拥有着很多实用的数据结构和算法。其中，map 是一种十分常用的数据结构，可以用于快速查询和插入键值对。

在 C++ 中，可以使用 map 来查找前缀。为了方便操作，可以通过自定义一个字符串树节点来实现。该节点包含了一个 map，用来存储子节点，以及一个 bool 类型的变量，用来表示该节点是否为一个单词的结束点。

接下来，我们可以通过递归遍历字符串，一层一层往下查找对应的节点，直到找到目标前缀为止。在此基础上，我们可以再次递归遍历子节点，找到所有以该前缀开头的单词。

以下是实现过程的详细步骤：

1. 定义树节点

首先，我们需要自定义一个树节点，在其中包含字符串的某个字符、子节点 map 和 bool 类型变量等信息。代码如下：

struct TrieNode {

char ch;

map children;

bool is_end;

};

2. 插入单词

接下来，我们需要实现插入单词的函数，以及查找前缀的函数。这里先实现插入单词的函数，代码如下：

void insert_word(TrieNode* root, string& word) {

TrieNode* curr = root;

for (char c : word) {

if (curr->children.find(c) == curr->children.end()) {

curr->children[c] = new TrieNode{ c, {}, false };

}

curr = curr->children[c];

}

curr->is_end = true;

}

该函数首先定义一个 TrieNode 指针，指向根节点。然后遍历该单词的每一个字符，如果当前节点的子节点 map 中没有该字符，则在 map 中新增一个节点，否则直接访问该字符对应的节点。最后，将当前节点标记为单词结束。

3. 查找前缀

接下来，我们需要实现查询前缀的函数。这个函数需要先遍历整个前缀，找到对应的最后一个节点。然后，从该节点递归遍历 map，找到所有以该前缀开头的单词。

代码如下：

void find_prefix(TrieNode* root, string& prefix, vector & results) {

TrieNode* curr = root;

for (char c : prefix) {

if (curr->children.find(c) == curr->children.end())

return;

curr = curr->children[c];

}

find_words(curr, prefix, results);

}

这个函数首先定义一个 TrieNode 指针，指向根节点。然后遍历前缀的每一个字符，如果当前节点的子节点 map 中没有该字符，则直接返回，否则继续遍历该前缀。最后，我们定义一个递归函数 find_words，用来遍历所有以该前缀开头的单词。

代码如下：

void find_words(TrieNode* node, string& prefix, vector & results) {

if (node->is_end) {

results.push_back(prefix);

}

for (auto child : node->children) {

prefix.push_back(child.first);

find_words(child.second, prefix, results);

prefix.pop_back();

}

该函数通过判断当前节点是否为单词的结尾，来决定是否将该单词加入结果列表。然后递归遍历 map，将所有以该前缀开头的单词加入结果列表中。

4. 小结

使用 map 查找前缀是一项非常常用的操作，在 C++ 中也可以很方便地实现。通过定义自定义节点以及递归遍历，我们可以轻松地查找所有以某个前缀开头的单词。相信大家掌握了这种方法，一定能够更好地解决实际问题。

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

下一篇: C++实现二叉树数据结构及其创建方法

评论区

()

相似文章