Распределение памяти

Рефераты / Программирование, компьютеры и кибернетика / Распределение памяти

3. Отход. Если мы определили, что ячейки, исходящие из текущей ячейки, уже просмотрены, но значение поля back предыдущей ячейки равно R или L, а поле right содержит атом (Атомом авторы называют содержательное данное) или нуль указатель, значит мы уже просмотрели все ячейки, исходящие из предыдущей ячейки. Тогда осуществляется отход, при котором предыдущая ячейка становится текущей, а следующая

ячейка вдоль пути от предыдущей к ячейке source - новой предыдущей ячейкой. Эти изменения показаны на рисунке В

Нетрудно заметить, что каждый шаг, показанный на рисунке, можно рассматривать как одновременную циклическую перестановку трёх указателей. Чтобы выполнить эти модификации указателей, используется процедура rotate

Procedure rotate(var p1, p2, p3: ^celltype);

Var

Temp: celltype;

Begin

Temp:=p1;

P1:=p2;

P2:=p3;

P3:=temp;

End;

Теперь вернёмся к описанию нерекурсивной процедуры маркировки. Для неё возможны два состояния: продвижение вперёд, представленное меткой state1 и отход представленный меткой state2 и отход представленный меткой state2. Поначалу, а также в тех случаях, когда мы перешли на новую ячейку (либо в результате шага продвижения вперёд, либо в результате шага переключения), мы переходим в первое состояние. В этом состоянии мы пытаемся выполнить ещё один шаг продвижения вперёд и "отходим" или "переключаемся" лишь в том случае, если оказываемся заблокированными. Можно оказаться заблокированными по двум причинам: (1) ячейка к которой только, что обратились , уже помечена; (2)в данной ячейке отсутствуют ненулевые указатели. Оказавшись заблокированными, переходим во второе состояние - состояние отхода. Переход во второе состояние возможен в тех случаях, когда мы отходим или когда не можем оставаться продвижения вперёд, так как оказались заблокированными. В состоянии отхода проверяем, отошли ли обратно на ячейку source1. Как уже было сказано выше, мы распознаём эту ситуацию по выполнению условия previous=current; в этом случае переходим в состояние 3 (метка state3), то есть практически закончили маркировку ячеек. В противном случае принимается решение либо отступить и остаться в состоянии отхода, либо переключится и перейти в состояние продвижения вперёд.

А) движение вперёд