Всем доброго времени сУток!
Вопрос в следующем.
Есть двусвязный список:

Как(в теории) определить, закольцован он или нет?
Рекурсия не подходит. Сами понимаете почему.
В общем...любопытно Ваше мнение.

Спасибо за внимание.

берешь два итератора("быстрый" и "медленный" ), пускаешь их по кругу, где на два шага "быстрого" приходится один шаг "медленного"..
проверяешь оба итератора на равенство после каждого шага "быстрого", и если встретились раньше, чем "быстрый" дошел до конца, значит список закольцован.
  


Это сообщение отредактировал(а) mes - 12.4.2009, 21:33

100% результат - это создание массива указателей, в который помещать каждый узел и пробежаться по списку. Если такой адрес в массиве есть - значит закольцованность.
Менее надежно - ввести в узлы служебное поле, которому присваивать определенное значение. Дошли до узла с таким значением - закольцован. Менее надежен потому, что случайно такое значение может быть. Для чистоты эксперимента прогнать второй раз с другим значением.

для еще большей чистоты - прогнать третий раз
потом четвертый
потом пятый
а потом доказывать начальству, что такого не может быть, что после пятого раза такой обломище

ЗЫЖ к стенке надо таких прграммистов

Добавлено через 2 минуты и 9 секунд
2mes, 

а я там давал вторую часть задачи? починить список?

Третий не нужно - для проверки 2-х раз достаточно   


За что меня к стенке?    Я всего-лишь предложил 2 варианта - первый мне больше нравится.    Вашего варианта я же не видел - может он лучше, я бы свои не предлагал.

Злые вы.   

т.е. второй раз "случайно такое значение"(С)Anikmar быть не может? это закон природы такой, да?   


вы видели вариант mes'а, но видимо не прониклись

Добавлено через 47 секунд

мы не злые, мы мудрые

А если конец списка ссылается на начало? Быстрый итератор будет равен первому элементу, а медленный в середине где-то? Разве равенство сработает?


Второй раз случайно может быть, но это обнаружимо. В любом случае, я вижу только мой первый вариант как 100% 

Все проникся - все равно догонит.


Мудрые к стенке не ставят. Мудрые доводят до самоубийства.    

Это сообщение отредактировал(а) Anikmar - 13.4.2009, 09:45

Цитата(Anikmar @  13.4.2009,  06:30 )

Вашего варианта я же не видел - может он лучше, я бы свои не предлагал.

Предложенный мной вариант, был услышан некоторое время назад от Joker.   


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

Так для случая отн. большой петли (если быстрый до места встречи успел пройти по петле только раз) 
L=2*O-S , 
где L - длина от начала , до конца (до стыка который надо востанавливать)
      О-длина петли
      S-кол-во шагов медленного.

Для остальной части задачи надо мозги напрячь.. попозже попробую.. 
  

имхо покрасить каждый элемент при простом проходе, если попали на покрашенное - значит кольцо есть.

 если только список предполагал возможность окрашивания +  надо как то убедиться что список нигде не подкрашен.
  

Да. Этот вариант мне больше нравится.


И вернулись к изначальному вопросу  

и в чем проблема создать map<void*, isColored> подобную структуру при обходе? не вижу никаких проблем.

jonie, Да. Спасибо. Вопрос решен.

а как узнать длину списка если он закольцован ?
a если проверять есть ли в списке уже указатель, то зачем параметр isColored ?

mes, Вы правы! Начал реализовывать, и уперся    
И так. Дисскусия продолжаеться.  

а чем не устраивает способ, где  
?

mes, Туплю по ходу   Не могу понять что и как...  

вот набросок (работоспособность не проверял):

расстояние от точки встречи итераторов до точки пересечения всегда равно остатку от деления куска до пересечения на длину кольца
т.е. простейший вариант пустить два "медленных" итератора - один из точки встречи, другой с начала списка - они встретятся в точке пересечения

нда..самое эффективное решение как всегда лежит на поверхности 
J0ker,   

не вижу проблем при простом однонаправленном проходе с головы в хвост с сохранением метки "я тут был". В чем проблема-то?

нечто вроде:



Это сообщение отредактировал(а) jonie - 14.4.2009, 09:21

если Вы каждую элемент добавляете в карту, то 

а без него решение превращается в :

и требует наличие некого дополнительного объема памяти
и также кол-во операций сравнения получается выше, чем у способа с двумя итераторами.

ну вот и вопрос, зачем использовать заведомо медленный и не эффективный способ,  строить дополнительные механизмы, 
 когда все решается простым (двух-итераторным) обходом списка ?

аа , я думал вы нашли там баг фатальный)

andrew_121, ты покажи ф-цию вывода элементов списка, а потом можно будет говорить. Ты же выводишь элементы каким-то образом? Как ты это делаешь? По кругу или нет? 

Прежде чем выводить, тс. надо проверить не поврежден ли список, иначе прога войдет в бесконечный цикл   

можно сохранить prev и next в prevsave и nextsave и, продвигаясь по списку, проверять next на NULL и prevsave, а prev на NULL и nextsave

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


Добавлено @ 00:33
двусвязный список может быть корректно закольцован только если хвост указывает на голову и наоборот
все остальные случаи подпадают под термин "сломан"

Это сообщение отредактировал(а) J0ker - 15.4.2009, 00:43

  

Все остальные случаи должны корректно обрабатываться. Вот над этим и бьюсь сейчас. Нужно что-то вроди отчета, который потом(возможно однажды) придется использовать для "ремонта" списка.

Это сообщение отредактировал(а) inside_pointer - 15.4.2009, 11:58

а где проверка, что cur->next не ноль ?!

я в процессе ещё 

а зачем их делать членами класса ?

mes, вопрос, ведь, не в этом. Не хочешь - не делай. Это просто иллюстрация, примерчик, так сказать. Показано, как проверить и всё. Дальше, пусть человек сам думает.

Добавлено через 3 минуты и 19 секунд
там нужна ещё проверка "в обратную сторону", аналогичная этой..

  

Я так понимаю, это чтобы в консоли русский текст корректно отображался.
Однако я встречал ещё два аналогичных варианта:
1) setlocale(LC_ALL, "");
2) setlocale(LC_ALL, "Russian");

Интересно, сколько их всего... 


Это сообщение отредактировал(а) zim22 - 15.4.2009, 13:47

не хочу.. просто испугало.. представил, что эти строчки воспримут как руководство к действию.   

гы-гы....
mes, зачем же о людях так думать?   


zim22, не знаю.  На моём компе если так не сделать, то будет на иврите выводить...   

да после соседней темы с  **(char *)&string еще и не такие ужасы привидятся..      



Это сообщение отредактировал(а) mes - 15.4.2009, 14:17

  

Это что?  

извращение в чистом виде