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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

14
При переполнении i-го стека реализуется одна из трёх возможно-
стей:
1) Определяется наименьшее k (если такое значение существует),
для которого i < k ≤ n и TOP [k] < BASE [k + 1] (k-й список заканчивается
раньше, чем начинается (k + 1)-й). Затем осуществляется сдвиг на одну
позицию вверх:
CONTENTS (L + 1) ← CONTENTS (L),
для L = TOP [k], TOP [k] – 1, …, BASE [i + 1] + 1.
И выполняются операторы BASE [j] ← BASE [j] +1, TOP [j] ← TOP [j] +1
для j = i + 1, i + 2, …, k.
2) Нельзя найти значение k, удовлетворяющее условию 1), но име-
ется наибольшее k, для которого 1 ≤ k < i и TOP [k] < BASE [k + 1]. Те-
перь осуществляется сдвиг на одну позицию вниз:
CONTENTS (L – 1) ← CONTENTS (L),
для L = BASE [k + 1] + 1, BASE [k + 1] + 2, …, TOP [i].
И выполняется BASE [ j ] ← BASE [ j ] – 1, TOP [ j ] ← TOP [ j ] – 1 для
j = k + 1, k + 2, …, i.
3) Для всех k ≠ i имеет место TOP [k] = BASE [k + 1]. Тогда невоз-
можно найти место для нового элемента i-го стека и работу со стеками
следует прекратить.
Понятно, что многих первых переполнений стеков можно избежать,
если разумно выбрать начальные условия, а не отводить с самого начала
всю память под n-й стек. Например, если ожидается, что стеки будут оди-
накового размера, то можно начать с равномерного распределения памяти:
BASE [ j ] = TOP [ j ] = c
−
−
∞
)(
1
0
LL
n
j
+ L
0
.
Однако каким бы хорошим ни было начальное распределение, оно
позволяет сэкономить лишь фиксированное количество переполнений на
ранней стадии работы программы.
Описанный простейший метод можно улучшить, если при каждой
переупаковке памяти готовить место для более чем одного нового эле-
мента. При этом выигрыш во времени достигается за счёт того, что сдвиг
таблицы на несколько позиций сразу выполняется быстрее, чем несколь-
ко сдвигов на одну позицию.
Предлагается при возникшей ситуации переполнения производить
полную переупаковку памяти, основываясь на изменении размера каждо-
го стека с момента последней переупаковки. Представленный ниже алго-
ритм использует дополнительный массив с именем OLDTOP, в котором
хранятся значения, бывшие в массиве TOP непосредственно после пре-

Страницы