Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
vadim_bz
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
#1

Подобие графа - C++

05.06.2016, 18:53. Просмотров 633. Ответов 29
Метки нет (Все метки)

Имеется примерно такой вот класс:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Room {
    private:
        string name;
        string story;
        vector <Room*> rooms; //указатели, куда доступен переход
    public:
        Room () {}
        Room (string name, string story) {
            this->name = name;
            this->story = story;
            }
    public:
        string getName () const { return name; }
        string getStory () const { return story; }
    };
Нужно создать некое подобие графа, элементом которого был бы класс расположенный выше. Переменная rooms содержала бы указатели на все доступные соседние элементы. И вот всё голову ломаю и придумать не могу, как это всё грамотно организовать. А именно, в каком формате будет ввод (но обязательно из файла) и как это всё дело потом создать и связать опираясь на ввод. Буду рад любым пинкам в правильном направлении.

Добавлено через 5 часов 24 минуты
UPD:
Необязательно себя утруждать и писать код, приму любую помощь. Достаточно просто объяснить, как это возможно реализовать, либо не возможно и свой вариант решения задачи.
http://www.cyberforum.ru/cpp-beginners/thread324659.html
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.06.2016, 18:53
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Подобие графа (C++):

Подобие треугольников
На проверочном сайте проходит 80%, где ошибка? Заданы два треугольника: ABC...

Подобие игры
Ребята. Начал писать, но тут проблема. Программа не работает. Он запускает...

Подобие базы данных
А если быть точнее, то цель стоит- вывести перед пользователем список, из...

Подобие чата с ботом
А как сделать что то на подобе чата с ботом Тоесть что-бы если я написал в...

Робот (подобие игры Sokoban)
Написать программу, на подобие игры Sokoban 1) создаёте матрицу нужного...

29
Vort_
190 / 190 / 78
Регистрация: 10.07.2012
Сообщений: 400
05.06.2016, 19:00 #2
Я думал как раз код написать .
Идея в том, чтобы делать связи в файле по индексам или по ключам.
0
vadim_bz
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
05.06.2016, 19:01  [ТС] #3
UPD2:
То что уже имеется:
-все возможные объекты room вводятся из файлов
Из идей было такое:
-названия этих файлов (с набором данных для room, описано выше) будут расположены иерархически в файле - карте и в зависимости от степени вложенности - присваивать каждому названию индекс.
-В соответствии индексу и протягивать связи между объектами, создавая тем самым граф.

Но с реализацией в тупике.
0
Vort_
190 / 190 / 78
Регистрация: 10.07.2012
Сообщений: 400
05.06.2016, 19:08 #4
Зачем объектам комнат иерархичность?
Можно, к примеру, иметь четыре записи/файла:
0: Первая комната, связи: 1, 2
1: Вторая комната, связи: 0, 3
2: Третья комната, связи: 0, 3
3: Четвёртая комната, связи: 1, 2
Затем по этим данным при загрузке восстанавливать массив указателей.

Добавлено через 1 минуту
Или вопрос в том, как по таким данным восстановить объекты?
0
vadim_bz
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
05.06.2016, 19:14  [ТС] #5
Vort_, о таком варианте структуры файла - карты и не подумал, хотел как-то сделать что-бы и наглядно было ясно что-куда и что-бы это потом можно было индексировать от степени вложенности. Но теперь от этой идеи откажусь.

Но это даже наверное не главная проблема, не хватает информации и знаний о том, как потом имея индексы воссоздать граф такого типа, не много информации по этому поводу нашёл. Если вас не затруднит, я бы был рад если вы покажите как.
0
Vort_
190 / 190 / 78
Регистрация: 10.07.2012
Сообщений: 400
05.06.2016, 19:31 #6
Лучший ответ Сообщение было отмечено vadim_bz как решение

Решение

Вот пример:
Файл:
Код
4
First room
First room description
2 1 2
Second room
Second room description
2 0 3
Third room
Third room description
2 0 3
Fourth room
Fourth room description
2 1 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
44
45
46
47
48
49
50
51
52
53
54
#include <vector>
#include <string>
#include <fstream>
#include <iostream>
 
using namespace std;
 
class Room {
private:
    string name;
    string story;
    vector<Room*> rooms;
public:
    Room() {}
    Room(string name, string story) {
        this->name = name;
        this->story = story;
    }
public:
    string getName() const { return name; }
    string getStory() const { return story; }
    void addLink(Room* link) { rooms.push_back(link); }
};
 
void main()
{
    ifstream file;
    file.open("rooms.txt");
 
    int roomCount;
    file >> roomCount;
    file.ignore();
 
    vector<Room> rooms(roomCount);
    for (int i = 0; i < roomCount; i++)
    {
        string name;
        string story;
        getline(file, name);
        getline(file, story);
        rooms[i] = Room(name, story);
 
        int linkCount;
        file >> linkCount;
 
        for (int j = 0; j < linkCount; j++)
        {
            int linkedIndex;
            file >> linkedIndex;
            rooms[i].addLink(&rooms[linkedIndex]);
        }
        file.ignore();
    }
}
1
Mr.X
Эксперт С++
3178 / 1705 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
06.06.2016, 13:12 #7
Цитата Сообщение от vadim_bz Посмотреть сообщение
Нужно создать некое подобие графа, элементом которого был бы класс расположенный выше.
Ну, комнаты у вас и так связаны и образуют граф через указатели. А вы в каком виде граф хотите получить?
0
vadim_bz
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
06.06.2016, 13:19  [ТС] #8
Mr.X, именно так и хотел, не был уверен в номенклатуре, так как при поисках находил нечто иное, отличное от желаемого.
0
vadim_bz
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
07.06.2016, 18:19  [ТС] #9
Уж коль далеко не ходить, как устроить для него очищение выделенной памяти?) Думаю обращаться в деструкторе к тому же файлу - карте не совсем правильно, может сделать так что бы при вызове деструктора любой комнаты очищался бы весь граф сразу, или тоже вариант не очень?
0
Vort_
190 / 190 / 78
Регистрация: 10.07.2012
Сообщений: 400
07.06.2016, 18:22 #10
Если использовать мой вариант - vector<Room>, то он сам очистится как выйдет из области видимости.
0
vadim_bz
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
07.06.2016, 19:08  [ТС] #11
Vort_, ах да, забыл сказать, сделал всё с выделением памяти и после создания всё это живёт не умирая. Вот и подумываю, как лучше организовать очищение (деструктор).
0
Vort_
190 / 190 / 78
Регистрация: 10.07.2012
Сообщений: 400
07.06.2016, 19:13 #12
За один элемент всё держится что ли?
Если так, то можно создать временный массив, закинуть в него указатели на все элементы.
Затем пройтись по массиву и очистить у каждого объекта ссылки на соседние комнаты (не удаляя объекты).
После чего в цикле удалить все объекты в массиве.

Но точно сказать, не понимая структуры решения, я не могу.
1
Toshkarik
1148 / 865 / 90
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 1
07.06.2016, 19:34 #13
Используйте shared_ptr.
0
Vort_
190 / 190 / 78
Регистрация: 10.07.2012
Сообщений: 400
07.06.2016, 19:35 #14
Цитата Сообщение от Toshkarik Посмотреть сообщение
Используйте shared_ptr.
Только поможет ли это, если комнаты связаны в кольцо?
0
Toshkarik
1148 / 865 / 90
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 1
07.06.2016, 19:38 #15
Да, упустил из вида. Тогда weak_ptr.
1
vadim_bz
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
07.06.2016, 20:29  [ТС] #16
Vort_ , у меня так и выходит, что каждые соседние комнаты имеют указатели на друг друга. Я думал сделать так, что бы при вызове деструктора для произвольной комнаты начинался поиск крайней комнаты графа (которая имеет только одну ссылку на соседнюю), очистить её, вернуться обратно и снова начать поиск крайней, пока комнат не останется.
Но это и правда ломается если комнат всего 1 или где то не протянута обратная связь.
0
vadim_bz
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
07.06.2016, 20:34  [ТС] #17
Кликните здесь для просмотра всего текста
Подобие графа
0
Mr.X
Эксперт С++
3178 / 1705 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
07.06.2016, 21:52 #18
Цитата Сообщение от vadim_bz Посмотреть сообщение
ах да, забыл сказать, сделал всё с выделением памяти и после создания всё это живёт не умирая. Вот и подумываю, как лучше организовать очищение (деструктор).
Умные указатели используйте.
0
Vort_
190 / 190 / 78
Регистрация: 10.07.2012
Сообщений: 400
08.06.2016, 06:30 #19
мне кажется, что как загрузкой, так и удалением графа должна заниматься внешняя, по отношению к элементу, сущность
задача же деструктора элемента - уничтожить именно элемент
0
vadim_bz
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
08.06.2016, 17:55  [ТС] #20
Не правильно?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Room {
    private:
        string name;
        string story;
        vector <weak_ptr <Room>> *rooms;
    public:
        Room () {}
        Room (string name, string story) {
            this->name = name;
            this->story = story;
            rooms = new vector <weak_ptr <Room>>;
            }
        void addRoom (Room *room) { 
            shared_ptr <Room> ptr;
            ptr = make_shared <Room> (*room);
            rooms->push_back(ptr);
            delete room;
            }
    public:
        string getName () const { return name; }
        string getStory () const { return story; }
        //vector <Room*> *get_ptrRooms () const { return rooms; }
    };
0
08.06.2016, 17:55
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.06.2016, 17:55
Привет! Вот еще темы с решениями:

Подобие math.h для геометрии
Существуют ли такие библиотеки? И где их взять.. Например, нужно найти...

Как сделать подобие case из Pascal в C++
Есть программа, в ней 3 задачи, как сделать как в паскале что бы при открытии...

Подобие MessageBox выводящего INT и LPCSTR . Не тупо ли ?
Привыкшему к удобствам PHP с++ нубу захотелось сделать такое вот извращение.....

Обращение к методам базового класса (есть ли подобие base/super?)
Понятное дело, что можно обращаться к методам базового класса так:...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru