B 1. [Начальная устан овка.] Установить Т¬Н-1, В ¬Н-1, Kl ¬М+1. Отметить все непосредственно доступные узлы и последовательно занести их адреса в стек (с помощью только что описанного действия).
B2. [Стек пуст?] Если Т = В, перейти к B5.
BЗ . [Взять из стека верхний элемент.] Установить К¬STACK [Т],
T ¬(T-l ) m od H.
B4 .[Исследо ват ь связи.] Если узел NODE(K ) - атом , то вериуться
К B2. В противном случае, если NODЕ(АL1NK(К)) не отмечен, то отметить его и занести ALINK (К) в стек. Аналогично, если NODE (BLINK (К)) не отмечен, то отметить его и занести REF (К) в стек. Вернуться к B2.
B5. [Прочесать.] Если K1>М, то алгоритм завершен. (Переменная К1 представляет наименьший адрес, откуда имеется возможность вновь выйти на узел, который следует отметить.) В противном случае, если NODE(KI) нe отмечен, увеличить К1 на 1 и повторить этот шаг. Если NODE (К1) отмечен, то установить К¬К1, увеличить К1 на 1 и перейти к B4.
Этот алгоритм можно улучшить, если не заносить в стек X, когда NODE (X) - атом.
Алгоритм B фактически становится алгоритмом А, когда Н = 1, и очевидно, эффективность его плавно возрастает с увеличением Н. К сожалению, алгоритм B не поддается точному анализу по тем же причинам, что и алгоритм А, и мы не в состоянии указать, при каком Н этот метод будет достаточно быстрым. В качестве правдоподобного, но не очень надежного можно назвать значение Н = 50, при котором алгоритм B применим для сбора мусора в большинстве случаев.
В алгоритме В используется стек, расположенный в последовательных ячейках памяти, которые расположены в памяти непоследовательно. Этот факт наводит на мысль, что в алгоритме мы могли бы организовать стек, каким-то образом разбросав его по той же самой области памяти» в которой собирается мусор. Это нетрудно сделать, если предоставить программе сбора мусора немного больше места, чтобы она могла "вздохнуть свободнее".
Будем считать, например, что все Списки представлены, за тем лишь исключением, что поле RЕF в каждом головном узле используется для сбора мусора, а не для счетчика ссылок. Тогда мы можем переработать алгоритм организовав стек в полях REF головных узлов.
Алгоритм D (Маркировка). Пусть дано множество узлов, имеющих следующие поля
MARK (одноразрядное поле,первоначально
нулевое в каждом узле),
ATOM (еще одно одноразрядное поле),
ALINK (указательное поле),
BLINK (указательное поле),
Когда ATOM = 0, поля ALINK и BLINK могут содержать L или указатель на другой узел того же формата; когда ATOM = 1, содержимое полей ALINK и BLINK несущественно для данного алгоритма.
Если задан указатель Р0, то этот алгоритм устанавливает 1 в поле MARK в узле NODE (Р0) и во всех других узлах, до которых можно добраться по цепочке указателей ALINK и BLINK и в которых ATOM = MARK = 0. В алгоритме используются три указательные переменные, Т, Q и Р, и связи при выполнении алгоритма могут быть временно изменены, но так, что после завершения алгоритма во всех полях ATOM, ALINK и BLINK восстанавливаются их прежние значения.
D1. [Начальная установка.] Установить Т¬L, Р¬Р0 (Далее в этом алгоритме переменная Т будет использоваться в двух смыслах: если Т¹L, то она указывает на вершину того, что, по существу, является стеком, а узел, на который указывает Т, некогда содержал связь, равную Р, вместо "искусственной" стековой связи, находящейся теперь в NODE (Т).)
D2. [Отметить.] Установить MARK (Р) ¬ 1.
DЗ, [Атом?] Если ATOM (Р) = 1, то перейти к Е6.
D4. [Вниз по ALINK.] Установить Q¬ALINK (Р). Если Q¹L и MARK (Q) = 0, то установить ATOM (Р) ¬1, ALINK (Р)¬Т, Т¬Р, P¬Q и перейти к D2. (Теперь поля ATOM и ALINK на время изменены и, следовательно, довольно радикально изменилась списочная структура в некоторых отмеченных узлах. Но в шаге D6 все будет восстановлено.)
D5. [Вниз по BLINK.) Установить Q¬BLINK (Р). Если Q¹L и MARK(Q)=0, то установить BLINK (Р)¬Т, Т¬Р, Р¬Q и перейти к D2.
D6. [Вверх.] (В этом шаге устраняются изменения связей, сделанные в шагах D4 или D5; значение АТОМ (Т) говорит о том, какую из связей ALINK (Т) или BLINK (Т) следует восстановить.) Если Т=L, алгоритм завершен. В противном случае установить Q¬Т. Если АТОМ (Q)=1, то установить ATOM (Q)¬0, Т¬ALINK (Q), ALINK(Q)¬P, P¬Q и вернуться к D5. Если ATOM (Q) = 0, то установить Т¬BLINK (Q), BLINК(Q)¬Р, Р¬Q и вернуться к D6.
Блок-схема алгоритма D показана на рисунке,
После После
ALINK BLINK
D1.Нач. D2. D3. D4. Вниз по D5. Вниз по D6. Вверх
установка Отметить Атом? ALINK Уже BLINK Уже
Да отмечен отмечен
Обратим внимание на то, что в шагах D4 и D5 искусственно изменяется списочная структура. Когда происходит возврат к предыдущему состоянию, поле ATOM говорит о том, какие из связей ALINK и BLINK содержат искусственные адреса. "Вложения", показанные в нижней части рисунка служат иллюстрацией того, что в алгоритме каждый неатомарный узел посещается три раза
Доказательство правильности алгоритма D можно построить, основываясь на индукции по количеству узлов, которые подлеж
Наверняка у вас есть товары или услуги, продажа которых приносит вам максимальную прибыль. Для быстрого старта в сети вам необходимо создание посадочной страницы (одностраничного сайта), на которой будет размещена информация о маржинальных товарах/услугах интернет магазина. За 8 лет опыта разработки конверсионных страниц мы выработали оптимальную структуру, которая позволит привлекать через landing page больше продаж. На такую структуру «одевается» ваш контент — фирменный стиль, тексты, фотографии, уникальные торговые предложения, после чего страница выходит в свет. Разработка лендинга и запуск в сети — до 7 рабочих дней. Стоит отметить, что в разработку самой посадочной страницы входит и написание копирайтером продающих текстов для вашего бизнеса, чтобы каждый посетитель страницы захотел совершить покупку именно у вас. Результат: качественно разработаная продающая посадочная страница, которая готова приносить вам новых клиентов.