OberonCore
https://forum.oberoncore.ru/

Добавление в конец списка
https://forum.oberoncore.ru/viewtopic.php?f=35&t=2825
Страница 1 из 1

Автор:  Илья Ермаков [ Понедельник, 06 Сентябрь, 2010 21:58 ]
Заголовок сообщения:  Добавление в конец списка

Что-то давненько не приходилось работать со списком, когда добавлять надо в конец.
Разбаловался системщиной, где один указатель - и добавление в голову :))

Так вот, кажется громоздким IF, проверяющий при добавлении список на непустоту.

Разумно принять, что первый элемент списка - фиктивный, пустой.

Например:

Код:
   TYPE
      Word = POINTER TO RECORD
         next: Word;
         ...
      END;

      WordList = RECORD
         dummy, last: Word
      END;


Тогда при создании списка:
NEW(list.dummy); list.last := list.dummy;
а при добавлении очередного элемента:
list.last.next := new; list.last := new;

Ну а голова списка - list.dummy.next.
Проверка на пустоту: list.last = list.dummy.

Автор:  Info21 [ Понедельник, 06 Сентябрь, 2010 23:22 ]
Заголовок сообщения:  Re: Добавление в конец списка

В смысле?

Автор:  Александр Ильин [ Вторник, 07 Сентябрь, 2010 09:15 ]
Заголовок сообщения:  Re: Добавление в конец списка

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

Интересно, не появится ли проблем или противоречий, если в языке разрешить следующее присваивание с охраной типа:
dest := source (DestType);
при source = NIL? В таком случае присваивание эквивалентно "dest := NIL", но Оберон выдаёт трап при попытке проверить тип sourcre.

Автор:  Сергей Губанов [ Вторник, 07 Сентябрь, 2010 11:11 ]
Заголовок сообщения:  Re: Добавление в конец списка

Александр Ильин писал(а):
Интересно, не появится ли проблем или противоречий
Тогда явная проверка на NIL заменится на скрытую от программиста. В Виртовской Школе считается, что компилятор должен выполнять лишь такие действия, которые сам программист сделать не может. Проверить указатель на NIL программист может и сам, если захочет.

Автор:  Илья Ермаков [ Вторник, 07 Сентябрь, 2010 14:50 ]
Заголовок сообщения:  Re: Добавление в конец списка

Info21 писал(а):
В смысле?


Ну, если у нас список - first и last, то при добавлении:

IF last # NIL THEN
last.next := new; last := new
ELSE
first := new; last := new
END

(На эту громоздкость и Вирт в книге жалуется, типа "удобнее в начало списка").

А если у меня наполнение списка идёт много где - да, например, в цикле - не одного, а нескольких списков.. То этот IF становится поперёк...

Кстати, если список наполняется единожды, а потом передаётся как есть, то передавать стоит просто указатель на элемент. (В моём примере функции у меня возвращают Word, но внутри, в порождающих циклах, работают с WordList).

Автор:  Info21 [ Вторник, 07 Сентябрь, 2010 15:57 ]
Заголовок сообщения:  Re: Добавление в конец списка

Используем "барьер" (sentinel) -- и что?
Чётто не понимаю пафоса.
Ну и ладно.

Автор:  Илья Ермаков [ Вторник, 07 Сентябрь, 2010 16:06 ]
Заголовок сообщения:  Re: Добавление в конец списка

Не, барьер - это в конце, и инициализируемый перед обработкой. А тут - фиктивный элемент в начале, чтобы проверки на NIL избежать. Ну да, полностью аналогично sentinel, но наоборот.

И пафоса нет. Просто поделился нюансом.

Автор:  Info21 [ Вторник, 07 Сентябрь, 2010 18:15 ]
Заголовок сообщения:  Re: Добавление в конец списка

Илья Ермаков писал(а):
Не, барьер - это в конце
Один хрен.

Пафоса оказалось достаточно, чтобы начать тему.

Просто любопытно.

Автор:  Валерий Лаптев [ Вторник, 07 Сентябрь, 2010 19:37 ]
Заголовок сообщения:  Re: Добавление в конец списка

Илья Ермаков писал(а):
Что-то давненько не приходилось работать со списком, когда добавлять надо в конец.
Разбаловался системщиной, где один указатель - и добавление в голову :))

Так вот, кажется громоздким IF, проверяющий при добавлении список на непустоту.

Разумно принять, что первый элемент списка - фиктивный, пустой.
Тогда при создании списка:
NEW(list.dummy); list.last := list.dummy;
а при добавлении очередного элемента:
list.last.next := new; list.last := new;

Ну а голова списка - list.dummy.next.
Проверка на пустоту: list.last = list.dummy.

Дык это обычная практика в STL. Я всегда так делаю... :)

Страница 1 из 1 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/