Лекция Реализация стеков с помощью односвязных списков. Утилизация освободившихся элементов в многосвязных списках
 Скачать 21.5 Kb.
|
Лекция 7. Реализация стеков с помощью односвязных списков. Утилизация освободившихся элементов в многосвязных списках.План: Реализация стеков с помощью односвязных списков Применение операций Getnode, Freenode и удаление освободившихся элементов Удаление освободившихся элементов в многосвязных списках 1. Реализация стеков с помощью односвязных списков Любой односвязный список может рассматриваться в виде стека. Однако список по сравнению со стеком в виде одномерного массива имеет преимущество, так как заранее не задан его размер. Стековые операции, применимые к спискам Чтобы добавить элемент в стек, надо в алгоритме заменить указатель Lst на указатель Stack (операция Push(S, X)). P = GetNode Info(P) = X Ptr(P) = Stack Stack = P Проверка стека на пустоту (Empty(S)) If Stack = Nil then Print “Стек пуст” Stop Выборка элемента из стека (POP(S)) P = Stack X = Info(P) Stack = Ptr(P) FreeNode(P) Реализация на Паскале: Стек Вместо указателя Lst используется указатель Stack Процедура Push (S, X) procedure Push(var Stack: PNode; X: Integer); var P: PNode; begin New(P); P^.Info:=X; P^.Next:=Stack; Stack:=P; end; Проверка на пустоту (Empty) function Empty(Stack: PNode): Boolean; begin If Stack = nil then Empty:=True Else Empty:=False; end; Процедура Pop procedure Pop(var X: Integer; var Stack: PNode); var P: PNode; begin P:=Stack; X:=P^.Info; Stack:=P^.Next; Dispose(P); end; Операции с очередью, применимые к спискам. Указатель начала списка принимаем за указатель начала очереди F, а указатель R, указывающий на последний элемент списка - за указатель конца очереди. Операция удаления из очереди (Remove(Q, X)). Операция удаления из очереди должна проходить из ее начала. P = F F = Ptr(P) X = Info(P) FreeNode(P) Проверка очереди на пустоту. (Empty(Q)) If F = Nil then Print “Очередь пуста” Stop Операция вставки в очередь. (Insert(Q, X)) Операция вставки в очередь должна осуществляться к ее концу. P = GetNode Info(P) = X Ptr(P) = Nil Ptr(R)= P R = P Реализация на Паскале: procedure Remove(var X: Integer; Fr: PNode); var P: PNode; begin New(P); P:=Fr; X:=P^.Info; Fr:=P^.Next; Dispose(P); end; function Empty(Fr: PNode): Boolean; begin If Fr = nil then Empty:=True Else Empty:=False; end; procedure Insert(X: Insert; var Re: PNode); var P: PNode; begin New(P); P^.Info:=X; P^.Next:=nil; Re^.Next:=P; end; 2. Применение операций Getnode, Freenode и удаление освободившихся элементов Для более эффективного использования памяти компьютера (для исключения мусора, то есть неиспользуемых элементов) при работе его со списками создается свободный список, имеющий тот же формат полей, что и у функциональных списков. Если у функциональных списков разный формат, то надо создавать свободный список каждого функционального списка. Количество элементов в свободном списке должно быть определено задачей, которую решает программа. Как правило, свободный список создается в памяти машины как стек. При этом создание (GetNode) нового элемента эквивалентно выборке элемента свободного стека, а операция FreeNode - добавлению в свободный стек освободившегося элемента. Пусть необходимо создать пустой список по типу стека (рис. 1) с указателем начала списка - AVAIL. Разработаем процедуры, которые позволят создавать пустой элемент списка и освобождать элемент из списка.  Рис. 1. Создание пустого списка Операция GetNode Разработаем процедуру, которая будет создавать пустой элемент списка с указателем Р. Для реализации операции GetNode необходимо указателю сгенерированного элемента присвоить значение указателя начала свободного списка, а указатель начала перенести к следующему элементу. P = Avail Avail = Ptr(Avail) Перед этим надо проверить, есть ли элементы в списке. Пустота свободного списка (Avail = Nil), эквивалентна переполнению функционального списка. If Avail = Nil then Print “Переполнение” Stop Else P = Avail Avail = Ptr(Avail) Endif Операция FreeNode При освобождении элемента Nod(P) из функционального списка операцией FreeNode(P), он заносится в свободный список. Ptr(P) = Avail Avail = P 3. Удаление освободившихся элементов в многосвязных списках Стандартные операции возвращения освободившегося элемента списка в пул свободных элементов не всегда дают эффект, если используются нелинейные многосвязные списки. Первый способ утилизации - метод счетчиков. В каждый элемент многосвязного списка вставляется поле счетчика, который считает количество ссылок на данный элемент. Когда счетчик элемента оказывается в нулевом состоянии, а поля указателей элемента находятся в состоянии nil, этот элемент может быть возвращен в пул свободных элементов. Второй способ - метод сборки мусора (метод маркера). Если с каким-то элементом установлена связь, то однобитовое поле элемента (маркер) устанавливается в “1”, иначе - в “0”. По сигналу переполнения ищутся элементы, у которых маркер установлен в ноль, т. е. включается программа сборки мусора, которая просматривает всю отведенную память и возвращает в список свободных элементов все элементы, не помеченные маркером. Контрольные вопросы Зачем были введены двусвязные списки? 2. В чем разница в операциях, производимых над односвязными и двусвязными списками? 3. Какой список является более удобным в обращении, односвязный или двусвязный? 4. Как можно представить двусвязный список с помощью односвязных списков? 5. Операции над двусвязными списками. 6. Список и стек – общее и различия. 7. Какие операции, производимые над очередью, можно производить над списками? 8. Почему можно производить все эти операции над списками? 9. Для чего предназначены операции Getnode и Freenode? 10. Что означает AVAIL? |