Утилизация освободившихся элементов в многосвязных списках

Стандартные операции возвращения освободившегося элемента списка в пул свободных элементов не всегда дают эффект, если используются нелинейные многосвязные спи­ски.

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

Второй способ - метод сборки мусора (метод маркера). Если с каким-то элементом установлена связь, то однобито­вое поле элемента (маркер) устанавливается в "1", иначе - в "О". По сигналу переполнения ищутся элементы, у которых маркер установлен в ноль, т. е. включается программа сборки мусора, которая просматривает всю отведенную память и возвращает в список свободных элементов все элементы, не помеченные маркером.

13. Очередь и операции над ней при реализации со связными списками.

Указатель начала списка принимаем за указатель начала очереди F, а указатель R, указывающий на последний эле­мент списка - за указатель конца очереди.

1) Операция удаления из очереди (Remove(Q, X)).

Операция удаления из очереди должна проходить из ее начала.

If F = nil

then print “Очередь пуста”

Stop

endif

P = F

F = Ptr(P)

X = Info(P)

FreeNode(P)

return

2) Проверка очереди на пустоту. (Empty (Q))

If F = nil

then print “Очередь пуста”

Stop

endif

return

3) Операция вставки в очередь. (Insert(Q, X))

Операция вставки в очередь должна осуществляться к ее концу.

P = GetNode

Info(P) = x

Ptr(P) = Nil

Ptr(R)= P

R = P

Return