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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

24
редью, которые использованы на шагах Т4, Т6 и Т7, не идентичны опера-
циям (18) и (20), поскольку в этой системе мы пользуемся специальными
свойствами очереди и нет необходимости создавать узлы или возвращать
их в свободное пространство.
Время выполнения алгоритма оценивается значением выражения
c
1
m + c
2
n, где m – количество вводимых отношений, n – количество объ-
ектов; c
1
и c
2
– константы.
Циклический список – связанный список такой, что связь его по-
следнего узла не пустая, а идёт к первому узлу этого же списка:
Здесь PTR – указатель на самый правый узел списка; LINK(PTR) –
адрес самого левого узла.
Наиболее важными операциями являются:
a) Включение Y слева: P ⇐ AVAIL, INFO(P) ← Y, LINK(P) ←
LINK(PTR), LINK(PTR) ← P.
b) Включение Y справа: Включение Y слева, затем PTR ← P.
c) Запись в Y значения из левого узла и исключение этого узла из
списка: P ← LINK(PTR), Y ← INFO(P), LINK(PTR) ← LINK(P), AVAIL ⇐ P.
Описание операций (a), (b) и (c) не учитывает того, что циклический
список может быть пустым. Условившись, что PTR равен Λ в случае пус-
того списка, уточним упомянутые операции:
a) Включение Y слева: P ⇐ AVAIL, INFO(P) ← Y. Если PTR = Λ,
то PTR ← LINK(P) ← P; иначе LINK(P) ← LINK(PTR), LINK(PTR) ← P.
b) Включение Y справа: Включение Y слева, затем PTR ← P.
c) Запись в Y значения из левого узла и исключение этого узла из спи-
ска: Если PTR = Λ, то НЕХВАТКА; иначе P ← LINK(PTR), Y ← INFO(P),
LINK(PTR) ← LINK(P), AVAIL ⇐ P и если PTR = P, то PTR ← Λ.
Заметим, что операции (a), (b) и (c) являются операциями дека, ог-
раниченного по выходу. Это значит, что циклический список можно ис-
пользовать или как стек (операции (a) и (c)), или как очередь (операции
(b) и (c)).
Применительно к циклическим спискам эффективны и некоторые
другие важные операции:
d) Очистка списка: Если PTR ≠ Λ, то P ← AVAIL, AVAIL ←
LINK(PTR), LINK(PTR) ← P.
(23)
PTR

Страницы