Страницы

Поиск по вопросам

пятница, 27 декабря 2019 г.

Поиск зацикленности в списке

#c_sharp #алгоритм #net


Допустим, есть список или массив, мы берём определённый его элемент, необходимо знать,
не ссылается ли он на другой элемент из этого списка, то есть нет ли зацикленности.
(Самый очевидный ответ - перебор с помощью цикла - не подходит, так как длина списка
может быть очень велика. Этот вопрос задали на собеседовании.) Буду признателен за
код (например, на C#).    


Ответы

Ответ 1



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

Ответ 2



Массив в принципе не может быть зациклен. Вы курите! Список можно проверить ТОЛЬКО пробежав его до конца и проверив нет ли ссылки на какой нибудь элемент этого списка. Как вариант еще можно попробовать хранить количество элементов в списке и попробовать просто пробежать его и если вы вышли за размер - он зациклен. Могу только предположить, что если у вас каким то образом так оказалось, что вся куча у вас в стеке, то можно искать ссылки на элементы списка. Если у любого из элементов более 1 ссылки то возможно зациклен. Еще есть вариант если у вас двусвязный список - пытаться пройти на встречу.

Комментариев нет:

Отправить комментарий