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

В) Отход

td height=5>

previous
				current

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

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

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

function blockleft (cell:celltype):boolean;

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

begin

with cell do

if (pattern=pp) or (pattern=pa) then

if left<>nil then return(false);

return true;

end; {blockleft}

function blockright (cell:celltype): boolean;

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

begin

with cell do

if (pattern=pp) or (pattern=ap) then

if right<>nil then return(false);

end;{blockright}

function block (cell:celltype):boolean;

{проверяет, помечена ли ячейка и не содержит ли ненулевые указатели}

begin

if (cell.mark=true) or blockleft(cell) and blockright(cell) then

return true

else return false

end; {block}

procedure nrdfs; {помечает ячейки, доступные из ячейки source}

var

current, previous:^celltype;

begin {инициализация}

current:=source1^.right; {ячейка на которую указывает source1}

previous:=source1;

source1^.back:=r;

source1^.right:=source1;

source1^.mark:=true;

state1: {Движение вперёд}

if block (current^) then

begin {Подготовка к отходу}

current^.mark:=true;

goto state2;

end;

else

begin

{пометить и продвинуться вперёд}

current^.mark:=true;

if blockleft (current^) then

begin

{следование правому указателю}

current^.back:=r;

rotate (previous, current, current^.right);

{реализация изменения согласно схеме а}

goto state1

end

else

begin

{следование левому указателю}

current^.back:=L;

rotate(previous, current, current^.left);

{реализация изменения согласно схеме а}

goto state1;

end;

end;

state2: {Завершение отход или переключение}

if previous = current then goto state3 {завершение}

else if (previouse^.back=L) and (not blockright(previous^)) then

begin {переключение}

previous^.back:=R;

rotate(previouse^.left,current, previouse^.right);

{реализация изменений как на схеме б}

goto state1;

end

else if previous^.back=R then {Отход}

rotate(previous, previous^.right,current)

{реализация изменений как на схеме в}

else rotate(previous, previous^.left,current);

{реализация изменений вариант в, но поле left предыдущей ячейки включено в путь}

goto state2

end;

state 3: {Здесь необходимо вставить код для связывания непомеченных ячеек в список свободной памяти}

end; {nrdfs}

2 Задача 2. Пометка занятых ячеек памяти

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

В чём проблема.

Задача пометки упирается в задачу обхода списка. Если мы научимся обходить связный список, то проблема пометки решится сама собой. Задача же обхода произвольного списка имеет тривиальное решение. А именно, мы можем в каждом узле имеющем некоторое количество указателей ВПЕРЁД завести такое количество указателей НАЗАД и счётчик вхождений в данный узел. Следующий алгоритм будет решением задачи:

При вхождении в узел

Если есть неиспользованные указатели ВПЕРЁД

ТО перейти на узел по очередному указателю ВПЕРЁД

ИНАЧЕ

Если есть неиспользованные указатели НАЗАД

ТО перейти на узел по очередному указателю НАЗАД

Это очень общий алгоритм и мы не будем рассматривать его детально, так как он всё равно не годится из-за необходимости заводить большое количество дополнительных указателей. Вспомним, что ранее рассмотренный алгоритм (алгоритм ДОЙЧА) имеет смысл только потому, что он требует на два указателя лишь одного дополнительного поля. А стало быть проблема заключается в том, что нам нужен алгоритм не требующий больших ресурсов памяти для своей работы.

Небольшой предварительный анализ

Суть алгоритма Дойча в том, что в нём для запоминания пути назад используются уже имеющиеся указатели и одно маленькое поле back. Данное поле представляет собой однозначное двоичное число которым можно закодировать два числовых значения или что то же самое пронумеровать два указателя, поэтому алгоритм работает только с двоичным деревом. Очевидно, добавление ещё одного битового поля увеличит количество указателей которые можно пронумеровать.

Идея.

Я думаю, что намек уже понятен. Если мы заведем дополнительное поле размером в один байт, то это даст нам возможность пронумеровать 256 указателей.

Но это конечно ещё не всё. Понятно, что каждый из этих указателей может указывать как вперёд так и назад (Помните, что каждый из указателей используется как для запоминания пути вперёд так и пути назад). Возникает важный вопрос: как запомнить какой куда? Для ответа договоримся о следующем:

Во-первых, пусть множество указателей в каждом узле упорядочено линейно (сейчас не важно как именно это осуществляется, важно, что порядок есть и он линейный)

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

Алгоритм, как и алгоритм Дойча, должен уметь две вещи: во-первых запоминать путь назад и во вторых, определять в каждом узле указатель указывающий на узел в который необходимо перейти.

Общее описание алгоритма.

Для того, чтобы иметь возможность двигаться по сети узлов в двух направлениях нужно иметь два рабочих указателя. Назовём их ВПЕРЁД и ОБРАТНО. Указатель ВПЕРЁД содержит адрес узла в который необходимо перейти на следующем шаге, а указатель ОБРАТНО содержит адрес узла из которого Исполнитель вышел на предыдущем шаге. Сие означает, что на каждом шаге (в каждом узле) нужно выполнить операции определения этих адресов.

 Скачать реферат