我要提前道歉,因为我不知道如何问这个问题,否则我的标题会更好。
我正在尝试实现 UPGMA Algorithm from Wikipedia 。假设我有一个由整数组成的 vector 。
std::vector<std::vector<int>> test = { {0},{1},{2},{3},{4},{5}}
其中整数表示我的程序中的特定字符串。现在,假设我有特定的输入告诉我合并 test[0]
和test[3]
一旦它们合并在一起,我们将合并的 vector 推回到末尾,然后删除 test[0]
和test[3]
看起来像这样:
test = { {1}, {2}, {4}, {5}, {0,3} }
这可以通过以下代码轻松实现:
int x = 0;
int y = 3;
merge = {test[x][0],test[y][0]}; // merge is a std::vector<int>
test.push_back(merge);
test.erase(test.begin() + x)
test.erase(test.begin() + y - 1); // -1 since the first erase shifts everything over
当我想合并 test[1]
时出现问题和test[4]
。期望的结果看起来像这样:
test = { {1}, {4}, {5}, {2,{0,3} };
这就是我遇到问题的地方,因为我现在似乎引入了 std::vector<std:vector<int>>
进入我测试的位置3。并使用 merge = {test[x][0],test[y][0]}
将失败。随着时间的推移,这种情况会变得更糟。因为我可能有可能看起来像这样的东西:
test = { {1}, {{4,5},{2,{0,3}}} }
我想我很快意识到我的数据结构是错误的,但我完全不知道我需要使用什么数据结构。我可以使用什么样的数据结构来轻松实现这一点?
我再次为这个糟糕的问题道歉。
最佳答案
您正在构建一棵二叉树。每个子节点都是一个int
或一个子树。这在任何东西的 vector
中都没有有用的建模。
#include <vector>
#include <variant>
#include <memory>
#include <utility>
using Node = std::variant<std::shared_ptr<class Tree>, int>;
struct Tree {
Tree(Node left, Node right) : left(left), right(right) {}
Node left;
Node right;
};
std::pair<std::vector<Node>::iterator, std::vector<Node>::iterator> decide_merge(const std::vector<Node> & v)
{
// Some process to choose elements
return { v.begin(), v.begin() + 1 };
}
int main()
{
std::vector<Node> nodes = { {0}, {1}, {2}, {3}, {4}, {5} };
while (nodes.size() > 1)
{
auto [left, right] = decide_merge(nodes);
auto tree = std::make_shared<Tree>(*left, *right);
nodes.erase(left);
nodes.erase(right);
nodes.push_back(tree);
}
}
关于c++ - 我应该使用什么样的数据结构来实现 UPGMA?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50405621/