Developing.ru

Встречалась мне такая задачка, даже знал когда-то ответ да забыл. Вот сейчас хочется совместно со всеми вспомнить -
Условия проще некуда - Определить зацикливается ли однонаправленный список. Понятно, что не методом сравнивания каждого нового элемента со всеми предыдущими.

Уточните, плиз, условия зацикливания однонаправленного списка.

laura писал(а):Уточните, плиз, условия зацикливания однонаправленного списка.

Устовие простое, если указатель на следующий элемент у одного из элеметнов указывает на элемент который был перед ним. т.е.

A->B
B->C
C->D
D->E
E->C // зацикливание

если нету нумерации то ИМХО никак кроме сравнения....

Если указатель любого элемента списка _обязательно_ указывает на какой-либо элемент этого списка, то зацикливание будет всегда. Или список бесконечный.

chur писал(а):Если указатель любого элемента списка _обязательно_ указывает на какой-либо элемент этого списка, то зацикливание будет всегда. Или список бесконечный.

Если отталкиваться от этого утверждения, то надо всеголишь найти элемент у которого указатель будет равен NULL или определить, что такого элемента нет. В случае если список не зациклен, то это легко, а вот наоборот ? Ты будешь вечно по списку бегать

Определить зацикливается ли однонаправленный список. Понятно, что не методом сравнивания каждого нового элемента со всеми предыдущими.

Элементарно: запомнить указатель на первый (или на любой другой) элемент и, пробегая список, сравнивать с ним указатель на текущий элемент. Заметь - не со всеми сравнивать, а только с одним Если указатели совпали - список зациклен. Но если длина списка не ограничена, то и поиск может быть таким же. Правда, я с трудом представляю себе бесконечный зацикленный список

В приведнном мною примере, запомнили мы например указатель "A" и побежали по списку. Больше на "A" мы никогда не попадем а список всеравно зацикленный навечно

Пардон, я имел в виду случай полного цикла. А помечать пройденные элементы никак нельзя (типа флажок ставить - 'здесь был вася')?

Да нет, это было бы слишком просто