Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Организация операций 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) 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 с.) |