Любой односвязный список может рассматриваться в виде стека. Однако односвязный список имеет преимущество по сравнению со стеком, реализованном на одномерном массиве, так как заранее не задан его размер.
Стековые операции, применимые к спискам
1). Чтобы добавить элемент в стек, надо в алгоритме вставки в начало списка заменить указатель Lst на указатель S вершины стека (операция Push(S, X)).
P = GetNode
Info(P) = x
Ptr(P) = S
S = P
return
2) . Проверка стека на пустоту (Empty(S))
if S = Nil
then print “ Стек пуст ”
return
endif
return
3) . Выборка элемента из стека (POP(S))
Empty(S)
P = S
X = Info(P)
S = Ptr(P)
FreeNode(P)
return
Операции с очередью, применимые к спискам.
Указатель начала списка принимаем за указатель начала очереди F, а указатель R, указывающий на последний элемент списка - за указатель конца очереди.
Рис. 3.5’
1). Алгоритм операции проверки очереди на пустоту (Empty(Q)) следующий:
If F = nil
then print “ Очередь пуста ”
return
endif
return
2). Операция удаления из очереди должна проходить из ее начала. Алгоритм операции удаления из очереди (Remove(Q)) следующий:
If F = nil
then print “ Очередь пуста ”
return
endif
P = F
F = Ptr(P)
X = Info(P)
FreeNode(P)
return
3). Операция вставки в очередь должна осуществляться к ее концу. Алгоритм операции вставки в очередь. (Insert(Q, X)) следующий:
P = GetNode
Info(P) = x
Ptr(P) = Nil
Ptr(R)= P
R = P
return
Организация операций Getnode, Freenode и утилизация освободившихся элементов
Для более эффективного использования памяти компьютера (для исключения мусора, то есть неиспользуемых элементов) при работе его со списками создается свободный список, имеющий тот же формат полей, что и у функциональных списков.
Если у функциональных списков разный формат, то надо создавать свободный список каждого функционального списка.
Количество элементов в свободном списке должно быть определено задачей, которую решает программа. Как правило, свободный список создается в памяти машины как стек. При этом создание (GetNode) нового элемента эквивалентно выборке элемента свободного стека, а операция FreeNode - добавлению в свободный стек освободившегося элемента.
Пусть нам необходимо создать пустой список по типу стека (рис. 3.6) с указателем начала списка - AVAIL.
Необходимы функции, которые позволят нам создавать пустой элемент списка и освобождать элемент из списка.
3.3.1 Операция P=GetNode.
Разработаем функцию, которая будет создавать пустой элемент списка с указателем Р.
Для реализации операции GetNode необходимо указателю сгенерированного элемента присвоить значение указателя начала свободного списка, а указатель начала перенести к следующему элементу. При этим надо проверить, есть ли элементы в списке. Пустота свободного списка (Avail = Nil), эквивалентна переполнению функционального списка.
If Avail = Nil
then Print “ Переполнение ”
return
else P = Avail
Avail = Ptr(Avail)
endif
return
Операция FreeNode(P).
При освобождении элемента из функционального списка, он заносится в свободный список.
Ptr(P) = Avail
Avail = P
return
Дата: 2019-12-10, просмотров: 235.
