ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Проверка на зацикленность
7 сообщений из 7, страница 1 из 1
Проверка на зацикленность
    #36265936
Naf
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Naf
Участник
Есть класс Item, у него поле/свойство Next - ссылка на объект того же типа Item. То есть имеем связанный список, если у очередного элемента Next=null, то это конец списка.
На входе объект A класса Item, на выходе ответ, есть ли у списка, начинающегося с элемента A, конец или нет, то есть проверка на зацикленность. Интересует наиболее оптимальное решение.
...
Рейтинг: 0 / 0
22.10.2009, 09:11:37
| Ответить | Цитировать | Написать  
Проверка на зацикленность
    #36265985
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
отмечать все элементы, которые уже прошли.
петля я понимаю может быть любой - хоть "Ъ"

4 8 15 16 23 42
...
Рейтинг: 0 / 0
22.10.2009, 09:39:41
| Ответить | Цитировать | Написать  
Проверка на зацикленность
    #36265996
Vowk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Vowk
Участник
Я так полагаю, что потребуется память, способная запомнить ссылки на все объекты, потому что зацикливание может произойти где угодно и куда угодно. Если их можно упорядочить как-то (по адресу, например), то проверка на присутствие в списке такой ссылки будет быстрой, а если нет - тогда с каждой новой ссылкой придется просматривать весь список.
...
Рейтинг: 0 / 0
22.10.2009, 09:45:03
| Ответить | Цитировать | Написать  
Проверка на зацикленность
    #36266003
Naf
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Naf
Участник
Aklinотмечать все элементы, которые уже прошли.
петля я понимаю может быть любой - хоть "Ъ"
да, петля произвольная, отмечать внутри объекта не получится, у него нет свойства/поля такого
у меня получился двойной цикл
...
Рейтинг: 0 / 0
22.10.2009, 09:48:51
| Ответить | Цитировать | Написать  
Проверка на зацикленность
    #36266385
AIS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AIS
Участник
Может это и не к месту, но приведу такой пример:
Есть дерево и все его элементы в одной таблице.
Создавая новую ветку, создаем массив из Parent-ов этой ветки подымаясь вверх до 0 (корень).
Далее тестируем связь новой ветки (т.е. в вашем случае Next) на вхождение в этот массив.
Если входит, то цикл. Если нет, то ветку можно создавать.
...
Рейтинг: 0 / 0
22.10.2009, 11:46:01
| Ответить | Цитировать | Написать  
Проверка на зацикленность
    #36267184
donky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
donky
Гость
Naf,

Оптимальное по чему? По скорости или по памяти?

Если по скорости, то дополнительная хэш таблица, в котрой будут храниться все посещенные объекты.
Если по памяти, то есть классический алгоритм, когда по списку пускаем 2 указателя, один за шаг переходит на 1 элемент вперед, 2-й - на 2 элемента вперед. При проходе 2-м проверяем, если он указывает на тот-же объект, что и первый - значит цикл есть.
...
Рейтинг: 0 / 0
22.10.2009, 15:23:07
| Ответить | Цитировать | Написать  
Проверка на зацикленность
    #36267259
Naf
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Naf
Участник
donkyNaf,

Оптимальное по чему? По скорости или по памяти?

Если по скорости, то дополнительная хэш таблица, в котрой будут храниться все посещенные объекты.
Если по памяти, то есть классический алгоритм, когда по списку пускаем 2 указателя, один за шаг переходит на 1 элемент вперед, 2-й - на 2 элемента вперед. При проходе 2-м проверяем, если он указывает на тот-же объект, что и первый - значит цикл есть.
точно
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
class Item
    {
        public Item Next { get; set;}
        public bool HasLoop()
        {
            Item c = this;
            Item f = c.Next;
            while (c != null && f != null && f.Next != null)
            {
                c = c.Next;
                f = f.Next.Next;
                if (c == f) return true; 
            }
            return false;
        }
    }
...
Рейтинг: 0 / 0
22.10.2009, 15:41:30
| Ответить | Цитировать | Написать  
7 сообщений из 7, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Проверка на зацикленность
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&tid=1344159]:
 0ms
get settings:
 11ms
get forum list:
 21ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 226ms
get topic data:
 11ms
get forum data:
 2ms
get page messages:
 55ms
get tp. blocked users:
 1ms
others: 232ms
total:  567ms
созд. / загр.: 567ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]