Организация операций Getnode, Freenode и утилизация освободившихся элементов 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Организация операций Getnode, Freenode и утилизация освободившихся элементов



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

Если у функциональных списков разный формат, то надо создавать свободный список каждого функционального списка.

Количество элементов в свободном списке должно быть определено задачей, которую решает программа.

Как правило, свободный список создается в памяти машины как стек.

Создание (GetNode) нового элемента эквивалентно выборке элемента из свободного стека, а операция FreeNode - добавлению в свободный стек освободившегося элемента.

Пусть необходимо создать пустой список по типу стека с указателем начала списка - AVAIL. Рассмотрим функции, которые позволят создавать пустой элемент списка и освобождать элемент из списка.

Операция P = GetNode

Для реализации операции GetNode необходимо указателю сгенерированного элемента присвоить значение указателя начала свободного списка, а указатель начала свободного списка перенести к следующему элементу.

Перед этим надо проверить, есть ли элементы в списке. Пустота свободного списка (Avail = nil), эквивалентна переполнению функционального списка.

If Avail = Nil

then Print “Переполнение”

Stop

else P = Avail

Avail = Ptr(Avail)

endif

return

 

Операция FreeNode (P)

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

FreeNode(P)

Ptr(P) = Avail

Avail = P

return

 

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

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

Метод счетчиков

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

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

Метод маркера

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

 

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

Операции с очередью, применимые к спискам.

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

Проверка очереди на пустоту

Empty(Q)

If F = nil

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

Stop

endif

return

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

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

Remove(Q)

If F = nil

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

Stop

endif

P = F

F = Ptr(P)

X = Info(P)

FreeNode(P)

return

 

Операция вставки в очередь

Insert(Q, x)

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

Insert(Q, x)

P = GetNode

Info(P) = x

Ptr(P) = Nil

Ptr(R)= P

R = P

return

 



Поделиться:


Последнее изменение этой страницы: 2017-02-05; просмотров: 411; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 34.228.239.171 (0.004 с.)