3.2.3 Использование динамического распределения и связанных списков

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

В этом тексте, не рассматриваются детали распределения и освобождения компьютерной памяти, и предполагается, что необходимые операции происходят как необходимо. При динамическом распределении на запись ссылаются указателем вместо индекса массива. Когда запись распределяется в C или C ++, программа распределения возвращает указатель на распределенную запись, которая должна быть сохранена в переменной области или другой записи для более позднего использования. Об указателе на запись можно думать как физическом или логическом адресе в компьютерной памяти для записи.

В нашем примере, мы будем использовать систему обозначений для записей, идентичную предыдущему разделу (3.2.2):

Объекты: [ID, атрибут, следующий указатель]

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

Но мы не будем ссылаться на систему обозначений массива R(i) как прежде, потому что это ввело бы в заблуждение. Если бы по некоторым причинам мы хотели бы ввести третий элемент в список, то мы должны были бы просмотреть список, считая элементы, пока мы не достигли бы третьей записи. В отличие от массивов нет никакого способа отыскать непосредственно i-ю запись в связанном списке, поскольку фактические записи могут быть сохранены в любом произвольном месте в компьютерной памяти и не сохранены рядом как для массива.

ПРИМЕР 3.8 (Список будущих событий и проблема самосвала)

Основываясь на табл. 3.6 намеченные события в проблеме самосвала Примера 3.5 расширены, чтобы включить указатель на следующее намеченное событие в списке будущих событий, и они могут быть представлены как:

[ event type, event time, DT i , nextptr ]

например

[ EL, 10, DT 3, nextptr ],

где EL– конец события загрузки, которое произойдет в будущее время 10 для самосвала DT 3, а поле nextptr указывает на следующую запись в СБС. Имейте в виду, что записи могут быть сохранены где-нибудь в компьютерной памяти и не обязательно сохранены рядом. Рис. 3.9 представляет список будущих событий для ЧАСОВ со временем 10 взятый из табл. 3.6. Четвертое поле в каждой записи – значение указателя на следующую запись в списке будущих событий.

Языки C и C ++ и другие универсальные языки используют различную систему обозначений для ссылки на данные для указателя переменных. Для целей обсуждения, если R – указатель на запись, то

R  Eventtype, R  Eventtime, R  next

являются типом события, время события и следующая запись намеченного события, а R указывает «на». Например, если R установлено равным указателю головы для СБС для значения ЧАСОВ 10, то

R  eventtype = EW

R  eventtime = 12

R next – указатель для следующего намеченного события в СБС,

Рис. 3.9. Список будущих событий для самосвалов со связями

Так что

R  next  eventtype = EL

R  next  eventtime = 20

R  next  next является указателем на третье намеченное событие в СБС.

Если одно из полей указателя нулевое (или пустой указатель), то эта запись – последний элемент в списке, и указатель переменной tailptr указывает на эту последнюю запись, как изображено на рис. 3.9.

Были описаны так называемые однонаправленные списки, так как они имеют одностороннее соединение от головы списка к его хвосту. Указатель хвоста сохранен главным образом для удобства и эффективности, особенно для списков, для которых элементы добавляются в конец списка. Конечно, указатель хвоста не строго необходим, поскольку последний элемент может всегда быть найден, просматривая список, что делает некоторые операции более эффективными.

Для некоторых целей желательно проходить или искать элементы списка, начиная с хвоста также как и от головы. Для таких целей может использоваться двунаправленный список. Записи в двунаправленном списке имеют два поля указателя, одно для следующей записи и одно для предыдущей записи. Хорошие ссылки, в которых обсуждаются массивы, одно- и двусвязные списки, поиск и прохождение списков – Cormen и др. [1990] и Sedgewick [1998].

Цель этого раздела кратко представить некоторых из современных идей.

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

Некоторые современные алгоритмы используют другие представления списка, чем двунаправленный список, как, например кучи или деревья. Эти темы не рассматриваются в этом тексте. Хорошие ссылки – Cormen и др. [1990] и Sedgewick [1998].