Методы программирования. Громов Ю.Ю - 19 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

19
Использование связанного распределения предполагает поиск пус-
того пространства для нового узла. Для этого существует специальный
список, назовём его AVAIL, который содержит все узлы, которые в дан-
ный момент не используются, и ничем не отличается от любых других
списков. Переменная связи AVAIL ссылается на верхний элемент этого
списка.
Для выделения узла из списка AVAIL с целью его использования не-
обходимо поступить следующим образом:
X ← AVAIL, AVAIL ← LINK (AVAIL). (12)
В результате из стека AVAIL исключается верхний узел и перемен-
ная связи X становится указателем на только что выделенный узел. Опе-
рацию (12) для краткости будем обозначать X ⇐ AVAIL.
Если узел по адресу X далее не нужен, то его можно вернуть в спи-
сок свободного пространства:
LINK (X) ← AVAIL, AVAIL ← X. (13)
Эту операцию будем обозначать AVAIL ⇐ X.
Для построения списка AVAIL в начале работы необходимо (A) свя-
зать вместе все узлы, которые будут использоваться, (B) занести в AVAIL
адрес первого из этих узлов и (C) сделать связь последнего узла пустой.
Множество всех узлов, которые могут быть использованы, называют пу-
лом памяти.
С учётом проверки на переполнение операцию X ⇐ AVAIL следует
выполнять так:
Если AVAIL = Λ, то ПЕРЕПОЛНЕНИЕ;
в противном случае X ← AVAIL, AVAIL ← LINK
(AVAIL). (14)
Возникшее ПЕРЕПОЛНЕНИЕ означает, что необходимо прекратить
выполнение программы.
Рассмотрим несколько наиболее распространённых операций со свя-
занными списками, если работа ведётся со стеками и очередями.
Пусть имеется стек, на верхний элемент которого указывает пере-
менная T. Для включения информации из Y в стек используется вспомо-
гательный указатель P:
P ⇐ AVAIL, INFO(P) ← Y, LINK(P) ← T, T ← P. (15)
Для считывания в Y информации из стека следует:
Если T = Λ, то НЕХВАТКА;
иначе P ← T, T ← LINK(P), Y ← INFO(P), AVAIL ⇐ P. (16)

Страницы