3.2.2 Использование массивов для обработки списка

Метод хранения списка в виде массива типичен для ФОРТРАНА, но может использоваться в других процедурных языках. Поскольку большинство версий ФОРТРАНА не имеет фактических структур данных типа записи, запись может быть осуществлена как строка в двухмерном массиве или как множество параллельных массивов. Для удобства используется система обозначений R (i) для обращения к i-ой записи в массиве, и это может быть сохранено для используемого языка. Наиболее современные пакеты имитационного моделирования не использует массивы для хранения списка, а скорее использует динамически распределенныее записи, которые создаются сначала, когда нужно, и разрушаются, когда они больше не нужны.

Массивы выгодны для указания любой i -ой записи, так как могут быть найдены быстро без поиска, просто ссылаясь на R (i). Массивы неудобны, когда элементы добавляют в середину списка, или когда список должен быть перестроен. Кроме того, массивы обычно имеют постоянный размер, определенный во время компиляции или после начального распределения, когда программа начинает выполняться. При моделировании максимальное число записей для любого списка бывает трудно или невозможно определить заранее, в то время как текущее число элементов в списке может изменяться широко в течение выполняемой имитации. Хуже всего, что большинство имитаций требует более одного списка и, если бы сохранять их в отдельных массивах, каждый бы список должен быть самой большой размерности, что потенциально приведет к использованию чрезмерного количества компьютерной памяти.

При использовании массивов для сохранения списков, имеются два основных метода для хранения направления расположения записей в списке. Один метод состоит в том, чтобы хранить первую запись в R(1), вторую в R (2) и так далее, и последнюю в R (tailptr), где tailptr используется, чтобы обратиться к последнему элементу в списке. В то время как эта простая концепция проста для понимания, этот метод будет чрезвычайно неэффективен для большинства списков кроме самые коротких, у которых число записей меньше пяти. Поскольку при добавлении элемента, например в позицию 41 в списке из 100 элементов, последние 60 записей должны быть физически перемещены вниз на одну позицию массива для выделения пространства под новую запись. Даже если это было бы список "первый пришел – первый вышел" удаление первого элемента будет неэффективно, поскольку все остающиеся элементы должны были бы физически продвинуты на одну позицию в массиве. Физический метод перестановки управления списками не будет далее обсуждаться. Поскольку необходимо чтобы метод отслеживал и перестраивал логически упорядоченные элементы в списке без физического перемещения записи в компьютерной памяти.

Во втором методе переменная названная главный указатель с именем headptr, указывает на запись вершины списка. Например, если бы запись в позиции R(11) была бы записью в вершине списка, то headptr имел бы значение 11. Кроме того, каждая запись имеет поле сохраняемого индекса или указателя следующей записи в списке. Для удобства, допустим R(i, next) представляет поле следующего индекса.

ПРИМЕР 3.7 (Список для самосвалов в очереди взвешивания)

В Примере 3.5 проблемы самосвалов, предполагается, что образовалась очередь ожидания из трех самосвалов на взвешивание в том же порядке как для ЧАСОВ во время 10 в табл. 3.6, которая определяется как DT 3, DT 2, и DT 4. Предположим далее, что модель прослеживает один атрибут каждого самосвала, его время прибытия в очередь взвешивания, модифицируя каждый раз его время прибытия. Наконец, предположим, что объекты сохранены в записях в массиве с размерностью от 1 до 6, одна запись на каждый самосвал. Каждый объект представлен записью с 3 полями, первое – идентификатор объекта, второе время прибытия в очередь взвешивания и последнее поле – указатель "к точке" следующей записи, если таковые вообще имеются в списке. Очередь взвешивания представлена следующим образом:

[ DTi, время прибытия в очередь взвешивания, следующий индекс]

Перед их первым прибытием в очередь взвешивания и перед добавлением к списку очереди взвешивания, вторые и третьи поля бессмысленны. Во время 0, записи были бы инициализированы следующим образом:

R(1) = [ DT 1, 0.0, 0]

R(2) - [ DT 2, 0.0, 0]

. . .

R(6) = [ DT 6, 0.0, 0]

Тогда для ЧАСОВ со временем 10 в табл. 3.6 для моделирования список объектов в очереди взвешивания был бы определен так:

headptr = 3

R(1) = [ DT 1, 0.0, 0]

R(2) = [ DT 2, 10.0, 4]

R(3) = [ DT 3, 5.0, 2]

R(4) = [ DT 4, 10.0, 0]

R(5) = [ DT 5, 0.0, 0]

R(6) = [ DT 6, 0.0, 0]

tailptr = 4

Список создается в логическом порядке для прохода списка, начиная с главного указателя и перехода к следующей записи по указателю, что касается примера:

headptr = 3

R(3) = [ DT 3, 5.0, 2]

R(2) = [ DT 2, 10.0, 4]

R(4) = [ DT 4, 10.0, 0]

Нулевой вход для следующего указателя в R(4), также как tailptr = 4, указывает, что DT 4 конечный элемент списка.

При использовании следующих указателей для дисциплины FIFO как, например очередь взвешивания в этом примере, операции добавления и удаления записей объекта, когда самосвалы присоединяется и покидают очередь взвешивания, особенно простые. Когда ЧАСЫ установлены на время 12, самосвал DT 3 начинает взвешивание и оставляет очередь взвешивания. Чтобы удалять запись объекта DT 3 из вершины списка, надо модифицировать главный указатель, устанавливая его равным следующему значению указателя записи вершины списка, как в:

headptr = R(headptr, next)

Для этого примера получим:

headptr = R(3, next) = 2

Значение для самосвала DT 2 в R(2) теперь вверху списка.

Точно так же для ЧАСОВ со временем 20, самосвал DT 5 прибывает в очередь взвешивания и присоединяется к концу очереди. Чтобы добавлять записи DT 5 объекта в конец списка, предприняты следующиешаги:

R(tailptr, next) = 5 (предварительно модифицирует следующее поле указателя последнего элемента)

tailptr = 5 (модифицирует значение указателя хвоста)

Эти операции становятся более сложными, когда список – упорядоченный список, как, например список будущих событий или список объектов, упорядоченный по атрибутам объекта. Для упорядоченных списков обычно требуется поиск, чтобы добавлять или удалить элемент где-нибудь, исключая голову или хвост списка. См. Пример 3.8.

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