Страниц: [1]
  Печать  
Автор Тема: Жизнь заставит  (Прочитано 5134 раз)
oder
Гость
« : Февраля 16, 2011, 05:55:56 pm »

Оказывается, для коллекции объектов возможно создать очередь (для их обработки) в виде односвязного списка так, чтоб (і) каждый элемент списка содержал указатель на объект коллекции (иначе, какая от этого элемента польза?!), (іі) каждый объект коллекции имел указатель на свой элемент в списке и мог, используя этот указатель, удалять элемент из списка (чтоб отменить обработку или перевставить обработку в конец очереди).

Тренируйтесь! Wink

P.S. Кто не понял: суть проблемы здесь в том, що нет возможности найти указатель на предыдущий элемент списка, чтоб выбросить свой. Wink
P.P.S. Поиск с начала очереди не предлагать!
Записан
vshemm
Sr. Member
****
Offline Offline

Сообщений: 317


Просмотр профиля
« Ответ #1 : Февраля 17, 2011, 09:08:27 pm »

Что-то вы не договариваете Wink

Указатель на предыдущий элемент списка все равно придется искать (иначе поменяется порядок элементов списка),
а сделать это можно при данных условиях за О(n).
Либо использовать инкапсуляцию и в итераторе хранить указатель на предыдущий элемент списка прозрачно для пользователя.
Записан
oder
Гость
« Ответ #2 : Февраля 17, 2011, 09:18:15 pm »

Ну, конечно, что недоговариваю. Wink Иначе о чём тут думать было бы? Smiley
Понятное дело, что указатели указывают на список не прямо и непосредственно, как в школе учат. Они, как и данные, некоторым образом перетасованы, чтоб достичь поставленной цели. Но, в конечном счёте, у каждого объекта указатель только один и список, таки, остаётся односвязным.
Записан
vshemm
Sr. Member
****
Offline Offline

Сообщений: 317


Просмотр профиля
« Ответ #3 : Февраля 17, 2011, 09:42:12 pm »

Ну, тогда это не указатели на элементы списка, а итераторы в терминах generic-программирования.
И обращаться напрямую по ним нельзя (либо, если язык поддерживает инкапусляцию, можно... например,
в С++ это потребует перегрузки кучи операторов и т.д.). Суть в том, что итератор будет хранить
указатель не на текущий элемент списка, а на предыдущий, и при выборке возвращать, грубо говоря, p->next.
Вставка-удаление тогда будут выполняться за О(1).

Или эталонное решение все-таки основано на копировании хеда? Smiley
Записан
oder
Гость
« Ответ #4 : Февраля 17, 2011, 09:53:50 pm »

Не знаю, какая там инкапсуляция, но у меня код на простом C и никаких итераторов там не наблюдается. И данные хранятся именно в том элементе, на который указатель указывает. А если бы и хранились в другом, то никаких O(1) это бы не повлекло потому, что самому объекту данные (тоесть, указатель на себя самого) не нужны. А данные извлекаются только потоком-обработчиком из головы "в порядке живой очереди". Wink

И вообще, математика учит, что O(1) = O(0).  Tongue  Wink
Записан
vshemm
Sr. Member
****
Offline Offline

Сообщений: 317


Просмотр профиля
« Ответ #5 : Февраля 17, 2011, 10:05:38 pm »

Ок, Си так Си. Хотя итераторы и там можно реализовать Smiley
Все-таки лично мне не очень ясен пойнт этой задачи, много приходится додумывать.
Поэтому, дабы не обламывать других читателей, скину в личку конкретное решение Wink
Записан
oder
Гость
« Ответ #6 : Февраля 18, 2011, 02:53:58 pm »

Первый правильный ответ получен от участника Hed.
Записан
Страниц: [1]
  Печать  
 
Перейти в: