ВУЗ:
Составители:
20
Связанное распределение особенно удобно в применении к очере-
дям. При этом связи должны быть направлены от начального узла к по-
следнему:
Здесь F, R – указатели на начало и конец очереди соответственно.
Включение информации из Y в конец очереди выполняется следую-
щим образом:
P ⇐ AVAIL, INFO(P) ← Y, LINK(P) ← Λ.
Если F = Λ, то F ← P, иначе LINK(R) ← P. R ← P. (18)
Если (17) – ситуация перед включением, то после включения в ко-
нец очереди схема будет иметь следующий вид:
Исключение информации из начала очереди выполняется следую-
щим образом:
Если F = Λ, то НЕХВАТКА, иначе P ← F, F ← LINK(P),
Y ← INFO(P), AVAIL ⇐ P. (20)
Если схема (17) иллюстрирует ситуацию перед исключением, то в
результате этой операции она преобразуется в следующую схему:
Перейдём далее к изучению практического примера топологической
сортировки, которая оказывается полезной всякий раз, когда мы сталки-
ваемся с упорядочением.
Пусть имеется следующее частично упорядоченное множество, за-
данное графом:
(17)
F R
(19)
F R
AVAIL
⇒
Y
(21)
F
R
⇓
AVAIL
Страницы
- « первая
- ‹ предыдущая
- …
- 18
- 19
- 20
- 21
- 22
- …
- следующая ›
- последняя »
