Главная Промышленная автоматика.

Листинг 12.1, Объявлениятипов ячеек type

atomtype = {один из подходящих типов данных для атомов,

желательно того же размера, что и указатели } patterns = (РР,РА,АР,АА); celltype = record mark: boolean; case pattern: patterns of

PP: (left: tcelltype; right: tcelltype); PA: (left: Tcelltype; right: atomtype); AP: (left: atomtype; right: tcelltype) ; АЛ: (left: atomtype; right: atomtype) ;

end;

Предполагаем, что имеется массив ячеек, занимающий большую часть памяти, и определенная совокупность переменных, которые представляют собой указатели на ячейки. С целью упрощения также предполагаем, что есть только одна переменная, называемая source (исходная), которая указывает на ячейку (хотя обобщение на случай многих переменных не представляет особой трудности). Таким образом, объявляем

source: Tcelltype;

memory: array Ц. .memorysize] of celltype;

Чтобы пометить ячейки, доступные переменной source, сначала отменяем пометку всех ячеек (независимо от их доступности или недоступности), просматривая массив memory (память) и устанавливая для поля mark значение false. Затем выполняем поиск в глубину по дереву ячеек, исходя из ячейки source и помечая все посещаемые ячейки. Посещенные ячейки - именно те, которые доступны из программы и, следовательно, используются программой. Затем просматриваем массив memory и добавляем в список свободного пространства все непомеченные ячейки. В листинге 12.2 представлена процедура dfs, выполняющая поиск в глубину; вызов dfs осуществляется процедурой collect (выбор), которая отменяет пометку всех ячеек, а затем маркирует доступные ячейки, вызывая dfs. Мы не показываем программу, создающую связанный список свободного пространства, из-за особенностей языка Pascal. Например, несмотря на то что можно было бы связать свободные ячейки с помощью либо всех левых, либо всех правых полей ячеек, поскольку предполагается, что указатели и атомы имеют одинаковый размер, но мы не имеем права заменять атомы на указатели в ячейках типа АА.

Листинг 12.2.Алгоритм маркировки доступныхячеек

(1) procedure dfs ( currentcell: Tcelltype );

{ Если текущая ячейка помечена, не делать ничего.

В противном случае она помечается и вызывается dfs для всех ячеек, на которые указывает текущая ячейка } begin

(2) with currentcell do

(3) if mark = false then begin

(4) mark true;

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



(5) if (pattern = PP) or (pattern = PA) then

(6) if left <> nil then

(7) dfs (left);

(8) if (pattern - PP) or (pattern = AP) then

(9) if right <> nil then

(10) dfs(right) end

end; { dfs }

<11)procedurecolIeсt/

i; integer;

begin

(12) for i := 1 to memorysize do

{ отмена маркировки всех ячеек }

(13) memoryii] .mark:= false;

(14) dfs(source); { пометить доступные ячейки }

(15) {в этом месте должен быть код для сбора доступных ячеек) end; { collect }

Сборка на месте

Алгоритм, представленный в листинге 12.2, страдает небольшим изъяном. В вычислительной среде с ограниченным объемом памяти у нас может не оказаться достаточно места ддя хранения стека, требуюшегося ддя рекурсивных вызовов dfs. Как уже указывалось в разделе 2.6, каждый раз, когда dfs вызывает сама себя, Pascal (иди любой другой язык, допускаюший рекурсию) создает ддя данного вызова dfs так называемую активационную запись. Вообше говоря, в такой активационной записи предусмотрено место ддя параметров и переменных, локальных по отношению к процедуре, причем ддя каждого вызова требуется свой собственный экземпляр активационной записи. Кроме того, в каясдой активационной записи нуясно указывать адрес возврата - место программы, в которое необходимо передать управление посде завершения рекурсивного вызова процедуры.

При вызове процедуры dfs требуется дишь место ддя параметра и адреса возврата. Однако есди бы вся память была связана в цепочку, исходяшую из ячейки source (и, сдедоватедьно, количество активных вызовов dfs в какой-то момент времени стадо равным длине этой цепочки), ддя стека активационных записей могло бы потребоваться значительно больше пространства, чем имеется в памяти. И есди бы свободного пространства не оказалось, было бы невозможно выполнять маркировку освободившихся ячеек.

К счастью, разработан замечательный алгоритм, известный под названием алгоритма Дойча - Шорра - Уэйта (Deutsch - Schorr - Waite), который выполняет маркировку на месте. Читатель должен проверить сам, что последовательность ячеек, на которых был выполнен (но еше не завершен) вызов dfs, действительно образует путь от source до ячейки, на которой был сделан текуший вызов dfs. Поэтому можно воспользоваться нерекурсивной версией процедуры dfs, а вместо стека активационных записей, предназначенного ддя отслеживания пути ячеек от source до ячейки, анализируемой в данный момент, можно использовать поля указателей вдоль этого пути, которые и будут формировать этот путь. Таким образом, каждая ячейка на этом пути, за исключением последней, содержит иди в поде left (влево), иди в поде right (вправо) указатель на ее предшественника - ячейку, расположенную ближе к ячейке source. Мы опишем алгоритм Дойча - Шорра - Уэйта, исподь-зуюший еше одно однобитовое поде, которое называется back (назад). Поде back имеет перечисдимый тип (L, R) и говорит о том, какое из полей, left иди right, указывает на предшественника. Далее покажем, как информацию, хранящуюся в поде back,



можно включить в поле pattern (шаблон), чтобы избежать использования дополнительного места в ячейках.

Эта новая процедура, выполняюшая нерекурсивный поиск в глубину (назовем ее nrd/s), использует указатель current (текуший) для указания на текушую ячейку, а указатель previous (предыдуший) - для указания на предшественника текущей ячейки. Переменная source указывает на ячейку sourcel, которая содержит указатель только в своем правом поле. До выполнения маркировки в ячейке sourcel значение поля back устанавливается равным R, а ее правое поле указывает на самого себя. Па ячейку, на которую обычно указывает sourcel, теперь указывает ячейка current, а на sourcel указывает ячейка previous. Операция маркировки прекрашается в том случае, когда указатели current - previous, это может произойти лишь при условии, если обе ячейки current и previous указывают на sourcel, т.е. когда уже просмотрена вся структура.

source

soured

а. Структура ячеек

ГП 3

1 111 i

L i.

source

soureel

current

previous

6. Ситуация, когда ячейка (4) текущая

Рис. 12.3. Использование указателей для представления обратного пути к ячейке source

Пример 12.3. Па рис. 12.3, а показан возможный вариант структуры ячеек, исхо-дяших из ячейки source. Если выполнить поиск в глубину этой структуры, мы посетим ячейки (1), (2), (3) и (4) - именно в такой последовательности. На рис. 12.3, б показано изменение указателей, выполненное в момент, когда ячейка (4) является текущей. Здесь показаны значения поля back, а поля mark и pattern не отображены. Текуший путь от ячейки (4) к ячейке (3) осушествляется через указатель ячейки previous, дальнейший путь к ячейкам (2) и (1) и обратно к ячейке sourcel показан пунктирными указателями. Например, у ячейки (1) значение поля back равно L, поскольку на рис. 12.3,а поле left этой ячейки содержало указатель на ячейку (2), а

Это название - сокращение от nonrecurslve depthflrstseach (нерекурсивный поиск в глубину). - Прим. перев.

Такое несколько неуклюжее решение связано с особенностями языка Pascal.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 [111] 112 113 114 115 116 117 118 119 120 121 122 123

0.0024