Д. Кнут - Искусство программирования том 1 (1119450), страница 78
Текст из файла (страница 78)
Именно поэтому представление списка в виде (2) предпочтительнее, чем в виде (1). Дважды связанный список обычно занимает гораздо больше места в памяти, чем однократно связанный список (хотя в узле, который не заполняет полностью слово в памяти компьютера, иногда остается свободное место для другой связи).
Но дополнительные операции, которые могут очень эффективно выполняться с дважды связанными списками, часто являются более чем достаточной компенсацией за дополнительные затраты на память. Помимо очевидного преимущества, связанного с легкостью перехода либо назад, либо вперед вдоль дважды связанного списка, одной из наиболее принципиальных новинок является возможность удаления узла МООЕ(Х) пз списка, если известно только значение Х. Эту операцию довольно легко вывести иа основании схемы <состояния "дое и ипослееъ (рис.
11): КЕ1МК(1.ь1МК(Х)) +- йь1МК(Х), 1Л.1МК(В1,1МК(Х)) е- Е~.1МК(Х) (4) АЧА11. ~ Х. Перед удалением Рнс. 11. Удаление узла из дважды связанного списка. После удаления й АЧА1Е Так же просто в дважды связанный список можно вставить узел слева или справа от заданного узла МООЕ(Х). Например, для вставки узла справа от узла МОВЕ(Х) необходимо выполнить такие действия: Р е= АУА1Е, ЕЕ1МК(Р) +- Х, КЕ1МК(Р) +- ВЕ1МК(Х), 1Л.1МК(81.1МК(Х)) +- Р, КЕ1МК(Х) +- Р.
Аналогично, меняя местами обозначения левых н правых элементов, получим соответствующий алгоритм для вставки нового элемента слева от заданного узла. Операция (5) изменяет значения пяти связей, поэтому она выполняется несколь- В списке с только односторонними ссылками нельзя удалить узел МООЕ(Х), не зная, какой узел ему предшествует, так как в предшествующем узле после удаления узла МОВЕ(Х) нужно соответствующим образом изменить значение его связи. В алгоритмах, рассмотренных в разделах 2.2.3 и 2.2.4, эта дополнительная информация всегда была под рукой при каждом удалении узла.
В частности, в алгоритме 2.2.4А указатель Ц1 следовал за указателем О именно для этой цели. Однако, как будет показано ниже, существуют алгоритмы, с помощью которых необходимо удалять произвольно выбранные узлы в середине списка. Именно для этого и используются дважды связанные списки. (Следует отметить, что из циклического списка можно удалить узел МОВЕ(Х), зная только Х, если выполнить полный замкнутый цикл переходов к предшественнику Х.
Ясно, что такая операция крайне неэффективна при работе с длинными списками, и потому она редко используется в качестве альтернативы для дважды связанного списка. См, ответ к упр. 2.2.4 — 8.) ко медленнее, чем операция вставки в односвязном списке, где нужно изменить значения только для трех связей. В качестве примера использования дважды связанных списков рассмотрим программу дискреганого моделирования.
"Дискретное моделирование" означает моделирование системы, в которой предполагается, что все изменения состояния системы происходят в некоторые дискретно заданные моменты Моделируемая "система" обычно представляет собой набор отдельных действующих лиц, которые, хотя и могут взаимодействовать друт с другом, в основном, ведут себя независимо. Например, это могут быть покупатели в магазине, корабли в гавани, сотрудники некоторого предприятия. При этом процесс моделирования заключается в выполнении определенных действий, предусмотренных для данного момента, для перехода к следующему моменту с дальнейшим выполнением других действий, запланированных для нового момента.
И наоборот, "непрерывное моделирование" означает моделирование действий, которые происходят непрерывно, например движение автомобилей по автостраде, полеты космических кораблей к другим планетам и т. д. Непрерывное моделирование часто можно вполне удовлетворительно имитировать с помощью дискретного моделирования с очень малыми временными интервалами между соседними шагами. Но в таком случае получится 'синхронное" дискретное моделирование,при котором многие части системы слегка изменяются на каждом дискретном временном интервале, н такое приложение обычно нуждается в организации программы несколько нного типа, чем тот, который рассмотрен здесь.
Приведенная ниже программа моделирует работу лифта в здании факультета математики Калифорнийского технологического института (Калтех), Результаты такого моделирования, вероятно, будут полезны только тем, кому часто приходится посещать Калтех. И даже им, видимо, проще будет всего несколько раз воспользоваться этим лифтом, чем создавать специальную программу. Но, как обычно случается при изучении методов моделирования, используемые методы программирования гораздо интереснее, чем результаты выполнения программ. Рассматриваемые ниже методы иллюстрируют типичные методики, которые используются в программах дискретного моделирования.
Здание факультета математики имеет пять этажей: подвальный, цокольный, первый, второй и третий В нем находится один лифт с автоматическим управлением, который может останавливаться на каждом этаже. Для удобства перенумеруем этажи в следующем порядке: О, 1, 2, 3 и 4 На каждом этаже есть две кнопки вызова лифта: одна — для движения вверх (ОР), а другая — для движения вниз (ООЧИ). (На самом деле на этаже О имеется только кнопка УР, а на этаже 4 — только кнопка ПОЧИ, но эти особые случаи будут игнорироваться, потому что дополнительные кнопки никогда не будут использоваться ) Соответственно эти кнопки будут обозначаться десятью переменными САььОР [Я и САьЫОЧИ[у), О < у < 4.
Кроме того, переменные СА1.[.САИ[у), О < у < 4, будут представлять кнопки внутри кабины лифта, которые обозначают этаж назначения. Прн нажатии кнопки соответствующей переменной присваивается значение 1, а после выполнения запроса (т е. после того как лифт достигнет заданного этажа) переменной присваивается значение О. До сих пор работа лифта описывалась с точки зрения пользователя, но ситуация станет более интересной, если рассмотреть ее с точки зрения лифта.
Лифт может находиться в одном из трех следующих состояний: движение вниз (СО1ИСОР), движение вверх (601ИСООМИ) или нейтральное состояние (ИЕОТКАЬ) (Для человека текущее состояние обозначается светящимися стрелками внутри лифта.) Если лифт находится в нейтральном состоянии (МЕОТКАЬ) и не на этаже 2, механизм лифта закроет двери и (если до закрытия дверей не дана никакая команда) лифт придет в состояние движения (601ИСОР или 601МСООИИ), направляясь к этажу' 2. (Это его "базовый этаж", так как большинство людей входят в него именно здесь ) Если лифт находится на этаже 2 в состоянии ИЕОТКАЬ, двери со временем закроются и лифт будет ожидать следующей команды. Первая полученная им команда для перемещения на другой этаж приведет лифт в состояние движения 601МСОР или 601МСООЫИ в зависимости от нажатой кнопки. Лифт будет находиться в этом состоянии, пока не остановится. Тогда, если поступили новые команды, произойдет смена направления илн переход в нейтральное состояние (МЕОТКАЬ) непосредственно перед открытием дверей в зависимости от того, какие команды находятся в вызываемой последовательности.
Лифту требуется некоторое время для открытия и закрытия дверей, ускорения и замедления, а также для перемещения от одного этажа к другому. Все эти величины указаны в приведенном ниже алгоритме, который выглядит гораздо более строго, чем привычные нам простые правила пользования лифтом. Этот алгоритм может и не отражать истинный принцип действия лифта, но автор все же верит, что он является простейшим набором правил, которые могут объяснить все те явления, которые автор наблюдал в ходе длительных экспериментов с лифтом во время написания этого раздела. Работа лифта моделируется с помощью двух сопрограмм, одна из которых описывает поведение человека, а друтая — лифта. Эти подпрограммы описывают все выполняемые действия, а также задержки времени, которые должны быть учтены при моделировании.
В приведенном ниже описании переменная Т1ИЕ представляет текущее значение моделируемых часов. Все единицы времени даны в десягпмх долях секунды. Кроме того, в алгоритме используются другие переменные: РЬООК, текущее положение кабины лифта; 01, переменная, которая всегда равна нулю, за исключением промежутков времени, когда люди входят в лифт или выходят из него; 02, переменная, которая становится равной нулю, если лифт более 30 с находится на одном из этажей без движения; 03, переменная, которая всегда равна нулю, за исключением ситуации, когда двери открыты, но никто не входит в лифт и не выходит из него; ЯТАТЕ, текущее состояние лифта (601ИСОР, 601ИСООИИ или МЕОТКАЬ). В исходном состоянии РЬООК = 2, 01 = 02 = 03 = О и ЯТАТЕ = ИЕОТКА1.. Сопрограмма ТТ (Пользователи) Каждый входящий в систему человек (т.
е. тот, кто желает пользоваться лифтом) приступает к выполнению описанных ниже действий, начиная с шага Е1. Ш. [Вход в систему, ожидание следующего человека.] Перечисленные ниже величины легко определить, но эти определения здесь не приводятся. 1М, этаж, на котором следующий человек входит в систему; ООТ, этаж, на который этот человек хочет попасть (ООТ ф 1И); 61ЧЕОРТ1ИЕ, максимальное время ожидания человеком лифта, после которого его терпение исчерпывается и он решает воспользоваться лестницей; 1ИТЕМТ1МЕ, время до прихода другого человека.
После вычисления этих величин программа моделирования работы лифта организует весь процесс так, что следующий человек подходит к лифту в момент Т1МЕ+ 1МТЕКТ1ИЕ. 112. [Получение сигнала и ожидание.] (Назначение этого шага заключается в вызове лифта; особые ситуации могут возникнуть, если лифт уже находится на нужном этаже.) Если РЬООМ = 1М и если следующее действие заключается в выполнении описанного ниже шага Е6 (т. е. если двери лифта закрываются), нужно указать лифту на переход к шагу ЕЗ и отменить выполнение шага Еб. (Это значит, что двери откроются снова, прежде чем лифт начнет движение.) Если РЬООЕ = 1М и 03 ф О, установить 03 +- О, установить ненулевое значение для 01 и снова перейти к выполнению шага Е4. (Это значит, что двери лифта откроются на том же этаже, но кто-то вошел или вышел. На шаге Е4 людям предоставляется возможность входить в лифт в соответствии с обычными правилами хорошего тона.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
