Структуры данных и алгоритмы (1021739), страница 93
Текст из файла (страница 93)
Поле back имеет перечислимый тип (L, R) и говорит о том, какое из полей, left или right, указывает на предшественника. Далее покажем, как информацию, хранящуюся в поле back,346ГЛАВА 12. УПРАВЛЕНИЕ ПАМЯТЬЮможно включить в поле pattern (шаблон), чтобы избежать использования дополнительного места в ячейках.Эта новая процедура, выполняющая нерекурсивный поиск в глубину (назовем ееnrdfs1), использует указатель current (текущий) для указания на текущую ячейку, ауказатель previous (предыдущий) — для указания на предшественника текущей ячейки.
Переменная source указывает на ячейку sourcel, которая содержит указатель только в своем правом поле.2 До выполнения маркировки в ячейке sourcel значение поляback устанавливается равным R, а ее правое поле указывает на самого себя. На ячейку,на которую обычно указывает sourcel, теперь указывает ячейка current, а на sourcelуказывает ячейка previous. Операция маркировки прекращается в том случае, когдауказатели current — previous, это может произойти лишь при условии, если обе ячейкиcurrent и previous указывают на sourcel, т.е. когда уже просмотрена вся структура.(2)source\ •/\///,W^'sourcelШ1Л \(3)а(ьТ•са. Структура ячеекsourcesourcelЬcurrent\w/•сpreviousб. Ситуация, когда ячейка (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), а1Это название — сокращение от nonrecursive depth-first seach (нерекурсивный поиск в глубину).
— Прим. перев.Такое несколько неуклюжее решение связано с особенностями языка Pascal.12.3. АЛГОРИТМЫ ЧИСТКИ ПАМЯТИ ДЛЯ БЛОКОВ ОДИНАКОВОГО РАЗМЕРА347теперь используется для хранения части пути. Теперь поле left ячейки (1) указываетназад, а не вперед по пути; однако мы восстановим этот указатель, когда поиск вглубину перейдет с ячейки (2) обратно на ячейку (1). Аналогично, в ячейке (2) значение поля back равно R, а правое поле указывает в обратном направлении на ячейку(1), а не вперед на ячейку (3), как это показано на рис. 12.3, а.
ППри осуществлении поиска в глубину выполняются три основных шага.1.Продвижение вперед. Если мы определили, что текущая ячейка имеет один или несколько ненулевых указателей, нужно перейти на первый из них, т.е. следовать указателю в поле left или, если такового не имеется, — указателю в поле right. Теперьнадо преобразовать ячейку, на которую указывает текущая ячейка, в "новую" текущую, а "старую" текущую ячейку — в предыдущую. Чтобы облегчить поиск обратного пути, нужно сделать так, чтобы указатель, которому мы только что следовали, теперь указывал на прежнюю предыдущую ячейку. Эти изменения показаны нарис. 12.4,а в предположении, что отслеживался левый указатель.
На этом рисунке"старые" указатели показаны сплошными линиями, а "новые" — пунктирными.2. Переключение. Если мы определили, что ячейки, исходящие из текущей ячейки,уже все просмотрены (или, например, текущая ячейка может содержать толькоатомы, или может быть уже помеченной), то обращаемся к полю back предыдущей ячейки. Если его значение равно L, а поле right этой ячейки содержит ненулевой указатель на какую-то ячейку С, тогда делаем С текущей ячейкой, в товремя как статус предыдущей ячейки остается неизменным. Но значение поляback предыдущей ячейки устанавливается равным R, а левый указатель в этойячейке устанавливаем так, чтобы он указывал на прежнюю текущую ячейку.Чтобы отследить и сохранить путь от предыдущей ячейки обратно к ячейкеsource, надо сделать так, чтобы указатель на ячейку С в поле right предыдущейячейки теперь указывал туда, куда указывал ранее ее левый указатель.
Все этиизменения показаны на рис. 12.4, б.3. Отход. Если мы определили, что ячейки, исходящие из текущей ячейки, уже просмотрены, но значение поля back предыдущей ячейки равно R или L, а поле rightсодержит атом или нуль-указатель, значит, мы уже просмотрели все ячейки, исходящие из предыдущей ячейки. Тогда осуществляется отход, при котором предыдущая ячейка становится текущей, а следующая ячейка вдоль пути от предыдущей ячейки к ячейке source — новой предыдущей ячейкой. Эти изменения показаны на рис. 12.4, в (здесь значение поля back предыдущей ячейки равно R).Нетрудно заметить, что каждый шаг, показанный на рис. 12,4, можно рассматривать как одновременную циклическую перестановку трех указателей. Например, нарис.
12.4, а мы одновременно заменили (previous, current, current^.left) на (current,current^.left, previous) соответственно. В данном случае важно подчеркнуть одновременность этих действий: местоположение ячейки current^.left изменится только приприсваивании нового значения current. Чтобы выполнить эти модификации указателей, используется процедура rotate (циклический сдвиг), показанная в листинге 12.3.Листинг 12.3.
Процедура модификации указателейprocedure rotate ( var pi, p2, рЗ : tcelltype ).;jvartemp: tcelltype;begintemp:= pi;pl:= p2;p2: = p3;p3 : = tempend; { rotate }348•;яЯГЛАВА 12. УПРАВЛЕНИЕ ПАМЯТЬЮа. Продвижение впередV/ "-previousв. ОтходРис. 12.4. Три основных шага поиска в глубинуТеперь вернемся к написанию нерекурсивной процедуры маркировки nrdfs. Этапроцедура представляет собой один из тех запутанных процессов, которые прощевсего понять, если при их написании использовать метки и операторы безусловногоперехода goto. Для процедуры nrdfs возможны два "состояния": продвижение вперед, представленное меткой state 1, и отход, представленный меткой state2.
Поначалу, а также в тех случаях, когда мы перешли на новую ячейку (либо в результатешага продвижения вперед, либо в результате шага переключения), мы переходим впервое состояние. В этом состоянии мы пытаемся выполнить еще один шаг продвижения вперед и "отходим" или "переключаемся" лишь в том случае, если оказываемся заблокированными. Можно оказаться заблокированными по двум причинам: (1)ячейка, к которой только что обратились, уже помечена; (2) в данной ячейке отсутствуют ненулевые указатели. Оказавшись заблокированными, переходим во второесостояние — состояние отхода.Переход во второе состояние возможен в тех случаях, когда мы отходим или когда не можем оставаться в состоянии продвижения вперед, так как оказались заблокированными.
В состоянии отхода проверяем, отошли ли обратно на ячейку sourcel.Как уже было сказано выше, мы распознаем эту ситуацию по выполнению условияprevious = current; в этом случае переходим в состояние 3 (метка stateS), т.е. практически закончили маркировку ячеек. В противном случае принимается решение либоотступить и остаться в состоянии отхода, либо переключиться и перейти в состояниепродвижения вперед.12.3. АЛГОРИТМЫ ЧИСТКИ ПАМЯТИ ДЛЯ БЛОКОВ ОДИНАКОВОГО РАЗМЕРА349Код процедуры nrdfs показан в листинге 12.4.
В этой программе используютсяфункции blockleft (блокировка слева), blockright (блокировка справа) и block(блокировка), которые проверяют, содержит ли левое или правое поле ячейки (илиоба эти поля) атом или нуль-указатель. Функция block проверяет также, не маркирована ли ячейка., . • • ' . .••.:'.;'•: а. . . . ..:•!•>•:'.'. f ' . ''•'....'.. В,;:, i?,Листинг 12.4.
Нерекурсивный алгоритм маркировки ячеекfunction blockleft ( cell: celltype ): boolean;{ проверяет, является ли левое поле атомом или нуль-указателем }beginwith cell doif (pattern = PP) or (pattern = PA) thenif left <> nil then return(false);return(true)end; { blockleft }•ifunction blockright ( cell: celltype ): boolean;{ проверяет, является ли правое поле атомом или нуль-указателем }beginwith cell doif (pattern = PP) or (pattern = AP) thenif right <> nil then return(false);return(true)end; { blockright }function block ( cell: celltype ): boolean;{ проверяет, не помечена ли ячейка и не содержит линенулевые указатели }beginif (cell.mark = true) or blockleft(cell) and blockright(cell)thenreturn(true)elsereturn(false)end; { block }procedure nrdfs; { помечает ячейки, доступные из ячейки source }varcurrent, previous: Tcelltype;begin { инициализация }current:= sourcelt.right;{ ячейка, на которую указывает sourcel }previous:= sourcel; { теперь previous указывает на sourcel }sourcelt.back:= R;sourcelt.right:= sourcel; { sourcel указывает сама на себя }sourcelt.mark:= true;statel: { продвижение вперед }if Jblocfctcurrent?) then begin { подготовка к отходу }currentt.mar/c:= true;goto state2endelse begin { пометить и продвинуться вперед }сиггentt.таrk:= true;if blocJcleft( current?) then begin350ГЛАВА 12.
УПРАВЛЕНИЕ ПАМЯТЬЮ{ следование правому указателю }current^.back:= R;rotate (previous, current, current^. right) ;( реализация изменений как на рис. 12.4,а,но следуя правому указателю }goto statelendelse begin { следование левому указателю }current!. back:= L;rotate (previous, current, current^.left) ;{ реализация изменений как на рис. 12.4,а }goto statelendend;state2: { завершение, отход или переключение }if previous = current then { завершение }goto state3else if (previousf.back:= L) andnot blockright(previousT) then begin { переключение }previoust.back:= R;rotate(previous^ .left, current, previous?, right) ;{ реализация изменений как на рис.
12.4,6 }goto statelendelse if previoust.back = R then { отход }rotate (previous, previoust. right, current){ реализация изменений как на рис. 12.4,в }else { previousT. bacJc = L }rotate (previous, previous?, left, current);{ реализация изменений как на рис. 12.4,в,но поле left предыдущей ячейки включено в путь }goto state2end;state 3: { здесь необходимо вставить код для связываниянепомеченных ячеек в список сврбодно^ памяти )end; { nrdfs }Алгоритм Дойча — Шорра — Уэйта без использования поля backВозможно, хотя и маловероятно, что дополнительный бит, используемый в ячейках для поля back, может вызвать потребность в дополнительном байте или даже дополнительном машинном слове для хранения содержимого этого поля. Но оказывается, что без этого дополнительного бита вполне можно обойтись, по крайней мере припрограммировании на языке, который, в отличие от языка Pascal, позволяет использовать биты поля pattern для целей, отличных от тех, для выполнения которых ониизначально предназначались.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
