2

Добрый вечер. В задании необходимо было создать лес бинарных деревьев по введённым данным, единичное дерево было реализовано через класс:

class btree
{
public:
  btree();
  ~btree();
  void print();
  void insert(int key, std::string data);
  void destroy_tree();
private:
  void print(node *leaf);
  void destroy_tree(node *leaf);
  void insert(int key, std::string data, node *leaf);

  node *root;
};

Где node представляет:

struct node
{
    int key_value; //глубина узла
    std::string data; //значение узла
    node* left; //левая ветка
    node* right; //правая ветка
};

Дерево образуется так: ( - уровень ниже, ) - уровень выше, ',' - узел того же уровня, пример строки в коде:

int main(void)
{
    std::string str;
    std::string buff;

    btree tree;
    std::vector<btree> woods;

    unint i=0;
    unint n=0;

    str="a(d(e)c(n))";

    while(str[i])
    {
        if(str[i]!='(' && str[i]!=')' && str[i]!=',')
            buff+=str[i];

        if(str[i]==',') //Встречаем ,
        {
            if(n==0) //Если уровень 0, то кладём дерево в массив и чистим нынешнее
                {
                    woods.push_back(tree);
                    tree.destroy_tree();
                }
            else //Отлично от нуля - разные узлы
                {
                    tree.insert(n, buff);
                    buff.clear();
                }
        }

        switch (str[i])
        {
        case '(': //Встречаем ( - увеличиваем уровень на 1
            tree.insert(n, buff); // кладём буферную строку
            buff.clear(); //очищаем её
            n++;
            break;
        case ')': //Встречаем ) - уменьшаем уровень на 1
            tree.insert(n, buff); // кладём буферную строку
            buff.clear(); //очищаем её
            n--;
            break;
        }
        i++;
    }
    tree.print();
}

Единичное дерево код прекрасно обрабатывает и все функции работают корректно: insert - добавить, print - вывести дерево, destroy_tree - уничтожить дерево. Если попытаться добавить дополнительное дерево (такого же типа строка, через запятую при уровне равном 0) ты выскакивает следующая ошибка:

0 [main] BinWTreeEcl 5876 cygwin_exception::open_stackdumpfile: Dumping stack trace to BinWTreeEcl.exe.stackdump

BinWTree - название исходника. Помогите понять в чём заключается ошибка, пробовал аналогично через отдельный список - та же ситуация. Какие варианты ещё есть?

3
  • 1
    А вы можете определить в каком месте исключение происходит, в какой строчке кода? Или можете попробовать под отладчиком пройтись и посмотреть на какой строке оно умирает. Наверняка неверная работа с памятью, например освобождён указатель а вы его разыменовываете или может пытаетесь удалить дважды один указатель. Если нет возможности отлаживать, то можете определить строку просто выводом какого-то сообщения во всех ключевых местах.
    – Arty
    23 окт 2017 в 18:32
  • @ArtyOneSoul крашится в самом конце, после выполнения всех команд, выводит: No source available for ntdll!ZwWriteFile() at 0x76f0bdba
    – Totem
    23 окт 2017 в 18:52
  • @ArtyOneSoul и ещё No source available for "ntdll!ZwWaitForSingleObject() at 0x76f0bd7a"
    – Totem
    23 окт 2017 в 18:55

1 ответ 1

1

Не реализован конструктор копирования/перемещения (и операторы присваивания тоже). Отсюда получаем:

woods.push_back(tree);//Добавили в вектор (скопировался root)
tree.destroy_tree();//Следом уничтожили и в векторе теперь висячий указатель.
10
  • Не совсем понял что вы имеете ввиду, можете объяснить?
    – Totem
    23 окт 2017 в 19:03
  • 1
    Вы tree добавляете в вектор, а значит он копируется туда. В силу того, что у Вас нет реализованного конструктора копирования, то компилятор сгенерирует сам этот конструктор. Он будет просто копировать указатель root из исходного типа btree в целевой. То есть в векторе получается копия, ссылающаяся на те же данные, что и tree. Следом вы удаляете данные tree, а значит копия в векторе теперь будет содержать btree в котором указатель root, указывает на удаленные данные. 23 окт 2017 в 19:07
  • 1
    @ProstoNekitos Предлагаю вместо того чтобы делать глубокое копирование всех данных, вместо этого просто хранить в векторе умные указатели на деревья, т.е. vector<shared_ptr<btree>> тогда и не нужно копирования сложного делать глубокого, достаточно просто на каждое дерево выделять новый инстанс в динамической памяти.
    – Arty
    23 окт 2017 в 19:16
  • 1
    @ProstoNekitos Ошибка изза того что конструктор принимающий указатель у shared_ptr объявлен как explicit, значит правильно писать нужно woods.push_back(shared_ptr<btree>(new btree));, кстати надеюсь вы не забыли сделать #include <memory> для shared_ptr. Также shared_ptr если вы не знаете позволяет безопасно сколько угодно копий делать т.е. это значит что вы можете для удобства сделать после добавления в вектор shared_ptr<btree> tree = woods.back();, т.е. чтобы у вас как и раньше была tree переменная дополнительная для удобства указывающая на текущее дерево.
    – Arty
    24 окт 2017 в 8:39
  • 1
    @Arty OneSoul лучше с std::make_shared 24 окт 2017 в 8:47

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.