Встречалась мне такая задачка, даже знал когда-то ответ да забыл. Вот сейчас хочется совместно со всеми вспомнить -
Условия проще некуда - Определить зацикливается ли однонаправленный список. Понятно, что не методом сравнивания каждого нового элемента со всеми предыдущими.
А где конец?
Уточните, плиз, условия зацикливания однонаправленного списка.
Устовие простое, если указатель на следующий элемент у одного из элеметнов указывает на элемент который был перед ним. т.е.laura писал(а):Уточните, плиз, условия зацикливания однонаправленного списка.
A->B
B->C
C->D
D->E
E->C // зацикливание
если нету нумерации то ИМХО никак кроме сравнения....
Нет бога, кроме процессора и ассемблер - пророк его.
Если указатель любого элемента списка _обязательно_ указывает на какой-либо элемент этого списка, то зацикливание будет всегда. Или список бесконечный.
Если отталкиваться от этого утверждения, то надо всеголишь найти элемент у которого указатель будет равен NULL или определить, что такого элемента нет. В случае если список не зациклен, то это легко, а вот наоборот ? Ты будешь вечно по списку бегатьchur писал(а):Если указатель любого элемента списка _обязательно_ указывает на какой-либо элемент этого списка, то зацикливание будет всегда. Или список бесконечный.
Элементарно: запомнить указатель на первый (или на любой другой) элемент и, пробегая список, сравнивать с ним указатель на текущий элемент. Заметь - не со всеми сравнивать, а только с однимОпределить зацикливается ли однонаправленный список. Понятно, что не методом сравнивания каждого нового элемента со всеми предыдущими.
Если указатели совпали - список зациклен. Но если длина списка не ограничена, то и поиск может быть таким же. Правда, я с трудом представляю себе бесконечный зацикленный список В приведнном мною примере, запомнили мы например указатель "A" и побежали по списку. Больше на "A" мы никогда не попадем а список всеравно зацикленный навечно
Пардон, я имел в виду случай полного цикла. А помечать пройденные элементы никак нельзя (типа флажок ставить - 'здесь был вася')?
Да нет, это было бы слишком просто