53 / 53 / 8
Регистрация: 21.03.2009
Сообщений: 371
|
||||||
1 | ||||||
Функция: определить, содержит ли односвязный список циклы09.08.2011, 13:51. Показов 4247. Ответов 19
Метки нет (Все метки)
По скольку я не могу задавать вопросы в разделе С++ для специалистов,задаю его здесь
Была тема Написать функцию, определяющую содержит ли односвязный список циклы (например, последний ссылается на второй). Может я чего то не допонял(просто мне показалось,что приведенные решения были очень раздуты),но в односвязном списке зациклиться может только при участии последнего узла.Если нам зарание известно кол-во узлов то,все сводится к тому куда указывает
0
|
09.08.2011, 13:51 | |
Ответы с готовыми решениями:
19
Задали односвязный линейный список с целыми числами. Создать новый список, который содержит элементы заданного списка в обратном порядке Односвязный список.Функция удаления Односвязный список: функция добавления записи не работает Функция добавления элемента в односвязный список в указанную позицию |
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
|
09.08.2011, 13:58 | 2 |
Правильно. Но откуда известно, какой из них последний? Вот поэтому то и используется проверка всего списка, пока не встретится указатель, который уже был.
0
|
53 / 53 / 8
Регистрация: 21.03.2009
Сообщений: 371
|
||||||
09.08.2011, 17:50 [ТС] | 4 | |||||
Вопроса,по сути нет,есть попытка разобраться зачем нужна такая сложная(на мой взгляд) реализация простого алгоритма?Часто сталкиваюсь с тем что люди замысловато кодируют не сложные вещи,поэтому хочу понять как все таки правильно делать?Я пишу код по правилу: Все должно быть очень просто!
А STL библиотеку использую только если заранее известно,что нужно будет часто использовать ее алгоритмы.Даже если и использовать в этом случае STL наверно лучше использовать queue потому что это лучше подходит к однонаправленному списку? Но откуда известно, какой из них последний? Отсюда известно
0
|
09.08.2011, 18:05 | 5 |
Допустим у тебя есть указатель на 1-й элемент списка. Ты отталкиваясь от него идешь на следующий, следующий и так далее... Так вот если этот следующий == первому значит список цикличен.
Я себе так это представляю.
0
|
1069 / 848 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
|
|
09.08.2011, 18:31 | 6 |
lazybiz, Не обязательно равен первому . Может быть ссылка на людой элемент списка. В том числе - на себя.
0
|
53 / 53 / 8
Регистрация: 21.03.2009
Сообщений: 371
|
|||||||||||
09.08.2011, 18:44 [ТС] | 7 | ||||||||||
Вопрос не в том,как определить есть ли цикл!А наверное как правильно кодировать такого рода задачи
вы не правильно представляете,а если последний указывает на второй или на третий? не будете же вы каждый новый узел сравнивать со всеми предыдущими! Здесь достаточно узнать адрес последнего узла и в нем посмотреть чему равняется last_node->next и поскольку адреса в куче выделяются последовательно,то
0
|
53 / 53 / 8
Регистрация: 21.03.2009
Сообщений: 371
|
|
09.08.2011, 19:11 [ТС] | 9 |
В книги прочитал.Только в какой сейчас не вспомню
Добавлено через 17 минут кроме того,если бы это было не так,то была бы возможна такая ситуация,что в куче есть две ячейки размером word идущие не последовательно и объект размером dword тогда для этого объекта не бало бы места,а это не рациональное использование памяти
0
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
|
09.08.2011, 19:29 | 10 |
0
|
53 / 53 / 8
Регистрация: 21.03.2009
Сообщений: 371
|
|
09.08.2011, 19:33 [ТС] | 11 |
а где мной написанно ЗАМЕНИТЬ?
0
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
|
09.08.2011, 19:36 | 12 |
В принципе, если список односвязный, то без разницы с какого узла начинать проверку.
Нужно сохранить адрес первого проверяемого узла и ринуться дальше, до конца. Если есть цикл, то в итоге вернёшься к этому же узлу. т.е. дополнительно требуется всего один указатель и сложность линейно зависит от количества элементов. В любых других ситуациях речь идёт уже о двух односвязных списках. Проверить можно точно так же, но сложность станет квадратичной. Но два списка вместо одного - ошибка. Я вообще не понимаю, что это за задача. Наверное постановка не корректна. Добавлено через 54 секунды А слово Использовать что подразумевало? Как вообще очередь там оказалась?
0
|
2381 / 1665 / 279
Регистрация: 29.05.2011
Сообщений: 3,399
|
|
09.08.2011, 19:42 | 13 |
Можешь смеяться, но так и есть. В куче может быть такая ситуация, что 100 МБ свободно, но при этом нельзя выделить и 1 МБ. Избежать фрагментации кучи — не такое уж и лёгкое дело (в общем случае).
0
|
53 / 53 / 8
Регистрация: 21.03.2009
Сообщений: 371
|
|
09.08.2011, 19:58 [ТС] | 14 |
https://www.cyberforum.ru/cpp-... 08978.html
Там был использован контейнер set,а я сказал,что может лучше использовать queue для сохранения элементов списка поскольку очередь лучше отображает однонаправленный список Добавлено через 6 минут grizlik78, а можешь направить где это можно прочесть?
0
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
|
09.08.2011, 20:05 | 15 |
ПОЧЕМУ НЕ std::list??? Каким образом ты можешь заменить set/list очередью? Это не совместимые контейнеры. Если ты можешь заменить set очередью, то это ошибка проектирования. Или совершенно без разницы, какой контейнер использовать и тогда нужно использовать std::vector.
0
|
2381 / 1665 / 279
Регистрация: 29.05.2011
Сообщений: 3,399
|
|
09.08.2011, 20:10 | 16 |
Не знаю. Но давай попробуем смоделировать. Вот есть куча с размером в 100 объектов некоторого типа. И мы последовательно создаём 100 элементов списка. Пусть при этом память нам выделялась последовательно, тогда действительно каждый следующий элемент имеет адрес бльше предыдущего, а в куче больше нет места. Теперь удаляем элемент из головы (с освобождением памяти) и пытаемся создать новый в конце. Какой у него будет адрес? Естественно адрес бывшего первого элемента, ведь вся остальная часть кучи занята.
Да даже и такие сложности ни к чему, если вспомнить, что обмен значений в списке производится обычно просто заменой ссылок (указателей), а сами элементы остаются в куче на своих местах.
0
|
53 / 53 / 8
Регистрация: 21.03.2009
Сообщений: 371
|
|
09.08.2011, 20:16 [ТС] | 17 |
Потому что List больше подходит для двусвязного списка.А на счет выбора контейнера ты по сути прав.Я смотрел реализации которые были предложены и они мне показались не много "раздуты" вот я и пытаюсь разобраться
0
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
|
09.08.2011, 20:22 | 18 |
Очередь не может заменить список (никакой), та же как и set не может заменить список.
Если память мне не изменяет, в STL список как-раз двусвязный. Это было бы вполне логично, т.к. оверхэда всё равно нет, благодаря особенностям распределения памяти.
0
|
Модератор
12458 / 7482 / 1753
Регистрация: 25.07.2009
Сообщений: 13,762
|
||||||
10.08.2011, 01:53 | 19 | |||||
Может я, любитель, чего-то не понимаю, но обратные ссылки в списке как-то так должны бы находиться:
0
|
53 / 53 / 8
Регистрация: 21.03.2009
Сообщений: 371
|
|
10.08.2011, 13:35 [ТС] | 20 |
Всем спасибо за участие!
0
|
10.08.2011, 13:35 | |
10.08.2011, 13:35 | |
Помогаю со студенческими работами здесь
20
Определить содержит ли граф циклы Создать новый односвязный список, который содержит элементы заданного списка в порядке убывания Объясните как работает функция добавления в односвязный список Вложенные циклы: определить, содержит ли последовательность хотя бы два равных соседних числа Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |