древовидная структура данных со списком в c ++ - PullRequest
Новая
       11

древовидная структура данных со списком в c ++

0 голосов
/ 04 июля 2018

Я реализовал древовидную структуру в c ++, ссылаясь на чужие коды. Код ниже, который я сделал, был обязательно скомпилирован и, кажется, работает хорошо. Но я подозреваю, что есть лучшие способы. Например, безопасен ли этот код в случае утечки памяти? Есть ли более простой и эффективный в вычислительном отношении способ?

В частности, я сомневаюсь в необходимости "std :: list lst_nodes". Функция expand_node в классе Tree присоединяет новый узел к родительскому узлу, значение которого ближе всего к значению нового узла. Этот процесс требует итерации по всем существующим узлам для доступа к их значениям. Для этой итерации я определил переменную-член с именем "std :: list lst_nodes" в классе Tree. И я подозреваю, что может существовать изящный способ сделать то же самое без определения lst_nodes. 

#include<random>
#include<iostream>
#include<list>
using namespace std;

class Node{
  public:/*functions*/
    Node(const double& val_, Node* parent_=nullptr)
      :val(val_), parent(parent_)
    {
      if(parent){
        parent->children.push_back(this);
      }
    }
  public:/*variables*/
    Node* parent;
    std::list<Node*> children;
    double val;
};

class Tree{
  public:/*function*/
    Tree(double x_init);
    void extend_node();

  public:/*variables*/
    list<Node*> lst_nodes;
    double x_init;
};

Tree::Tree(double x_init_)
  :x_init(x_init_)
{
  Node* n=new Node(x_init);
  lst_nodes.push_back(n);
}

void Tree::extend_node(){
  double val_new = rand();
  auto it=lst_nodes.begin();
  double minval = abs((**it).val-val_new);
  Node* node_parent;
  for(;it!=lst_nodes.end(); it++){
    if(minval>abs((**it).val-val_new)){
      minval = abs((**it).val-val_new);
      node_parent = *it;
    }
  }
  Node* n_new = new Node(val_new, node_parent);
  node_parent->children.push_back(n_new);
  lst_nodes.push_back(n_new);
}

int main(){
  Tree t(0);
  for(int i=0; i<100; i++){
    t.extend_node();
  }
}

Большое спасибо.

1 Ответ

0 голосов
/ 04 июля 2018

В современном C ++ вы можете использовать unique_pointer<T> вместо необработанных T* указателей, когда объект, на который указывает указатель, принадлежит объекту с указателем. Таким образом, вам не нужно явно delete объект, это будет сделано в деструкторе unique_ptr.

В дереве (то есть связанном графе без циклов в нем) четко определено владение: каждый узел имеет своих дочерних элементов, поэтому вы можете использовать list<unique_ptr<Node>> для Node::children.

...