Здравствуйте, Жмур, Вы писали:


Ж>Задача: найти этот последний элемент структуры. Копировать структуры нельзя,
Ж>применять дополнительные средства, типа создать карту элементов, чтобы потом
Ж>проверить повторно встречающийся элемент, нельзя.

Ж>Оформить это нужно не в виде языка, а показать на пальцах.

Ну если на пальцах, то вот более рациональное и соответсвующее условию, имхо, решение, чем то что приводил Flamer. Его решение находит только закольцован список или нет. Потом еще дополнительно нужно будет искать последний элемент.

Я опущу проверку на закольцованость, которую добавить не трудно (понадобятся: память на хранение адреса первого элемента и пара if-ов), тем более что в условии ясно сказано что список закольцован. Сделаем так: будем идти по списку и менять направление ссылок на обратное, при этом первый элемент сошлем на "нулевой". При этом будем вести счетчик пройденых элементов списка.

То есть, если начальный список будет такой:

a -> b -> c -> d -> e -> f -> c

То после нескольких итераций он станет таким(при этом мы сейчас рассматриваем пару элементов d-e):

a <- b <- c <- d -> e -> f -> c

Дойдя до "конца" списка получим:

a <- b <- c <- d <- e <- f -> c

После чего продолжаем идти по ссылкам и менять их на "противоположные". Дойдя до начала(то есть элемента который ссылается на "нулевой элемент") мы получим такую структуру:

a -> b -> c <- d <- e <- f <- c

Вот тут, кстати говоря, и нужно, если что сделать проверку на закольцованость: достаточно сравнить адреса пары элементов: ссылющегося на "нулевой" элемент и начального, сохраненного нами в самом начале. Если совпадают — закольцован, нет — линеен.
Заметим, что после данного прохода в счетчике мы получили некое число, которое, если разобратся, равно 2k+p, где p-кол-во элементов в цикле, а к-кол-во элементов не входящих в цикл. Обозначим его C(count). После этого пройдем по списку C шагов не меняя ничего. При этом мы окажемся где-то внутри цикла. После этого нам осталось запомнить адрес текужего элемента и пройтись полностью по циклу — до попадания на этот же элемент, при этом подсчитывая шаги в новом счетчике. Мы получили p. Теперь совсем не сложно вычислить k=(c-p)/2. Теперь мы знаем номер элемента(если считать от начала), который "начинает" список. Также у нас есть адрес первого элемента — так что найти нужный нам элемент труда не состовляет.

Вот и все. На все про все понадобилось 2*(2*k+p)+p шагов, а также несколько дополнительных байт памяти.

Здравствуйте, Жмур, Вы писали:

[skip]
Это делается помоему так:

1)Берем 1-й элемент смотрим валидна ли ссылка 1-го элемента.
2)Если связь валидна то сохраняем 1-й элемент в качестве последнего елемента с валидной сслыкой.
3)Переходим к элементу на который ссылается 1-й элемент
4)и рвем связь между 1-м элементом и тем на который перешли.
5)Далее проделываем тоже самое с элементом на который перешли.
6)Делаем 1-5 до тех пор пока не окажется, что текущий элемент никуда не ссылается.
7)По выходу из цикла мы будем иметь последный(искомый) элемент, как последний элемент, который на что-то
ссылался.

Вот он то и будет искомым

Здравствуйте, Jakop, Вы писали:

J>Здравствуйте, Жмур, Вы писали:

J>[skip]
J>Это делается помоему так:

J>1)Берем 1-й элемент смотрим валидна ли ссылка 1-го элемента.
J>2)Если связь валидна то сохраняем 1-й элемент в качестве последнего елемента с валидной сслыкой.
J>3)Переходим к элементу на который ссылается 1-й элемент
J>4)и рвем связь между 1-м элементом и тем на который перешли.
J>5)Далее проделываем тоже самое с элементом на который перешли.
J>6)Делаем 1-5 до тех пор пока не окажется, что текущий элемент никуда не ссылается.
J>7)По выходу из цикла мы будем иметь последный(искомый) элемент, как последний элемент, который на что-то
J>ссылался.

J>Вот он то и будет искомым

Кстати предупреждая недовольные высказывания типа "Да он же портит список... " итд
хочу сказать ,что
1)в условии задачи сказано всегда ровно то что требуется сделать,
2)теми средствами , которыми это можно сделать и с
3)теми ограничениями которые налагаются на решение.
Не больше не меньше.

Здравствуйте, Jakop, Вы писали:

J>Здравствуйте, Жмур, Вы писали:

J>[skip]
J>Это делается помоему так:

J>1)Берем 1-й элемент смотрим валидна ли ссылка 1-го элемента.
J>2)Если связь валидна то сохраняем 1-й элемент в качестве последнего елемента с валидной сслыкой.
J>3)Переходим к элементу на который ссылается 1-й элемент
J>4)и рвем связь между 1-м элементом и тем на который перешли.
J>5)Далее проделываем тоже самое с элементом на который перешли.
J>6)Делаем 1-5 до тех пор пока не окажется, что текущий элемент никуда не ссылается.
J>7)По выходу из цикла мы будем иметь последный(искомый) элемент, как последний элемент, который на что-то
J>ссылался.

J>Вот он то и будет искомым

Да вот еще....для того, чтобы определить закольцовал ли список нужно просто проверить ссылается ли текущий елемент на чтонибудь. И если не ссылается — то список не закольцован выходим из цикла.

A>> Встаём в начало списка. Начинаем по нему бежать, записывая в массив адреса того, что нашли по дороге.
A>> На каждом жаге проверяем, нет ли в массиве совпадающих адресов.
A>> Если есть — алгоритм окончен и на предыдущем шаге нам попался тот самый последний эл-т.

Ж>Вот примерно-такой же родил и я — ну как после ещё дополнительно оказалось
Ж>оказалось, что при поиске нельзя использовать никакой вектор для слежения
Ж>(вообще дополнительно выделать память на какую либо структуру).

A>> То же самое можно сделать и без массива.

Ж>Мона подробнее?

Вместо дополнительного массива использовать этот же самый список.

Ж>B всё это должно быть очень эффективно.

А это вообще демагогия.

Здравствуйте, Жмур, Вы писали:

Ж> Чесслово не вру, без преукраски. Очень солидная
Ж>фирма. Гы-гы.

Что за контора?