Два маленьких класса для дерева строк на стандартных алгоритмах
Небольшой код на представление деревьев в C++ с помощью стандартной библиотеки алгоритмов.
Класс nestTree
выводит форму представления с вложенностью узлов, показанной строчным отступом, а экземпляр класса indentTree
, который может быть создан из nestTree
, делает это с помощью нумерации уровней вложенности узлов.
Объект класса indentTree
можно преобразовать обратно к nestTree
с помощью метода indentToNest
,
также определён оператор ==
для сравнения объектов nestTree
.
Ниже показаны консольный листинг на C++, выполненный в актуальной сборке Visual Studio 2019 и результаты вывода программы.
#include <iostream> #include <iomanip> #include <vector> #include <list> #include <string> #include <utility> class nestTree; bool operator == (const nestTree&, const nestTree&); class nestTree { public: explicit nestTree(const std::string& name) : name_(name) {} nestTree& add_child(const std::string& name) { children_.emplace_back(name); return children_.back(); } void print(std::ostream& out) const { print(out, 0); } const std::string& name() const { return name_; } const std::list<nestTree>& children() const { return children_; } bool equals(const nestTree& n) const { return name_ == n.name_ && children_ == n.children_; } private: void print (std::ostream& out, int level) const { std::string indent(level * 4, ' '); out << indent << name_ << std::endl; for (const nestTree& child : children_) child.print(out, level + 1); } std::string name_; std::list <nestTree> children_; }; bool operator == (const nestTree& a, const nestTree& b) { return a.equals(b); } class indentTree { public: explicit indentTree (const nestTree& n) { items_.emplace_back(0, n.name()); indentFromNest(n, 0); } void print (std::ostream& out) const { for (const auto& item : items_) std::cout << item.first << ' ' << item.second << std::endl; } nestTree indentToNest() const { nestTree n (items_[0].second); indentToNestProc(n, 1, 0); return n; } private: void indentFromNest (const nestTree& n, int level) { for (const nestTree& child : n.children()) { items_.emplace_back(level + 1, child.name()); indentFromNest (child, level + 1); } } size_t indentToNestProc (nestTree& n, size_t pos, int level) const { while (pos < items_.size() && items_[pos].first == level + 1) { nestTree& child = n.add_child(items_[pos].second); pos = indentToNestProc (child, pos + 1, level + 1); } return pos; } std::vector<std::pair<int, std::string>> items_; }; int main() { nestTree n ("My tree"); auto& child1 = n.add_child("Node 1"); auto& child2 = n.add_child("Node 2"); child1.add_child("Node 1-1"); child1.add_child("Node 1-2"); auto& child13 = child1.add_child("Node 1-3"); child13.add_child("Node 1-3-1"); child2.add_child("Node 2-1"); std::cout << "Nest tree (n):" << std::endl; n.print (std::cout); indentTree i(n); std::cout << "Indent from nest (i):" << std::endl; i.print(std::cout); nestTree n2(i.indentToNest()); std::cout << "Indent to nest (i->n2):" << std::endl; n2.print(std::cout); std::cout << "n==n2? " << std::boolalpha << (n==n2) << std::endl; return 0; }
Nest tree (n): My tree Node 1 Node 1-1 Node 1-2 Node 1-3 Node 1-3-1 Node 2 Node 2-1 Indent from nest (i): 0 My tree 1 Node 1 2 Node 1-1 2 Node 1-2 2 Node 1-3 3 Node 1-3-1 1 Node 2 2 Node 2-1 Indent to nest (i->n2): My tree Node 1 Node 1-1 Node 1-2 Node 1-3 Node 1-3-1 Node 2 Node 2-1 n==n2? true
18.12.2021, 11:57 [619 просмотров]