не, при некоторых предположениях, которые почти всегда верны на современных архитектурах, можно впихнуть в структуру флаг "мы тут уже были" и его просто проверять и всех дел
Ну собственно с PHP я уже полгода не работал, в основном с Java... Просвети fixxxer, что чём ты говорил имея ввиду делегирование?Автор оригинала: fixxxer
ясно все с тобой. тебя бы я не взял на работу
Такого патерна не знаю, либо его нет вообще, либо он называется иначе (полагаю стратегия), либо дайте ссылку на него.
Гы) Если перефразировать задачу на Си, то получится следующее.
typedef struct List List;
int is_cyclic(List *list);struct List {
/* foo struct members */
struct List *next;
/* bar struct members */
};int is_cyclic(List *list) {
List *first = list;
if (list == NULL) return 0;
for (list = list->next; list != NULL; list = list->next) {
if (first == list) {
/* обнаружен цикл */
return 1;
}
}
/* напоролись на NULL, т.е. цикла нет */
return 0;
}
MSITStore:C:\php_manual_ru.chm::/ru/language.operators.logical.html
int is_cyclic(List *list) {
List *first = list;
int depth = 1; /* глубина поиска цикла */
if (list == NULL) return 0;
for (;;) {
for (int i = 0; i < depth; i++) {
list = list->next;
if (list == NULL) {
/* напоролись на NULL -> конец списка, т.е. цикла нет */
return 0;
}
if (list == first) {
/* обнаружен цикл */
return 1;
}
}
/* увеличиваем глубину поиска одновременно с
* продвижением в глубину списка */
depth++;
first = first->next;
list = first;
}
/* цикл for (;;) завершится в любом случае выходом из функции */
}
это решение имеет сложность O(n^2) если вы заметили.Автор оригинала: valyala
я вот тут подумал - а ведь цикл не обязательно должен выглядеть так:
1 -> 2 -> .... n -> 1
Он может выглядеть и так:
1 -> 2 -> ... -> m -> ... -> n -> m
Тогда алгоритм is_cyclic() немного усложняется и не вкладывается в поставленные ограничения - кроме памяти, необходимой для указателей list и first, в стеке используется дополнительная память для переменных depth и i... Так что алгоритм только на троечку
Код:int is_cyclic(List *list) { [порезано] }
ввиду перечисленных выше замечаний привожу решение со сложностью O(n), написанное на ПХП:
bool is_cyclic($list)
{
if ($first == null) return false;
$depth = 1;
for (;;) {
$first = $list;
for ($i = 0; $i < $depth; $i++) {
$list = $list->next;
if ($list == null) return false;
if ($list == $first) return true;
}
$depth += $depth;
}
}