алгоритмическая задачка

[Sherman]

2Adelf

Да ты прав. Пришлось попотеть:

http://hpaste.org/fastcgi/hpaste.fcgi/view?id=23121#a23121

p.s. Все еще интересен вариант на си.

 

[phprus]

Sherman

p.s. Все еще интересен вариант на си.

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

 

[Sherman]

2phprus
Почему сразу не понимаю, может быть существуют и другие варианты решения, было бы интересно увидеть. Пусть даже и с непереносимыми хаками ;-)

 

[Adelf]

Sherman
Ну фактически из твоего варианта получается и правильный. просто некоторые указатели временно "перемещаются" в исходный список(а потом восстанавливаются).

-~{}~ 01.03.10 17:34:

Никаких шаманств на Си я вчера так и не смог придумать думал массив как-то поможет, но не особо.

-~{}~ 01.03.10 17:38:

ггг ) Посмотрел новый твой вариант. Опять ты там химичишь нечестно В сумме опять памяти на два списка выделаешь. Хоть и удаляешь там, но в итоге в сумме памяти выделено на два.
Для правильного решения данной задачи надо временно править исходный список.

 

[Sherman]

2Adelf

Дык так оно и есть.
Expand вставляет в текущий список элементы(n). Получается цепочка: original -> random -> original -> ...

Далее, проставляются правильные значения для random.

И затем разделение списков. Метод addItem в split не создает новый элемент.

 

[Adelf]

Sherman
Да ты прав. Все отлично там.
Кстати можно уже немного переработать и tale выкинуть
И вообще классически данные списки представляются в программе лишь одной вещью - ссылкой на head.

 

[Sherman]

2Adelf

Классически, никто уже с односвязными списками не работает(кроме студентов) ;-)
Везде двухсвязный список и часто закольцованный. На основе него очень легко сделать queue, stack, deque.

 

[Adelf]

Sherman
Ну ты еще скажи что задача эта из реальной жизни

 

[Sherman]

2Adelf

Ну в реальной жизни такой код врядли имел бы право на существование в продакшин, потому что он не thread safe и не exception safe.

 

[Жигaн]

Sherman
Вот вариант в стиле С
http://hpaste.org/fastcgi/hpaste.fcgi/view?id=23134#a23134

 

[Sherman]

Заработало

2Жиган
А можешь пояснить строчку list_item* orig_rand(list->rand);
Что в ней происходит?

 

[Жигaн]

Это вызов конструктора копирования. В данном случае равнозначно с
list_item* orig_rand = list->rand;

 

[Adelf]

Раз уж пошли вопросы не совсем по теме:
Sherman
final ListItem<T> tmp = curr.next;

final здесь для чего?

 

[Sherman]

2Adelf

Исключительно для выразительности кода. Никакой специальной функции оно не несет.

 

[fixxxer]

>>Пусть даже и с непереносимыми хаками ;-)

В задачке про определение закольцованности списка antoxa предлагал юзать в качестве маркера младший бит самого указателя, пользуясь тем, что адреса на всех современных платформах выравниваются

 

[cDLEON]

в качестве маркера младший бит самого указателя, пользуясь тем, что адреса на всех современных платформах выравниваются

Можно где-нибудь почитать это предложение? Не совсем понятно как взаимосвязано выравнивание адреса и младший бит...

 

[phprus]

cDLEON

Не совсем понятно как взаимосвязано выравнивание адреса и младший бит...

Нечетных адресов начала блоков памяти не бывает в случае выравненных объектов, если выравнивание идет больше чем на 1 байт (а выравнивание на 1 байт равнозначно его отсутствию).

fixxxer
Для определения закольцованности списка достаточно двух указателей, которые двигаются с разной скоростью (второй в два раза быстрее первого) и если быстрый догонит медленный, тогда в списке есть кольцо.
Помоему это решение красивее чем решение с хаком указателей.

 

[Alexandre]

хотя, если оно в непрерывном фрагменте памяти, то все решается в один проход.

в два:
первым проходом определяем кол-во элементов списка,
дале выделяем область памяти sizeof(list_item) * n
вторым проходом по байтно переписываем список, с инкрементом данных на разницу адресов first_0 - first_1

но факт, что все элементы списка лежат в непрерывном фрагменте памяти.

том решении память выделяется не дополнительно, а под новый список

согласен, но тот новый список является совершенно другой структурой.

-~{}~ 02.03.10 15:16:

не все ответы еще просмотрел, но обзательно просмотрю.

 

[fixxxer]

phprus
зато с хаком эффективнее. )

 

[phprus]

fixxxer
Думаю это зависит от того, необходимо ли восстанавливать указатели после того как определили наличие отсутствия цикла.
В таком случае нам понадобится второй проход и тогда ресурсоемкости сравняются. Или даже в таком случае хак даст преимущество (если да, то почему)?