Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.57/21: Рейтинг темы: голосов - 21, средняя оценка - 4.57
4 / 3 / 0
Регистрация: 22.08.2014
Сообщений: 80

Дерево с узлами трёх разных типов

24.07.2017, 20:14. Показов 4009. Ответов 21
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Требуется реализовать произвольное дерево, где каждый узел может быть строкой, целым или вещественным числом, и иметь любое количество детей, также одного из этих трёх типов (дети могут иметь разный тип). При разработке класса для узла у меня возникли две идеи, как это сделать:
1)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename T>
class tree_node
{
    using value_type = typename std::enable_if
        <
            std::is_same<std::string, T>::value ||
            std::is_same<int, T>::value ||
            std::is_same<float, T>::value, T
        >::type;
    value_type data;
    std::vector<??????> children;// Что за тип здесь должен быть?
public:
...
2)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct node_data {};
struct str_node: public node_data
{
    std::string data;
    str_node(std::string &str): data(str) {};
};
struct int_node: public node_data
{
    int data;
    int_node(int n): data(n) {};
};
struct float_node: public node_data
{
    float data;
    float_node(float f): data(f) {};
};
 
class tree_node
{
    std::shared_ptr<node_data> val;
    std::vector<std::shared_ptr<node_data>> children;
public:
....
//Поскольку для подклассового полиморфизма нужно работать с указателями решил заодно 
//использовать кучу, а затем, чтобы не писать сложный деструктор, обернул в умные 
//указатели. Ввиду того, что шаблоны использовать нельзя, приходится писать многие методы 
//в трёх экземплярах, соответственно смысла в полиморфизме мало.
Существует ли изящное решение (например, какие-нибудь шаблоны проектирования) данной задачи?
0
Лучшие ответы (1)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
24.07.2017, 20:14
Ответы с готовыми решениями:

Бинарное дерево с повторяющимися узлами - как их найти?
Всем добрый вечер. Сейчас сижу и сам пытаюсь понять тему связанную с деревьями, но возникла тупиковая ситуация, может даже какое то...

массив-текстБокс/Сортировка/текстБокс -массив(вызвать для трех разных типов)
Всем доброго времени суток! Заполняю массив элементов типа int из textBox1. Уже чем только не пробовал числа какие-то левые выводит в...

Создать массивы разных типов(3 типов), вывести их на экран
Создать массивы разных типов(3 типов), вывести их на экран.

21
 Аватар для RunningMan
278 / 186 / 75
Регистрация: 12.04.2017
Сообщений: 1,088
Записей в блоге: 2
24.07.2017, 21:48
Цитата Сообщение от VergilYamato Посмотреть сообщение
Существует ли изящное решение ... данной задачи?
Цитата Сообщение от VergilYamato Посмотреть сообщение
каждый узел может быть строкой, целым или вещественным числом,
Это только моё ИМХО.
Хранить строку и не заниматься ерундой.
1
4 / 3 / 0
Регистрация: 22.08.2014
Сообщений: 80
24.07.2017, 22:06  [ТС]
Как будет возможно отличить строку, например, "7.34" от числа 7.34?
1
79 / 67 / 28
Регистрация: 22.04.2016
Сообщений: 384
24.07.2017, 22:12
Цитата Сообщение от VergilYamato Посмотреть сообщение
Как будет возможно отличить строку, например, "7.34" от числа 7.34?
Даже, если вы сделаете разбиение шаблона на 3 типа, то при выводе дерева на экран, вы никак не увидите разницы между строкой и числом с плавающей точкой. Имхо.
0
4 / 3 / 0
Регистрация: 22.08.2014
Сообщений: 80
24.07.2017, 22:21  [ТС]
Цитата Сообщение от igdev Посмотреть сообщение
Даже, если вы сделаете разбиение шаблона на 3 типа, то при выводе дерева на экран, вы никак не увидите разницы между строкой и числом с плавающей точкой. Имхо.
При выводе допустим, а если мы захотим что-то сделать с числом, хранящимся внутри узла? Я пока вижу только решение, заключающееся в хранении пары "строка"-"инфа о настоящем типе", но это накладывает дополнительные расходы на перегонку число-строка и строка-число, которая непонятно как часто будет нужна.
0
 Аватар для RunningMan
278 / 186 / 75
Регистрация: 12.04.2017
Сообщений: 1,088
Записей в блоге: 2
24.07.2017, 22:22
перегонка к дереву то не относится.
0
4 / 3 / 0
Регистрация: 22.08.2014
Сообщений: 80
24.07.2017, 22:32  [ТС]
Цитата Сообщение от RunningMan Посмотреть сообщение
перегонка к дереву то не относится.
То есть, всё ок, если условный пользователь ожидает увидеть целое число в созданном им узле, а ему приходит строка?
0
зомбяк
 Аватар для TRam_
1585 / 1219 / 345
Регистрация: 14.05.2017
Сообщений: 3,940
24.07.2017, 22:32
Сделай дерево с пометками типа и указателями на объекты. Для получения преобразуешь указатель в тот тип, который указан ы пометке. А так, если памяти не жалко, можно в каждой ячейке держать и строку, и целое, и вещественное
1
 Аватар для RunningMan
278 / 186 / 75
Регистрация: 12.04.2017
Сообщений: 1,088
Записей в блоге: 2
24.07.2017, 22:45
Цитата Сообщение от VergilYamato Посмотреть сообщение
То есть, всё ок, если условный пользователь ожидает увидеть целое число в созданном им узле, а ему приходит строка?
Что вы там такое проектируете?
Ну храните структуру внутри узла. в чем проблема вообще?

Для чего нужно дерево как структура данных? Для хранения, поиска, сортировки.
Вы же возлагаете на дерево не те задачи.
1
79 / 67 / 28
Регистрация: 22.04.2016
Сообщений: 384
24.07.2017, 22:56
Цитата Сообщение от VergilYamato Посмотреть сообщение
а если мы захотим что-то сделать с числом
Цитата Сообщение от RunningMan Посмотреть сообщение
Для чего нужно дерево как структура данных? Для хранения, поиска, сортировки.
Если Вам нужно выполнять какие-то арифметические действия над числом, то стоит посмотреть в сторону односвязных или двусвязных списков. Иначе, использование деревьев для того, чтобы что-то сделать с числом не целесообразно.
0
4 / 3 / 0
Регистрация: 22.08.2014
Сообщений: 80
24.07.2017, 23:07  [ТС]
Цитата Сообщение от RunningMan Посмотреть сообщение
Что вы там такое проектируете?
Ну храните структуру внутри узла. в чем проблема вообще?
Честно говоря, я думал, я понятно описал задачу, попробую ещё раз: произвольное дерево (не бинарное/тернарное/n-арное, а с разным возможным числом потомков для разных узлов; не обладающее ни сбалансированностью, ни полнотой, ни чем-либо ещё из свойств). Каждый из узлов может быть (чтобы было понятнее, наверное, стоит сказать хранить) строкой (строку), целым числом (целое число) или вещественным числом (вещественное число). Логичным в данном случае мне показалось представить внутреннюю структуру узла как "Объект (строка/целое число/вещественное число)"-"массив указателей на детей", но при реализации выяснилось, что, либо непонятно как выводить тип того, что в массиве (под цифрой 1 в первом сообщении), либо происходит копирование кода по 3 раза (чтобы обработать строку/целое число/вещественное число - цифра 2 в первом сообщении). Для понятности, вот так выглядит добавление потомка в узел во 2-ом случае:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    void add_child(std::string &_val)
    {
        if(children.empty())
            children.resize(3);
        children.push_back(std::shared_ptr<node_data>(new str_node(_val)));
    }
    void add_child(int _val)
    {
        if(children.empty())
            children.resize(3);
        children.push_back(std::shared_ptr<node_data>(new int_node(_val)));
    }
    void add_child(float _val)
    {
        if(children.empty())
            children.resize(3);
        children.push_back(std::shared_ptr<node_data>(new float_node(_val)));
    }
Цели, с которыми дерево будет использоваться не указаны.

Добавлено через 5 минут
Цитата Сообщение от igdev Посмотреть сообщение
Если Вам нужно выполнять какие-то арифметические действия над числом, то стоит посмотреть в сторону односвязных или двусвязных списков. Иначе, использование деревьев для того, чтобы что-то сделать с числом не целесообразно.
Мне дерево нужно само по себе, а не для решения какой-либо задачи. Также ничего плохого не вижу в том, чтобы пройтись по дереву до нужного узла и изменить каким-то образом его значение.
0
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
24.07.2017, 23:14
Цитата Сообщение от VergilYamato Посмотреть сообщение
Требуется реализовать произвольное дерево, где каждый узел может быть строкой, целым или вещественным числом, и иметь любое количество детей, также одного из этих трёх типов (дети могут иметь разный тип).
1) union. Его уже научили хранить объекты с нетривиальным конструктором. Просто конструктор для одного из объектов union надо вызвать явно.
2) Виртуальные функции.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
class Tree
{
public:
    virtual bool isString()const{return false;}
    virtual bool isInt()const{return false;}
    virtual bool isDouble()const{return false;}
 
    virtual const std::string&getString()const{throw std::runtime_error("Ops..");}
    virtual int getInt()const{throw std::runtime_error("Ops..");}
    virtual double getDouble()const{throw std::runtime_error("Ops..");}
 
    std::vector<std::unique_ptr<Tree>> childList;
};
1
4 / 3 / 0
Регистрация: 22.08.2014
Сообщений: 80
24.07.2017, 23:59  [ТС]
Цитата Сообщение от Renji Посмотреть сообщение
1) union. Его уже научили хранить объекты с нетривиальным конструктором. Просто конструктор для одного из объектов union надо вызвать явно.
2) Виртуальные функции.
1) Перечитал про union: нашёл, что объекты внутри union могут друг друга перекрывать и всё. Можете привести пример, как оно хотя бы примерно должно выглядеть?
2) Не совсем понял, где находятся инкапсулируемые данные.

Добавлено через 6 минут
То есть, по идее, для очередного узла мы переопределяем соответствующие функции, например:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
class Tree
{
public:
    virtual bool isString()const{return true;}
    virtual bool isInt()const{return false;}
    virtual bool isDouble()const{return false;}
 
    virtual const std::string&getString()const{ return std::string("abc");}
    virtual int getInt()const{throw std::runtime_error("Ops..");}
    virtual double getDouble()const{throw std::runtime_error("Ops..");}
 
    std::vector<std::unique_ptr<Tree>> childList;
};
Но это всё должно быть определено на этапе компиляции, а нам нужно добавлять узлы в runtime.
0
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
25.07.2017, 00:14
Лучший ответ Сообщение было отмечено VergilYamato как решение

Решение

Цитата Сообщение от VergilYamato Посмотреть сообщение
1) Перечитал про union: нашёл, что объекты внутри union могут друг друга перекрывать и всё. Можете привести пример, как оно хотя бы примерно должно выглядеть?
2) Не совсем понял, где находятся инкапсулируемые данные.
1) Ну так и должно выглядеть - три поля в union, плюс флаг показывающий какое из них используется, плюс явный вызов конструктора/деструктора.
2) В потомках.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//это через union
class TreeUnion
{
public:
    enum Type{isString,isInt};
    TreeUnion(const std::string&value):type(isString),stringValue(value){}
    TreeUnion(int value):type(isInt),intValue(value){}
    ~TreeUnion()
    {
        if(type==isString)
            stringValue.std::string::~string();
    }
 
    Type type;
    union
    {
        std::string stringValue;
        int intValue;
    };
};
 
class TreeVirtual
{
public:
    virtual bool isString()const{return false;}
    virtual bool isInt()const{return false;}
    virtual bool isDouble()const{return false;}
 
    virtual const std::string&getString()const{throw std::runtime_error("Ops..");}
    virtual int getInt()const{throw std::runtime_error("Ops..");}
    virtual double getDouble()const{throw std::runtime_error("Ops..");}
 
    std::vector<std::unique_ptr<TreeVirtual>> childList;
};
 
//вот здесь хранится строка для TreeVirtual
class TreeString
{
public:
    bool isString()const{return true;}
    const std::string&getString()const{return value;}
    std::string value;
};
Добавлено через 15 секунд
Цитата Сообщение от Renji Посмотреть сообщение
class TreeString
Тьфу-ты, class TreeString:public TreeVirtual
1
 Аватар для Геомеханик
838 / 641 / 940
Регистрация: 26.06.2015
Сообщений: 1,409
25.07.2017, 06:47
Для большего развития лучше пытаться реализовывать B-Tree, B* -Tree, B+ -Tree, 2-3 Tree, 2-3-4 Tree, ну или Биномиальную и Фибоначчиеву кучу, если будет сложно то лучше начать тогда со skip-list, splay-tree, rand-tree, treap, RB-Tree, AVL-Tree...
0
93 / 69 / 22
Регистрация: 17.10.2011
Сообщений: 235
25.07.2017, 09:32
а почему не сделать через std::type_info
вроде меньше писанины выходит
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Elbase{
    virtual size_t typehash() =0;
};
 
template <typename T>
class Elem :Elbase {
    using value_type = typename std::enable_if
        <
            std::is_same<std::string, T>::value ||
            std::is_same<int, T>::value ||
            std::is_same<float, T>::value, T
        >::type;
    size_t typehash(){ return typeid(T).hash_code();};
    T val;
};
тут и в контейнер запихать можно все подряд
0
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
25.07.2017, 13:35
Цитата Сообщение от vndtta Посмотреть сообщение
а почему не сделать через std::type_info
А по стандарту им уже можно пользоваться? "std::type_info::name - No guarantees are given; in particular, the returned string can be identical for several types and change between invocations of the same program. ". Такие цитатки наводят на мысль что лучше обходить этот type_info за пушечный выстрел. Максимум в какую ни будь систему логирования воткнуть.
0
93 / 69 / 22
Регистрация: 17.10.2011
Сообщений: 235
25.07.2017, 13:50
Цитата Сообщение от Renji Посмотреть сообщение
А по стандарту им уже можно пользоваться? "std::type_info::name - No guarantees are given; in particular, the returned string can be identical for several types and change between invocations of the same program. ". Такие цитатки наводят на мысль что лучше обходить этот type_info за пушечный выстрел. Максимум в какую ни будь систему логирования воткнуть.
а как же
Code
1
Remarks: An implementation should return different values for two type_*info objects which do not compare equal.
?
1
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
25.07.2017, 14:00
Цитата Сообщение от vndtta Посмотреть сообщение
а как же
Хм, действительно, значит на http://en.cppreference.com чего-то попутали.
0
93 / 69 / 22
Регистрация: 17.10.2011
Сообщений: 235
25.07.2017, 16:28
по-моему там самому можно это дописать

Добавлено через 5 минут
п.с. ну все, я дописал
интересно, отменят правку или нет

Добавлено через 2 часа 2 минуты
в общем правку отменили и добавили дополнительно информации, что объекты, отоносящиеся к разным типам, могут иметь одинаковый хеш.

только мне все равно не понятно, разные типы и разные объекты type_info - это одно и тоже или нет?

Добавлено через 20 минут
конечный вывод - использовать
Code
1
type_index(typeid(T))
- он то уж точно уникальный для каждого объекта type_info
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
25.07.2017, 16:28
Помогаю со студенческими работами здесь

Бинарное дерево с использованием ссылочных типов
Здравствуйте! Я продолжаю изучение Пролога в универе (работаю на прологе 7.5). Задали задание реализовать бинарное дерево с помощью...

Хранение разных типов
Приветствую всех. Возник вот такой вопрос. У меня есть, например, 3 разных структуры, каждая из которых имеет разные поля: struct one ...

Матрица из разных типов
хочу создать клас Matrix елементы обьектов которого могли бы быть разных типов. была идея создать клас Cell и определить его как...

Коллекции разных типов
Добрый день! Подскажите, пожалуйста! Необходимо создать класс, который будет читать данные из файла 1. Про коллекцию объектов...

Массив разных типов
Подскажите пожалуйста!Ситуация следующая: Есть масив с числами int arr_id; Есть масив с строками: string str_answers; Мне нужно...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Нашел на реддите интересную статью под названием «Кто-нибудь знает, где получить бесплатный компьютер или. . .
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru