Глупый конструктор шаблонного класса и обхода - PullRequest
Новая
       0

Глупый конструктор шаблонного класса и обхода

0 голосов
/ 31 октября 2019

У меня есть класс Node и класс Tree, а в моем классе Tree (который является m-арным деревом) у меня есть метод, который выполняет обход inorder в моем дереве.
Так что проблема в том, что когда явызов этого метода, я могу напечатать первую ветвь моего дерева, и после этого я получаю ошибку сегментации. Я знаю (с отладкой), что ошибка может происходить из-за того, что в конструкторе моего класса Node, или, возможно, я не написал очень хороший метод обхода.
Вот мой код.

Node.hpp 

#ifndef NODE_HPP
#define NODE_HPP

#include <iostream>
#include <cstddef> 

template <typename V, unsigned short N>
class Node {
private:
  V _data;
  Node<V, N>* _children[N];

  template <typename U, unsigned short M>
  friend std::ostream& operator<< (std::ostream&, const Node<U, M>&);

public:
  Node();
  Node(V);
  Node(V, unsigned short);
  Node(const Node&); // copy constructor
  Node& operator= (Node&); // assignement by copy constructor
  Node (Node&&); // transfer constructor
  Node& operator= (Node&&); // assignement by transfer constructor
  ~Node() = default;
  V getData() const;
  Node<V, N>* getChildren();
  void setChild(unsigned short, Node<V, N>*);
  void delChild(unsigned short);
  Node<V, N>* getChild(unsigned short); 
};

template <typename V, unsigned short N>
Node<V, N>::Node()
  : _data(0),  _children(nullptr) {}

template <typename V, unsigned short N>
Node<V, N>::Node(V data)
  : _data(data) {
  for (unsigned short i = 0; i < N; i++) 
    _children[i] = NULL;
}

template <typename V, unsigned short N>
Node<V, N>::Node(V data, unsigned short size)
  : _data(data) {
  for (unsigned short i = 0; i < size; i++) 
    _children[i] = NULL;
}

template <typename V, unsigned short N>
Node<V, N>::Node (const Node& other)
  : _data(other._data) {
  // _children = other._children;
  for (unsigned short i = 0; i < N; i++) 
    _children[i] = other._children[i];
}

template <typename V, unsigned short N>
Node<V, N>& Node<V, N>::operator= (Node& n){
  if (&n != this) {
    delete _children;
    _data = n._data; _children = n._children;
    n._data = 0; n._children = nullptr;
  }
  return *this;
}

template <typename V, unsigned short N>
Node<V, N>::Node (Node&& n){
  _data = n._data; _children = n._children;
  n._data = 0; n._children = nullptr;
}

template <typename V, unsigned short N>
Node<V, N>& Node<V, N>::operator= (Node&& n){
  if (&n != this) {
    delete _children;
    _data = n._data; _children = n._children;
    n._data = 0; n._children = nullptr;
  }
  return *this; 
}

template <typename V, unsigned short N> // TO DO : move this to class scope ???
V Node<V, N>::getData() const {return _data;}

template <typename V, unsigned short N>
Node<V, N>* Node<V, N>::getChildren() {return *_children;}

template <typename V, unsigned short N>
void Node<V, N>::setChild(unsigned short index, Node<V, N>* childNode){
  this->_children[index] = childNode;
}

template <typename V, unsigned short N>
void Node<V, N>::delChild(unsigned short index){
  this->_children[index] = NULL;
}

template <typename V, unsigned short N>
Node<V, N>* Node<V, N>::getChild(unsigned short index){
  return &this->_children[index];
}

template <typename V, unsigned short N>
std::ostream& operator<< (std::ostream& o, const Node<V, N>& node){
  if (node._data) o << node._data ;
  return o;
}

#endif

tree.hpp 


#ifndef TREE_HPP
#define TREE_HPP

#include <iostream>
#include <cstddef> 
#include "node.hpp"

template <typename V, unsigned short N>
class Tree {
private:
  Node<V, N>* _info;
public:
  Tree();
  Tree(Node<V, N>*);
  Tree(V, unsigned short);
  Tree(const Tree&) = delete;  // copy constructor
  Tree& operator= (const Tree&) = delete; // assignement by copy constructor
  Tree (Tree&&); // transfer constructor
  Tree& operator= (Tree&&); // assignement by transfer constructor
  ~Tree() {delete _info;}
  Node<V, N>* info();
  bool vide();
  bool ins(unsigned short, Node<V, N>*);
  bool del(unsigned short);
  Node<V, N>* fils(unsigned short);
  void inorderTraverse(Node<V, N>*);
};

template <typename V, unsigned short N>
Tree<V, N>::Tree() 
  : _info(nullptr) {}

template <typename V, unsigned short N>
Tree<V, N>::Tree(Node<V, N>* newNode)
  : _info(newNode) {}

template <typename V, unsigned short N>
Tree<V, N>::Tree(V data, unsigned short size) {
  Node<V, N>* node = new Node<V, N>(data, size);
  _info = node;
}

template <typename V, unsigned short N>
Tree<V, N>::Tree(Tree&& t) {
  _info = t._info;
  t._info = nullptr;
}

template <typename V, unsigned short N>
Tree<V, N>& Tree<V, N>::operator= (Tree&& t) {
  if (&t != this) {delete _info; _info = t._info; t._info = nullptr;}
  return *this;
}

template <typename V, unsigned short N>
Node<V, N>* Tree<V, N>::info() { return _info;}

template <typename V, unsigned short N>
bool Tree<V, N>::vide() {
  return true ? _info : false;
}

template <typename V, unsigned short N>
bool Tree<V, N>::ins(unsigned short index, Node<V, N>* node){
  if (_info) {
    _info->setChild(index, node);
    return true;
  }
  return false;
}

template <typename V, unsigned short N>
bool Tree<V, N>::del(unsigned short index){
  if (_info) {
    _info->delChild(index);
    return true;
  }
  return false;
}

template <typename V, unsigned short N>
Node<V, N>* Tree<V, N>::fils(unsigned short index){
  return &_info->getChild(index);
}

template <typename V, unsigned short N>
void Tree<V, N>::inorderTraverse(Node<V, N>* node){
  if (node->getData()){
    std::cout << *node << "\n";
    for (unsigned short i = 0; i < N; i++) {
      if (node->getChildren()[i].getData()){
        inorderTraverse(&node->getChildren()[i]);
      }
    }
  }
}

#endif

main.cpp 

#include <iostream>
#include <cstddef>
#include "tree.hpp"
#include "node.hpp"
#define SIZE 5
int main() {
  Node<char, SIZE> n1('A',SIZE);
  Node<char, SIZE> n1_1('B',SIZE);
  Node<char, SIZE> n1_2('C',SIZE);
  Node<char, SIZE> n1_3('D',SIZE);
  Node<char, SIZE> n1_1_1('E',SIZE);
  Node<char, SIZE> n1_1_2('F',SIZE);
  Node<char, SIZE> n1_1_1_1('G',SIZE);
  Node<char, SIZE> n1_2_1('H',SIZE);
  Node<char, SIZE> n1_2_1_1('I',SIZE);
  Node<char, SIZE> n1_3_1('J',SIZE);
  n1.setChild(0,&n1_1);
  n1.setChild(1,&n1_2);
  n1.setChild(2,&n1_3);
  n1_1.setChild(0,&n1_1_1);
  n1_1.setChild(1,&n1_1_2);
  n1_1_1.setChild(0,&n1_1_1_1);
  n1_2.setChild(0,&n1_2_1);
  n1_2_1.setChild(0,&n1_2_1_1);
  n1_3.setChild(0,&n1_3_1);
  Tree<char, SIZE> t(&n1);
  t.inorderTraverse(t.info());
  return 0;
}

Заранее благодарю за помощь

1 Ответ

0 голосов
/ 31 октября 2019

Node::getChildren() возвращает *_children, который является первым указателем в массиве _children. Затем вы вызываете node->getChildren()[i], который добавляет i к этому указателю. Это работает для первого узла, так как все ваши узлы размещены рядом друг с другом в стеке, и он возвращает правильный узел. Это неопределенное поведение, и в реальном коде с узлами, выделенными из кучи, это может быстро привести к сбою. getChildren должно быть: 

template <typename V, unsigned short N>
Node<V, N>** Node<V, N>::getChildren() { return _children; }

Тогда ваш код вызова будет: 

if (node->getChildren()[i]->getData()) {
   inorderTraverse(node->getChildren()[i]);
}

Затем мы вернемся к первоначальной причине вашего сбоя из-за разыменования нулевого указателя. Простое исправление заключается в том, чтобы просто проверить, что дочерний элемент не равен нулю: 

auto children = node->getChildren();
if (children[i] && children[i]->getData()) {
   inorderTraverse(children[i]);
}

Ваш код теперь будет аварийно завершать работу при выходе из-за того, что деструктор Tree удаляет узел, который выделен в стеке: 

~Tree() { delete _info; }

Если вы хотите использовать delete, все ваши узлы должны быть созданы с new, а не стеком, выделенным в main. Еще лучше использовать std::unique_ptr или std::shared_ptr и избегать delete полностью.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...