Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
vadim_bz
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
#1

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

05.06.2016, 18:53. Просмотров 545. Ответов 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:
Необязательно себя утруждать и писать код, приму любую помощь. Достаточно просто объяснить, как это возможно реализовать, либо не возможно и свой вариант решения задачи.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.06.2016, 18:53     Подобие графа
Посмотрите здесь:

Подобие игры - C++
Ребята. Начал писать, но тут проблема. Программа не работает. Он запускает лишь ранее скомпилированный код (который &quot;загружает&quot; игру), а...

Подобие чата с ботом - C++
А как сделать что то на подобе чата с ботом Тоесть что-бы если я написал в консоль слово которое я укажу в коде например asd то будет...

Подобие базы данных - C++
А если быть точнее, то цель стоит- вывести перед пользователем список, из которого он нажатием клавиши 1 2 или 3 4 5выберет интересующий...

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

Робот (подобие игры Sokoban) - C++
Написать программу, на подобие игры Sokoban 1) создаёте матрицу нужного размера 2) из входного файла считываете заполнение поля 3)...

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

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
vadim_bz
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
07.06.2016, 20:29  [ТС]     Подобие графа #16
Vort_ , у меня так и выходит, что каждые соседние комнаты имеют указатели на друг друга. Я думал сделать так, что бы при вызове деструктора для произвольной комнаты начинался поиск крайней комнаты графа (которая имеет только одну ссылку на соседнюю), очистить её, вернуться обратно и снова начать поиск крайней, пока комнат не останется.
Но это и правда ломается если комнат всего 1 или где то не протянута обратная связь.
vadim_bz
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
07.06.2016, 20:34  [ТС]     Подобие графа #17
Кликните здесь для просмотра всего текста
Подобие графа
Mr.X
Эксперт С++
3048 / 1693 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
07.06.2016, 21:52     Подобие графа #18
Цитата Сообщение от vadim_bz Посмотреть сообщение
ах да, забыл сказать, сделал всё с выделением памяти и после создания всё это живёт не умирая. Вот и подумываю, как лучше организовать очищение (деструктор).
Умные указатели используйте.
Vort_
186 / 186 / 52
Регистрация: 10.07.2012
Сообщений: 400
08.06.2016, 06:30     Подобие графа #19
мне кажется, что как загрузкой, так и удалением графа должна заниматься внешняя, по отношению к элементу, сущность
задача же деструктора элемента - уничтожить именно элемент
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; }
    };
Toshkarik
1140 / 857 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
08.06.2016, 18:09     Подобие графа #21
vadim_bz, после выхода из функции ptr уничтожит объект, и weak_ptr в векторе будет невалидным.

Добавлено через 1 минуту
Что бы использовать weak_ptr, для каждой комнаты нужен shared_ptr, который, к примеру, будет хранится во внешнем контейнере, вроде вектора.
vadim_bz
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
08.06.2016, 18:59  [ТС]     Подобие графа #22
Мда, выходит тогда что-то сложное и не очень красивое, уж проще тогда где то держать вектор с указателями на все элементы, уж лучше такой баласт, чем все эти заморочки с "умными указателями", где в конечном счёте так же придётся держать вектор, но только с shared_ptr.
Toshkarik
1140 / 857 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
08.06.2016, 19:02     Подобие графа #23
vadim_bz, в случае shared_ptr и weak_ptr мы точно можем знать, когда объект уничтожен и weak_ptr не валидный. Ну и избежим new/delete.
vadim_bz
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
08.06.2016, 19:58  [ТС]     Подобие графа #24
Toshkarik, я хотел то как, функция строящая граф возвращает обычный указатель на первый элемент графа (созданный первым), затем навигация осуществляется путём перебора в цикле ближайших соседей, по какому-нибудь условию, и если условие выполняется то этот указатель приравнивается новому элементу графа. А теперь получается с shared_ptr такое не провернуть да и весь массив нужно выводить. Либо сделать что бы первый элемент массива был навигационный (то что описал ранее), другими словами - текущее положение в графе, а остальные уже элементы массива - это элементы графа и тогда один этот массив выводить из функции создания графа.
Vort_
186 / 186 / 52
Регистрация: 10.07.2012
Сообщений: 400
08.06.2016, 20:04     Подобие графа #25
Я не понимаю что мешает держать и массив и указатель на какой-то элемент.
Массив будет использоваться при создании и уничтожении графа, а указатель - для навигации по нему.
Toshkarik
1140 / 857 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
08.06.2016, 20:23     Подобие графа #26
Ну, я вижу это примерно так:
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
class Room {
public:
   Room( const std::string &roomName, const std::string &roomStory )
   :  name( roomName ),
      story( roomStory )
   {
 
   }
 
   ~Room() {
 
   }
 
   const std::string &getName() const {
      return name;
   }
 
   const std::string &getStory() const {
      return story;
   }
   //если нужно, реализовываем set-функции
 
   void link( std::shared_ptr< Room > room ) {
      links.push_back( room );
   }
 
private:
   std::string name;
   std::string story;
 
   std::vector< std::weak_ptr< Room > > links;
};
 
int main() {
   std::vector< std::shared_ptr< Room >> rooms;
 
   //тут считываем все комнаты в вектор ( исключая связи )
 
   for ( auto &it : rooms ) {
      //тут заполняем связи с помощью функции link
   }
 
   return 0;
}
При этом связи могут хранится в файле после описания всех комнат. Причем, как можно заметить, они двусторонние, поэтому можно просто указывать пары:

Код
имяКомнаты1 описаниеКомнаты1
имяКомнаты2 описаниеКомнаты2
имяКомнаты3 описаниеКомнаты3
имяКомнаты4 описаниеКомнаты4
1 2 //первая и вторая связаны
1 3 //первая и третья связаны
2 4 //вторая и четвертая связаны
vadim_bz
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
08.06.2016, 20:24  [ТС]     Подобие графа #27
Vort_, да наверное так и сделаю, а мой вариант с навигационным указателем, как первым элементом массива неадекватен?
Toshkarik
1140 / 857 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
08.06.2016, 20:28     Подобие графа #28
Последний цикл неверно записал, там нужно считывать до конца файла, но идею я думаю Вы должны понять.
Vort_
186 / 186 / 52
Регистрация: 10.07.2012
Сообщений: 400
08.06.2016, 20:32     Подобие графа #29
Цитата Сообщение от vadim_bz Посмотреть сообщение
Vort_, да наверное так и сделаю, а мой вариант с навигационным указателем, как первым элементом массива неадекватен?
Если не запутаться и не удалить потом элемент дважды, то можно.
Но я бы разнёс.
Сделал бы, к примеру, класс Graph, туда положил массив и указатель на текущий элемент.
А также методы по заполнению и очистке массива.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.06.2016, 20:47     Подобие графа
Еще ссылки по теме:

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

Обход графа в ширину - C++
Подскажите, как во время обхода графа в ширину помечать вершины как четные и не четные?

Варианты обхода графа - C++
подскажите пожалуйста сколько путей существует для такого графа, чтобы проходить через каждую Добавлено через 44 секунды или...

Обход в ширину графа - C++
Здравствуйте, помогите пожалуйста разобраться что не так в алгоритме работы обхода в ширину графа( Заданию матрицу Число вершин ...

Хроматическое число графа - C++
Здравствуйте =) Не можете подсказать какой-либо алгоритм нахождения хроматического числа графа


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

Или воспользуйтесь поиском по форуму:
vadim_bz
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
08.06.2016, 20:47  [ТС]     Подобие графа #30
Цитата Сообщение от Toshkarik Посмотреть сообщение
Последний цикл неверно записал, там нужно считывать до конца файла, но идею я думаю Вы должны понять.
Да примерно такой и вышел второй вариант, спасибо))

Думаю вопрос теперь точно исчерпан, всем ещё раз большое спасибо!
Yandex
Объявления
08.06.2016, 20:47     Подобие графа
Ответ Создать тему
Опции темы

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