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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

16
R2. [Поиск начала сдвига.] (Все стеки от 1 до j перемещены нуж-
ным образом.) j ← j + 1. Если NEWBASE [ j ] < BASE [ j ], то перейти к
шагу R3; иначе если NEWBASE [ j ] > BASE [ j ], то перейти к шагу R4;
иначе если j > n, то окончить алгоритм; иначе выполнить шаг R2 сначала.
R3. [Сдвиг вниз.] δ ← BASE [ j ] – NEWBASE [ j ]. Для L = BASE [ j ] + 1,
BASE [ j ] + 2, …, TOP [ j ] CONTENTS (L – δ) ← CONTENTS (L). (Заме-
тим, что BASE [ j ] может оказаться равным TOP [ j ], и в этом случае не
требуется никаких действий.) BASE [ j ] ← NEWBASE [ j ], TOP [ j ] ←
TOP [ j ] – δ. Перейти к R2.
R4. [Поиск верхней границы сдвига.] Найти наименьшее k ≥ j, для
которого NEWBASE [k + 1] ≤ BASE [k + 1]. (Заметим, что NEWBASE [n + 1]
должен быть равен BASE [n + 1] и поэтому такое значение k всегда суще-
ствует.) Затем выполнить шаг R5 для T = k, k – 1, …, j ; j ← k и перейти
к R2.
R5. [Сдвиг вверх.] δ ← NEWBASE [T] – BASE [T]. Выполнить
CONTENTS (L + δ) ← CONTENTS (L) для L = TOP [T], TOP [T] – 1, …,
BASE [T] + 1. (Заметим, что, как и на шаге R3, может не потребоваться
никаких действий.) BASE [T] ← NEWBASE [T], TOP [T] ← TOP [T] + δ. ■
Описанные алгоритмы можно адаптировать и для других относи-
тельно адресуемых таблиц, в которых текущая информация располагает-
ся между указателями BASE [ j ] и TOP [ j ].
При занятой памяти только на половину алгоритм G работает хоро-
шо и по крайней мере даёт правильные результаты при почти заполнен-
ной памяти. В последнем случае алгоритм R, осуществляющий переме-
щение последовательных таблиц, работает довольно долго. При большом
количестве последовательных таблиц переменного размера не следует
думать, что удастся использовать пространство памяти на 100% и все-
таки избежать переполнения. Для исключения бессмысленных потерь
времени можно остановить алгоритм G на шаге G3, если значение пере-
менной SUM станет меньше величины S
min
, которую задаёт программист,
избегая тем самым излишне трудоёмкие переупаковки.
Упражнения
1. Пусть состояние памяти по окончании последней переупаковки
было следующим:
1 1 3 3 3 4 4
0 1 2 3 4 5 6 7 8 9 10
11
12
13
14
15
16
17
18
19
Заметим, что число 1 в некоторой ячейке памяти обозначает элемент
первого стека, число 2 − элемент второго стека и т.д. Следовательно,
базовые адреса стеков имеют значения: BASE [1] = –1, BASE [2] = 2,

Страницы