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/ |