слово в памяти компьютера, иногда остается свободное место для другой связи). Но дополнительные операции, которые могут очень эффективно выполняться с дважды связанными списками, часто являются более чем достаточной компенсацией за дополнительные затраты на память. Помимо очевидного преимущества, связанного с легкостью перехода либо назад, либо вперед вдоль дважды связанного списка, одной из наиболее принципиальных новинок является возможность удаления узла NODE(X) из списка, если известно только значенпе X. Эту операцию довольно легко вывести на основании схемы «состояния "до" и "после"» (рис. 11):

RLINK (LLINK (X) ) RLINK (X), LLINK (RLINK (X) ) LLINK (X)

AVAIL < X.

В списке с только односторонними ссылками нельзя удалить узел NODE(X), не Зная, какой узел ему предшествует, так как в предшествующем узле после удаления узла NODE(X) нужно соответствующим образом изменить значение его связи. В алгоритмах, рассмотренных в разделах 2.2.3 и 2.2.4, эта дополнительная информация всегда была под рукой при каждом удалении узла. В частности, в алгоритме 2.2.4А указатель Q1 следовал за указателем Q именно для этой цели. Однако, как будет показано ниже, существуют алгоритмы, с помощью которых необходимо удалять произвольно выбранные узлы в середине списка. Именно для этого и используются дважды связанные списки. (Следует отметить, что из циклического списка можно удалить узел NODE(X), зная только X, если выполнить полный замкнутый цикл переходов к предшественнику X. Ясно, что такая операция крайне неэффективна при работе с длинными списками, и потому она редко используется в качестве альтернативы для дважды связанного списка. См. ответ к упр. 2.2.4-8.)

После удаления Jj.

AVAIL

Рис. 11. Удаление узла из дважды связанного списка.

Так же просто в дважды связанный список можно вставить узел слева или справа от заданного узла NODE(X). Например, для вставки узла справа от узла NODE(X) необходимо выполнить такие действия:

AVAIL, LLINK (Р) X, LLINK (RLINK (X)) Р,

RLINK(Р) <- RLINK(X), RLINK(X) P.

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

ко медленнее, чем операция вставки в односвязном списке, где нужно изменить значения только для трех связей.

В качестве примера использования дважды связанных списков рассмотрим программу дискретного моделирования. "Дискретное моделирование" означает моделирование системы, в которой предполагается, что все изменения состояния системы происходят в некоторые дискретно заданные моменты Моделируемая "система" обычно представляет собой набор отдельных действующих лиц, которые, хотя и могут взаимодействовать друг с другом, в основном, ведут себя независимо. Например, это могут быть покупатели в магазине, корабли в гавани, сотрудники некоторого предприятия. При этом процесс моделирования заключается в выполнении определенных действий, предусмотренных для данного момента, для перехода к следующему моменту с дальнейшим выполнением других действий, запланированных для нового момента.

И наоборот, "непрерывное моделирование" означает моделирование действий, которые происходят непрерывно, например движение автомобилей по автостраде, полеты космических кораблей к другим планетам и т. д. Непрерывное моделирование часто можно вполне удовлетворительно имитировать с помощью дискретного моделирования с очень малыми временными интервалами между соседними шагами. Но в таком случае получится "синхронное" дискретное моделирование, при котором многие части системы слегка изменяются на каждом дискретном временном интервале, и такое приложение обычно нуждается в организации программы несколько иного типа, чем тот, который рассмотрен здесь.

Приведенная ниже программа моделирует работу лифта в здании факультета математики Калифорнийского технологического института (Калтех). Результаты такого моделирования, вероятно, будут полезны только тем, кому часто приходится посещать Калтех. И даже им, видимо, проще будет всего несколько раз воспользоваться этим лифтом, чем создавать специальную программу. Но, как обычно случается при изучении методов моделирования, используемые методы программирования гораздо интереснее, чем результаты выполнения программ. Рассматриваемые ниже методы иллюстрируют типичные методики, которые используются в программах дискретного моделирования.

Здание факультета математики имеет пять этажей: подвальный, цокольный, первый, второй и третий В нем находится один лифт с автоматическим управлением, который может останавливаться на каждом этаже. Для удобства перенумеруем этажи в след>ющем порядке: О, 1, 2, 3 и 4

На каждом этаже есть две кнопки вызова лифта: одна-для движения вверх (UP), а другая - для движения вниз (DOWN). (На самом деле на этаже О имеется только кнопка UP, а на этаже 4 - только кнопка DOWN, но эти особые случаи будут игнорироваться, потому что дополнительные кнопки никогда не будут использоваться ) Соответственно эти кнопки будут обозначаться десятью переменными GALLUP[j] и CALLDOWN[j], О < J < 4. Кроме того, переменные CALLCAR[j], О < j < 4, будут представлять кнопки внутри кабины лифта, которые обозначают этаж назначения. При нажатии кнопки соответствующей переметшой присваивается значение 1, а после вьшолнения запроса (т е. после того как лифт достигнет заданного этажа) переменной присваивается значение 0.

До сих пор работа лифта описывалась с точки зрения пользователя, но ситуация станет более интересной, если рассмотреть ее с точки зрения лифта. Лифт может находиться в одном из трех следующих состояний: движение вниз (GOINGUP), движение вверх (GOINGDOWN) или нейтральное состояние (NEUTRAL) (Для человека текущее состояние обозначается светящимися стрелками внутри лифта.) Если лифт находится в нейтральном состоянии (NEUTRAL) и не на этаже 2, механизм лифта закроет двери и (если до закрытия дверей не дана никакая команда) лифт придет в состояние движения (GOINGUP или GOINGDOWN), направляясь к этажу 2. (Это его "базовый этаж", так как большинство людей входят в него именно здесь ) Если лифт находится на этаже 2 в состоянии NEUTRAL, двери со временем закроются и лифт будет ожидать следующей команды. Первая полученная им команда для перемещения на другой этаж приведет лифт в состояние движения GOINGUP или GOINGDOWN в зависимости от нажатой кнопки. Лифт будет находиться в этом состоянии, пока не остановится. Тогда, если поступили новые команды, произойдет смена направления или переход в нейтральное состояние (NEUTRAL) непосредственно перед открытием дверей в зависимости от того, какие команды находятся в вызываемой последовательности. Лифту требуется некоторое время для открытия и закрытия дверей, ускорения и замедления, а также для перемещения от одного этажа к другому. Все эти величины указаны в приведенном ниже алгоритме, который выглядит гораздо более строго, чем привычные нам простые правила пользования лифтом. Этот алгоритм может и не отражать истинный принцип действия лифта, но автор все же верит, что он является простейшим набором правил, которые могут объяснить все те явления, которые автор наблюдал в ходе длительных экспериментов с лифтом во время написания этого раздела.

Работа лифта моделируется с помощью двух сопрограмм, одна из которых описывает поведение человека, а другая - лифта. Эти подпрограммы описывают все выполняемые действия, а также задержки времени, которые должны быть учтены при моделировании. В приведенном ниже описании переменная TIME представляет текущее значение моделируемых часов.

Все единицы времени даны в десятых долях секунды. Кроме того, в алгоритме используются другие переменные:

FLOOR, текущее положение кабины лифта;

D1, переменная, которая всегда равна нулю, за исключением промежутков времени, когда люди входят в лифт или выходят из него;

D2, переменная, которая становится равной нулю, если лифт более 30 с находится на одном из этажей без движения;

D3, переменная, которая всегда равна нулю, за исключением ситуации, когда двери открыты, но никто не входит в лифт и не выходит из него;

STATE, текущее состояние лифта (GOINGUP, GOINGDOWN или NEUTRAL).

В исходном состоянии FLOOR = 2, D1 = D2 = D3 = О и STATE = NEUTRAL.

Сопрограмма U (Пользователи) Каждый входящий в систему человек (т. е. тот, кто желает пользоваться лифтом) приступает к выполнению описанных ниже действий, начиная с шага U1.

U1. [Вход в систему, ожидание следующего человека.] Перечисленные ниже величины легко определить, но эти определения здесь не приводятся.