из незаполненных таблиц. Можно использовать сразу несколько способов переупаковки, причем некоторые из них будут рассмотрены подробно, так как они очень важны для организации последовательного упорядочения линейных списков. Сначала рассмотрим наиболее простые способы, а затем - некоторые альтернативные им варианты.

Предположим, что существует п стеков и что значения BASE [г] и ТОР [г] обрабатываются согласно алгоритмам (9) и (10). Предполагается также, что эти стеки совместно используют общую область памяти, состоящую из L ячеек, удовлетворяющих условию Lo < L < Loo. (Здесь Lo и Loo-константы, которые задают общий размер доступной памяти в словах.) Начнем с рассмотрения случая, когда все стеки пусты, т. е.

BASE С j] = TOP[j] = Lo для 1 < j < п. (11)

Предположим также, что BASE[n4-1] = Loo, и тогда алгоритм (9) будет применим для i = п.

При переполнении (OVERFLOW) стека г возможны три варианта развития событий.

a) Найдем наименьшее к, для которого г < < п и TOP[fc] < BASE [/с Ч-1], если такое к существует. Теперь переместим все элементы на один узел вверх:

CONTENTS (L 4-1) <- CONTENTS (L) для TOP[fc] > L > BASE [г + 1].

(Во избежание утраты информации это следует делать в порядке убывания, а не возрастания значений L. Если ТОР [fc] = BASE [г Ч-1], такие перемещения вьшолнять не потребуется.) Наконец, BASE[j] <- BASE[j] Ч- 1 и TOP[j] <-TOP[j] + 1 для i <j <к.

b) Допустим, что ни одно к не удовлетворяет условию (а), но существует такое наибольшее к, для которого 1 < А; < г и TOP[fc] < BASE[fc --1]. Переместим все элементы на один узел вниз:

CONTENTS(L -!)•(- CONTENTS(L) для BASE[fc 4-1] < L < ТОРИ.

(Это нужно сделать только в порядке возрастания значений L.) Затем BASE[j] •(- BASE[j] - 1 и TOP[j] <- TOPCj] - 1 для < j < г.

c) Допустим, что ТОР [fc] = BASE[fc--1] для всех к i. Тогда очевидно, что для нового элемента стека нельзя найти свободное пространство, и поэтому работу программы придется прервать.

На рис. 4 показан пример конфигурации памяти для случая, когда п = 4, Lo = О, Loo = 20, по окончании последовательного выполнения действий

inn4 4Dii;iiIii;i4D2Di- (12)

(Здесь Ij и Dj относятся к операциям вставки и удаления в стеке j, а звездочка обозначает переполнение (OVERFLOW). При этом предполагается, что в начальный момент для стеков 1-3 пространство в памяти не выделялось.)

Ясно что в начальный момент многих ситуаций переполнения стеков можно избежать, если выбрать оптимальные начальные условия вместо выделения сразу всего доступного пространства в памяти для п-го стека, как предлагается в условии (11). Например, если предполагается, что размеры всех стеков равны, то следует

1 2 3 4 5 6 ,7 8

10 11 12 13 14 15 16 17 18 19 20

CN CN m m f

to О

H CL, M

CO о CO

->! H -л

о E-I

Рис. 4. Пример конфигурации памяти после выполнения нескольких операций вставки удаления.

выбрать следующие начальные условия:

BASE[j] =TOP[j] =

+ Lq для I < j <П.

(13)

Очевидно, что, обладая определенным опытом работы с некоторой програм.мой. можно предложить более подходящие начальные значения. Однако независи.мо от типа начального распределения таким образом можно избежать лишь незначительного фиксированного количества событий переполнения, причем этот эффект будет заметен только на начальных стадиях работы программы (см. упр. 17).

Другой возможный способ усовершенствования рассматриваемого метода основан на выделении при каждой переупаковке памяти объема свободного пространства, достаточного для размещения более чем одного нового элемента таблицы. Эта идея была использована Й. В. Гарвиком, который предложил полностью переупаковывать память при каждом событии переполнения на основе изменения каждого стека по окончании последней переупаковки. В его алгоритме используется дополнительный массив значений OLDTOP[j], 1 < j < п, которые равны значениям ТОР [ j] сразу после предьщущего выделения памяти. В исходном состоянии таблицы выглядят так же, как и прежде, т. е. OLDTOP [ j] = ТОР [ j]. Этот алгоритм состоит из следующих шагов.

Алгоритм G {Перераспределение последовательных таблиц). Предположим, что переполнение (OVERFLOW) произошло в стеке i согласно условиям (9). После вьшолнения алгоритма G либо будет исчерпана емкость памяти, либо память будет переупорядочена таким образом, что сможет быть выполнена операция NODE (ТОР [г]) (- У (Обратите внимание, что значение ТОР [г] увеличено в (9) еще до применения алгоритма G.)

G1. [Инициализация.] Пусть SUM •«- Loc - Lq, INC <- 0. Выполним шаг G2 хтя 1 < j < п. (В результате SUM будет равно общему размеру доступного пространства в памяти, а INC - общему количеству последовательных увеличений размеров стеков по завершении последнего распределения памяти.) Выполнив Эти действия, перейдем к шагу G3.

G2. [Сбор статистических данных.] Пусть SUM ч- SUM - (TOPCj] - BASE[j]). Еста TOP[j] > OLDTOP[j], то D[j] <- TOP[j] - OLDTOPCj] и INC <- INC Ч-D[j]; в противном случае D [j] •<- 0.

G3. [Ресурсы памяти исчерпаны?] Если SUM < О работа не может быть продолжена.

G4. [Вычисление показателей перераспределения памяти.] Пусть а <- 0.1 х SUM/n, /3 <- 0.9 X SUM/ING. (Здесь а и 0 - дробные, а не целые числа, которые необходимо вычислить с заданной точностью. На следующем этапе доступное пространство будет рЁйгпределено среди отдельных списков следующим образом: приблизительно 10% доступной памяти будет распределено поровну среди п стеков, а оставшиеся 90% будут разделены пропорционально увеличению размера стеков со времени предыдущего распределения памяти.)

G5. [Вычисление новых базовых адресов.] Пусть NEWBASE[1] <- BASE[1] и cr •«- 0; тогда для j = 2,3,...,п установим такие значения: г <- а + а + Dlj - 1/3, NEWBASE[j] •(- NEWBASE[j - 1] Ч- TOP[j - 1] - BASE[j - 1] Ч- [r\ - [ctJ и a <- г.

G6. [Переупаковка.] Пусть TOP [г] <-TOP[i]-l. (Таким образом задается истинный размер г-го стека для того, чтобы не предпринимались попытки переместить информацию за его пределами.) Выполните приведенный ниже алгоритм R, а затем установите ТОР [г] <- ТОР [г] + 1. Наконец, установите OLDTOP[j] •«-ТОР [ j] для 1 < j < п. I

Вероятно, наиболее интересной частью всего этого алгоритма является сам процесс перераспределения, который описывается ниже. Он не совсем тривиален, поскольку одни фрагменты памяти смещаются вниз, а другие - вверх. Очевидно, что очень важно не наложить перемещаемый фрагмент памяти на другую полезную информацию, после чего она может быть полностью утрачена.

Алгоритм R (Перемещение последовательных таблиц). Для 1 < j <п информация, заданная с помощью адресов BASE [ j] и ТОР [ j] в соответствии с указанными выше соглашениями, перемещается на новое место, задаваемое с адресами NEWBASE[j], а сами величины BASE [ j] и ТОР [ j] после этого принимают новые значения. Данный алгоритм основан на легко проверяемом условии, что перемещаемые вниз данные не должны пересекаться с любыми другими перемещаемыми вверх данными, а также с любыми неперемещаемыми данными.

R1. [Инициализация.] Установить j •(- 1.

R2. [Поиск начала перемещения.] (Теперь все перемещаемые вниз стеки с 1- до j-ro перемещены в новое место.) Будем последовательно увеличивать значение j с шагом 1 до тех пор, пока не выполнится одно из перечисленных ниже условий:

a) NEWBASE[j] < BASE[j]: перейти к шагу R3;

b) j > п: перейти к шагу R4.

R3. [Перемещение списка вниз.] Установить S <- BASE[j] -NEWBASE[j]. Установить CONTENTS(L-J) (- CONTENTS(L) для L = BASE[j] + 1, BASE[j] +2, TOP[j]-(Возможен вариант, когда значение BASE [ j] равно TOP [ j]; тогда никаких действий предпринимать не следует.) Установить BASE[j] <- NEWBASE[j]> TOP [j] <- TOP [j] - S. Вернуться к шагу R2.

R4. [Поиск начала перемещения.] (Теперь все перемещаемые вниз стеки с j-ro по п-й перемещены в нужное место.) Будем последовательно уменьшать значение j с шагом 1 до тех пор, пока не выполнится одно из перечисленных ниже условий:

a) NEWBASECj] > BASE[j]: перейти к шагу R5;

b) j = 1: прервать вьшолнение алгоритма.