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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.95
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
#1

Топологическая сортировка - C++

11.04.2013, 05:36. Просмотров 2635. Ответов 24
Метки нет (Все метки)

Здорова!
Тут от вычитал новое понятие "топологическая сортировка".
Вообщем есть задачка нужно сделать топологическу сортировку описаную в Кнут т1 (второе издание) ст 262.?????
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.04.2013, 05:36
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Топологическая сортировка (C++):

Топологическая сортировка - C++
Ошибка в строке 34, подскажите как исправить: 'reverse' was not declared in this scope // Top_Sort.cpp: определяет точку входа для...

Топологическая сортировка (содержание файла) - C++
Приветствую. Не так давно столкнулся с топологической сортировкой графа на c++. У программы задача отрисовывать граф и, соответственно,...

Сортировка Шелла. Написал программу, не могу понять, почему сортировка не выполняется - C++
Программа создает динамический массив с рандомным заполнением. Дальше выбор сортировок, пузырьком или сортировка Шелла. Вот она то и не...

Сортировка слиянием. В каком куске кода происходит сортировка и каким именно образом? - C++
Помогите, пожалуйста, разобраться. Подскажите в каком куске кода происходит сортировка и каким именно образом? #include <iostream> ...

Быстрая сортировка (сортировка Хоара) для связных списков - C++
есть у кого готовый алгоритм? или подскажите как реализовать

Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива - C++
Мне нужно отсортировать фрагмент массива, расположенный между первым и последним отрицательным элементом. Немогу понять как устоновить...

24
UnsKneD
алкокодер
154 / 150 / 11
Регистрация: 27.12.2012
Сообщений: 548
11.04.2013, 05:48 #2
ninja2, http://rain.ifmo.ru/cat/view.php/vis...2007/algorithm
http://hashcode.ru/questions/41924/c...B2%D0%BA%D0%B0
0
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
11.04.2013, 11:41  [ТС] #3
Ничо не понял. Есть допустим ассоциативный массив map<string, int>, как мне его отсортировать по топологической сортировке????


Для массива нужно сделать Map своего, но если для своего можно, то значит и для просто map можно. Пример кода в студию!
0
salam
165 / 146 / 14
Регистрация: 10.07.2012
Сообщений: 738
11.04.2013, 15:53 #4
по-моему, вы не понимаете, что делает этот алгоритм... он должен расставить вершины орграфа таким образом, чтобы ребра шли из вершин с меньшим номером в вершины с большим...
то есть надо найти некую перестановку вершин, чтобы можно было строго сказать, что из данной вершины мы пойдем только вперед по ребрам и сворачивать никуда не будем... (последнее - от себя, вероятно, коряво)
0
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
11.04.2013, 16:06  [ТС] #5
А как же я задачку решу? Там нужно применить эту сортировку для сортировки пользовательского массива Map построенного на двоичном дереве?

Задача: "Используйте Map для выполнения топологической сортировки описано в Кнут..."
0
salam
165 / 146 / 14
Регистрация: 10.07.2012
Сообщений: 738
11.04.2013, 16:06 #6
дерево - это граф...
0
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
11.04.2013, 16:07  [ТС] #7
salam, Головняк да?
0
salam
165 / 146 / 14
Регистрация: 10.07.2012
Сообщений: 738
11.04.2013, 16:08 #8
вам лучше начать с задач попроще.
0
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
11.04.2013, 16:10  [ТС] #9
salam, а если я просто извлечу все элементы из дерева запишу их в массив, а затем заново загоню их в дерево токо уже из отсортированного массива, тоже дерево отсортируется. хз. Так зато понятней?

Добавлено через 52 секунды
salam, яж могу ее так решить вытянуть элементы запись в массив, а затем вставить и все сортированое дерево, но хотелось бы применить топологическую сортировку, так чтобы знать.

Попроще я нихо хо эту сделать тем более там уровень сложности *2.5 типо часа 4 работы.

А можно в вектор загнать узлы дерева, а затем уже из них новое дерево сформировать отсортированное, а старое удалить.
0
salam
165 / 146 / 14
Регистрация: 10.07.2012
Сообщений: 738
11.04.2013, 16:12 #10
да дело не в расположении элементов по возрастанию/убыванию... это совсем другая задача... читайте книги...
0
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
11.04.2013, 16:14  [ТС] #11
salam, Это как раз мой уровень сложности сортировать, то я знаю как.

Добавлено через 49 секунд
salam, Да читал поля там подобавлять нада цвета им дать, головняк.

Добавлено через 51 секунду
Я просто от смотрю раз тут мало так людей в этой теме, то видимо в нее и углубляться не стоит, видимо не популярная и фиг кода пригодиться.
0
taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
11.04.2013, 16:16 #12
Цитата Сообщение от ninja2 Посмотреть сообщение
А как же я задачку решу? Там нужно применить эту сортировку для сортировки пользовательского массива Map построенного на двоичном дереве?
дерево тоже граф.
0
salam
165 / 146 / 14
Регистрация: 10.07.2012
Сообщений: 738
11.04.2013, 16:18 #13
это один из базовых графовых алгоритмов. он нужен в некоторых сложных и весьма полезных в определенной ситуации алгоритмах на графах. я считаю, что разработчик должен это уметь. за себя решайте сами.
0
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
11.04.2013, 16:20  [ТС] #14
salam, А как же мне сделать? Там то того кода 20 строк, а я фиг разберусь. Вроде с виду и не сложно делать. Хо сделать, да не лень разбираться.
Наверно придется вникнуть, хоть хочется хоть не хочется, тем более что вроде мало там написано и небось простой раз популярный.
Хотя подумать хорошо яж не разработчик. Значит мне это уметь не обязательно. Наверно забью. Для успокоения совести сделаю просто сортировку вытянуть элементы закинуть в массив, а затем новое дерево сформировать отсортированное. Как буду разработчиком тада изучу
0
salam
165 / 146 / 14
Регистрация: 10.07.2012
Сообщений: 738
11.04.2013, 16:21 #15
попу прижмите к стулу и учитесь...
0
11.04.2013, 16:21
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.04.2013, 16:21
Привет! Вот еще темы с ответами:

Сортировка Шелла и пирамидальная сортировка для символов - C++
Здраствуйте, можете пожалуйста привести пример сортировок шелла и пиромидальной сортировки для символов, а то ничего не могу ...

Сортировка вектора по полю(Сортировка вставками) - C++
Здравствуйте! Нужно написать сортировку вектора по полю weight класса tomato. Вот класс: #pragma once #include &lt;iostream&gt; ...

C/C++ FAQ :: Быстрая сортировка (сортировка Хоара) - C++
Вопрос, скорее академический, по мотивам реализации. Вот в faq приведена реализация этого метода сортировки на C++. В коде есть следующий...

2 сортировки: пирамидальная сортировка и сортировка слиянием - C++
Реализовать два улучшенных алгоритма сортировки. Для каждого алгоритма вычислить показатель качества сортировки (количество операций, т.е....


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

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

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