Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Задача о связанном списке

Автор: Dark Elf 20.4.2009, 13:54

Добрый день

Есть следующая задача:

1. Имеется связанный список с неизвестным нам количеством элементов.
2. У каждого элемента списка имеется метод Next
3. Элементы этого списка могут ссылаться друг на друга в произвольном порядке.
4. Последний элемент этого списка равен NULL
5. ID элемента определять по каким-то причинам нельзя

Вопрос состоит в следующем:

Как найти последний элемент?

(Сильно подозреваю что ответ простой но не могу понять как решать)

Автор: nworm 20.4.2009, 16:40

Это шутка?

Цитата

4. Последний элемент этого списка равен NULL

Цитата

Как найти последний элемент?

Код


printf("NULL");

Автор: azesmcar 20.4.2009, 16:44

nworm

Скорее всего автор хотел сказать что Next последнего элемента равен 0.

Dark Elf
А в чем задача то?

Код


while ( node->next )
{
   node = node->next;
}

//нашли node

Автор: Earnest 20.4.2009, 19:29

Действительно, либо связанный список, и тогда все элементы доступны по-порядку (какая разница, в каком).
Либо не связанный или не список.
В первом случае задача тривиальна, а во втором - просто не сформулирована.

Автор: Dark Elf 20.4.2009, 22:56

Цитата(Dark Elf @ 20.4.2009, 13:54)

3. Элементы этого списка могут ссылаться друг на друга в произвольном порядке.

То есть например "4-й" (условно) элемент может ссылать снова на "2-й" (условно) элемент.
Так мне сформулировали задачу.

Автор: ksnk 20.4.2009, 23:05

Dark Elf, Что такое 2 и 4-й элемент? Второй и четвертый, если идти по NEXT от начала списка? тогда это цикл - нарушение NULL'а в конце...

Автор: azesmcar 20.4.2009, 23:14

Dark Elf

Что-то я не пойму о чем речь. Список либо конечный, либо циклический..
если конечный - тогда решение которое я написал, если циклический то это не решается ..т.е. решится если его исправить.

Цитата

То есть например "4-й" (условно) элемент может ссылать снова на "2-й" (условно) элемент.

в списке нет индексов, если
"4-й" (условно) элемент может ссылать снова на "2-й"
то это не 2-й а 5-ый smile

Автор: Earnest 21.4.2009, 10:03

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