3.2 Обработка списков

Обработка списка имеет дело с методами для обработки списков объектов и списком будущих событий. Пакеты имитационного моделирования позволяют аналитику использовать в явном виде оба списка также как скрытый механизм имитации языка, использовать непосредственно списки и исполнять основные операции над списками для средств аналитика или модели.

Раздел 3.2.1 описывает основные свойства и операции, выполняемые в списках. Раздел 3.2.2 обсуждает использование массивов для обработки списков и использования индексов массива для создания связанных списков. Массивы являются более простым механизмом для описания основных операций, чем более обобщающее понятие динамически распределенные связанные списки, обсуждаемые в разделе 3.2.3. Наконец, раздел 3.2.4 кратко представляет некоторые из современных методов для управления списками.

Цель этого обсуждения обработки списка не состоит в том, чтобы подготовить читателя для работы со списками и их обработку на универсальном языке как, например, ФОРТРАН, C ++, а скорее обеспечить понимание у читателя списков, а так же основных концепций и операций.

3.2.1 Списки: Основные свойства и операции

Как предварительно обсуждено, списки – упорядоченный набор или упорядоченные записи. В имитации каждая запись представляет один объект или одно намеченное событие. Так как списки упорядочиваются, они имеют вершину или голову (первый элемент в списке); некоторый способ обхода списка (чтобы найти второй, третий, и т.д. элементы в списке); и конец или хвост (последний элемент в списке). Главный указатель – переменная, которая направляет или указывает на запись вершины списка. Некоторые списки могут также иметь указатель хвоста, который указывает на последний элемент в списке.

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

Для любого типа списка главные действия в обработке списка – добавлять запись в список и удаляют запись из списка. Определим главные операции в списке:

1. Удаление записи из вершины списка.

2. Удаление записи из любого места в списке.

3. Добавление записи объекта в вершину или конец списка.

4. Добавление записи в произвольную позицию списка, определенную в соответствии с правилом.

В то время как первая и третья операции удаления или добавления записи в вершину или конец списка могут быть выполнены за минимальное время, путем задания двух указателей записи: головы или указателя хвоста, другие две операции требуют, по крайней мере, неполного поиска по списку. Создание этих двух эффективных операций – цель обрабатывающих список методов.

В случае подхода с планированием, когда время продвинуто, и предстоящее событие должно быть выполнено, сначала имеет место операция удаления, а именно, событие в вершине СБС удаляется из СБС. Если произвольное событие отменяется или объект удаляется из списка, основанного на некоторых из его атрибутов (например, его приоритете и сроке выполнения), начинающих действие, то выполняется вторая операция удаления. Когда выполняется присоединение объекта к концу очереди по правилу FIFO, осуществляемое как список, тогда третья операция добавляет объект в конец списка. Наконец, если очередь определяется по правилу «самый ранний срок – первый», то по прибытию в очередь объект должен быть добавлен к списку не в вершину или основание, а в позицию, определяемую сроком для упорядочивающего правила.

При моделировании на компьютере вне зависимости от того, используется ли универсальный язык как, например ФОРТРАН, C или C ++ или пакет имитационного моделирования, каждая запись объекта и намеченное событие храниться в физическом месте компьютерной памяти. Имеются две основные возможности: (a) Все записи хранятся в массивах. Массивы содержат последовательные записи в непрерывных местах в компьютерной памяти. Они поэтому могут быть упомянуты индексом массива, о котором можно думать как о номере строки в матрице. (b) Все объекты и намеченные события представлены структурами (как в C) или классами (как в C ++), и распределены по оперативной памяти произвольно и ссылаются указателями на запись или структуру.

Большинство пакетов имитационного моделирования использует динамически распределенные записи и указатели для сохранения направления элементов списков. Поскольку массивы концептуально более простые, концепция связанных списков сначала объясняется через массивы и индексы массива в разделе 3.2.2 и затем применяется к динамически распределенным записям и указателям в разделе 3.2.3.