AOP_Tom1 (1021736), страница 80
Текст из файла (страница 80)
Состояние после вызова: Многочлен (Р) добавляется в список АУА1Ь; значения других регистров не определены. [Зомгчонпг. Эта подпрограмма может быть использована вместе с подпрограммой из упр. 11 в последовательности ь391 Ц;Л(Р ЕЕАЯЕ; 191 Р; Л(Р СОРТ; ЯТ2 О", чтобы получить "многочлен (О) +- многочлен (Р)".] 14. [ЯЯ] Создайте подпрограмму для компьютера Н1Х со следующими спецификациями. Вызов: 1ИР ХЕИО. Состояние до вызова: Не обусловлено. Состояние после вызова: г12 указывает на вновь созданный многочлен, равный О; значения других регистров не определены.
15. [24] Создайте подпрограмму для компьютера Н1Х дэя выполнения алгоритма М со следующими спецификациями. Вызов: )МР МЦЬТ. Состояние до вызова: г11 = Р, г12 = (), г14 = М. Состояние после вызова; Многочлен(Ц) < — многочлен(Ц) + многочлен(М) х многочлеп(Р); значения регистров г!1, г12, г14 остаются неизменными; значения других регистров не определеиы. [Замечание. Используйте программу А как подпрограмму, изменив значения ЯМ1, ЯМ2 и 2МЗ.] 16. (М28] Оцените время выполнения подпрограммы из упр.
15 иа основе наиболее важных параметров. ь 17. (22] В чем заключается преимущество представления многочлена в видециклического списка (опясанного в этом разделе) по сравнению с представлением в виде прямого линейного связанного списка, который завершается Л (и описанного в предыдущем разделе)? ь 18. (25] Придумайте способ представления циклических списков внутри компьютера таким образом, чтобы проход списка был эффективным в обоих направлениях, причем чтобы в каждом узле использовалось только одно поле связи.
(Указание. Если есть два указателя иа два последовательных узла х; 1 и х„то должна существовать возможность доступа к узлам хыа и х,-г.] 2.2.5. Дважды связанные списки Для гибкой работы со связанными списками в каждый узел можно включить даже две связи, которые будут указывать иа два соседних элемента: агент (1) Здесь ЬЕРТ и МИНТ обозначают переменные связи, которые указывают на левый и правый концы списка. Каждый узел списка включает две связи, например ЬЫМК и НЫМК.
Как показано в упр. 1, при таком представлении со списком можно выполнять те же операции, что и с деком общего типа. Однако операции с деком почти всегда гораздо легче выполняются, если в нем присутствует узел с функциями заголовка списка, который рассмотрен в предыдущем разделе. При наличии заголовка списка типичная схема дважды связанного списка выглядит так, как показано ниже: Заголовок списКа (2) Поля НЬТМК и ЬЫМК заголовка списка используются вместо указателей ЬКРТ и Н1СНТ в схеме (1). Правый и левый концы абсолютно симметричны, поэтому заголовок списка может с таким же успехом располагаться с правой стороны списка на схеме (2). Если список пуст, оба поля связи заголовка списка указывают на сам заголовок. Представление списка в виде (2), очевидно, удовлетворяет условию Н1.1МК(1.1.1МК(Х) ) = ЬЫМК(НЫМК(Х)) = Х, где Х вЂ” адрес любого узла в списке (включая его заголовок).
Именно поътому представление списка в виде (2) предпочтительнее, чем в виде (1). Дважды связанный список обычно занимает гораздо больше места в памяти, чем однократно связанный список (хотя в у.зле, который не заполняет полностью слово в памяти компьютера, иногда остается свободное место для другой связи). Но дополнительные операции, которые могут очень эффективно выполняться с дважды связанными списками, часто являются более чем достаточной компенсацией за дополнительные затраты на память. Помимо очевидного преимущества, связанного с легкостью перехода либо назад, либо вперед вдоль дважды связанного списка, одной из наиболее принципиальных новинок является возможность удаления узла МООЕ(Х) нз списка, если известно только значение Х.
Эту операцию довольно легко вывести на основании схемы «состояния "до" н "после"ъ (рис. 11): КЕ1МК(ОЕ1МК(Х)) +- ЕЕ1МК(Х), 1.11МК(ЕЫМК(Х)) +- ШМК(Х) АЧАЛО. Ф-. Х. Перед удаленнем Рис. 11. Удаление узла из дважды связанного списка. После удаления АЧАП. Так же просто в дважды связанный список можно вставить узел слева или справа от заданного узла МООЕ(Х). Например, для вставки узла справа от узла МООЕ(Х) необходимо выполнить такие действия: Р 4= АЧА11., ЕЕ1МК(Р) +- Х, КЕ1МК(Р) < — КЕ1МК(Х), ШМК(Ы.1МК(Х)) <†Р, КЫМК(Х) < — Р. Аналогично, меняя местами обозначения левых и правых элементов, получим соответствующий алгоритм для вставки нового элемента слева от заданного узла. Операция (5) изменяет значения пяти связей, поэтому она выполняется несколь- В списке с только односторонними ссылками нельзя удалить узел МООЕ(Х), не зная, какой узел ему предшествует, так как в предшествующем узле после удаления узла МООЕ(Х) нужно соответствующим образом изменить значение его связи.
В алгоритмах, рассмотренных в разделах 2.2.3 и 2.2.4, эта дополнительная информация всегда была под рукой при каждом удалении узла. В частности, в алгоритме 2.2.4А указатель Ц1 следовал за указателем О именно для этой цели. Однако, как будет показано ниже, существуют алгоритмы, с помощью которых необходимо удалять произвольно выбранные узлы в середние списка. Именно для этого и используются дважды связанные списки. (Следует отметить, что из циклического списка можно удалить узел МООЕ(Х), зная только Х, если выполнить полный замкнутый цикл переходов к предшественнику Х.
Ясно, что такая операция крайне неэффективна при работе с длинными списками, и потому она редко используется в качестве альтернативы для дважды связанного списка. См. ответ к упр. 2.2.4-8.) ко медленнее, чем операция вставки в односвязном списке, где нужно изменить значения только для трех связей. В качестве примера использования дважды связанных списков рассмотрим программу дискрегпного моделирования. "Дискретное моделирование" означает моделирование системы, в которой предполагается, что все изменения состояния системы происходят в некоторые дискретно заданные моменты Моделируемая "система" обычно представляет собой набор отдельных действующих лнц, которые, хотя и могут взаимодействовать друг с другом, в основном, ведут себя независимо.
Например, это могут быть покупатели в магазине, корабли в гавани, сотрудники некоторого предприятия. При этом процесс моделирования заключается в выполнении определенных действий, предусмотренных для данного момента, для перехода к следующему моменту с дальнейшим выполнением других действий, запланированных для нового момента. И наоборот, "непрерывное моделирование" означает моделирование действий, которые происходят непрерывно, например движение автомобилей по автостраде, полеты космических кораблей к другим планетам и т. д. Непрерывное моделирование часто можно вполне удовлетворительно имитировать с помощью дискретного моделирования с очень малыми временными интервалами между соседними шагами. Но в таком случае получится "синхронное" дискретное моделирование, при котором многие части системы слегка изменяются на каждом дискретном временном интервале, и такое приложение обычно нуждается в организации программы несколько иного типа, чем тот, который рассмотрен здесь.
Приведенная ниже программа моделирует работу лифта в здании факультета математики Калифорнийского технологического института (Калтех). Результаты такого моделирования, вероятно, будут полезны только тем, каму часто приходится посещать Калтех. И даже им, видимо, проще будет всего несколько раз воспользоваться этим лифтом, чем создавать специальную программу. Но, как обычно случается прн изучении методов моделирования, используемые методы программирования гораздо интереснее, чем результаты выполнения программ.
Рассматриваемые ниже методы иллюстрируют типичные методики, которые используются в программах дискретного моделирования. Здание фанультета математики имеет пять этажей: подвальный, цокольный, первый, второй и третий В нем находится один лифт с автоматическим управлением, который может останавливаться на каждом этаже. Для удобства перенумеруем этажи в следующем порядке: О, 1, 2, 3 и 4 На каждом этаже есть две кнопки вызова лифта: одна — для движения вверх (ОР), а другая — для движения вниз (00УИ).
(На самом деле на этаже О имеется только кнопка ОР, а на этаже 4 — только кнопка 00нн, но эти особые случаи будут игнорироваться, потому что дополнительные кнопки никогда не будут использоваться ) Соответственно этн кнопки будут обозначаться десятью переменными СА1.1ЛР[~) н САЕ1.0011М(у), О < у < 4. Кроме того, переменные СА11.САйгу), О < у < 4, будут представлять кнопки внутри кабины лифта, которые обозначают этаж назначения. Прн нажатии кнопки соответствующей переменной присваивается значение 1, а после выполнения запроса (т е.
после того как лифт достигнет заданного этажа) переменной присваивается значение О. До сих пор работа лифта описывалась с точки зрения пользователя, но ситуация станет более инте)зесной, если рассмотреть ее с точки зрения лифта. Лифт может находиться в одном из трех следующих состояний: движение вниз (601МСОР), движение вверх (601МСООММ) или нейтральное состояние (МЕОТЕАЬ) (Для человека текущее состояние обозначается светящимися стрелками внутри лифта.) Если лифт находится в нейтральном состоянии (МЕОТЕАЬ) и не на этаже 2, механизм лифта закроет двери и (если до закрытия дверей не дана никакая команда) лифт придет в состояние движения (СО1МСОР или 601МСООЫМ), направляясь к этажу 2.
(Это его "базовый этаж", так как большинство людей входят в него именно здесь ) Если лифт находится на этаже 2 в состоянии МЕОТЕАЬ, двери со временем закроются и лифт будет ожидать следующей команды. Первая полученная им команда для перемещения на другой этаж приведет лифт в состояние движения 601МСОР или 601МСООУМ в зависимости от нажатой кнопки. Лифт будет находиться в этом состоянии, пока не остановится. Тогда, если поступили новые команды, произойдет смена направления или переход в нейтральное состояние (МЕОТНАЬ) непосредственно перед открытием дверей в зависимости от того, какие команды находятся в вызываемой последовательности.
Лифту требуется некоторое время для открытия и закрытия дверей, ускорения и замедления, а также для перемещения от одного этажа к другому. Все эти величины указаны в приведенном ниже алгоритме, который выглядит гораздо более строго, чем привычные нам простые правила пользования лифтом. Этот алгоритм может и не отражать истинный принцип действия лифта, но автор все же верит, что он является простейшим набором правил, которые могут объяснить все те явления, которые автор наблюдал в ходе длительных экспериментов с лифтом во время написания этого раздела. Работа лифта моделируется с помощью двух сопрограмм, одна из которых описывает поведение человека, а другая — лифта. Этн подпрограммы описывают все выполняемые действии, а также задержки времени, которые должны быть учтены при моделировании.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
