Курсовая работа: Распределение памяти

2. Переключение. Если мы определили, что ячейки, исходящие из текущей ячейки, уже все просмотрены, то обращаемся к полю back предыдущей ячейки. Если его значение равно L, а поле right этой ячейки содержит ненулевой указатель на какую-то ячейку C, то делаем С текущей ячейкой, в то время как статус предыдущей ячейки остаётся неизменным. Но значение поля back предыдущей устанавливаем равным R, а левый указатель в этой ячейке устанавливаем так, чтобы он указывал на прежнюю текущую ячейку. Чтобы отследить и сохранить путь от предыдущей ячейке, обратно к ячейке source, надо сделать так, чтобы указатель на ячейку С в поле right в предыдущей ячейке теперь указывал туда, куда указывал ранее её левый указатель. Эти изменения показаны на рис Б.

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), то есть практически закончили маркировку ячеек. В противном случае принимается решение либо отступить и остаться в состоянии отхода, либо переключится и перейти в состояние продвижения вперёд.

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

Previous

current

На рисунках старые указатели показаны сплошными линиями, а новые пунктирными.

Б) Переключение

previous
				current

В) Отход

previous
		current

Авторы используют следующие обозначения: PP - указатель/указатель; PA - указатель/атом и т.д. Кроме того можно заметить, что текст записанный ниже, это не вполне Паскаль-программа. Там не всё в порядке с оператором возврата из процедуры. Например return(false); это авторы делают для упрощения записи. Понимать этот оператор надо так:

Имя функции:=false;

Goto метка конца тела функции.

function blockleft (cell:celltype):boolean;

{Проверяет, является ли левое поле атомом или нуль указателем}

begin