Стек. Функциональная спецификация

Стек — это структура с единственной читающей-записывающей головкой, последова­тельным доступом и неразрушающей записью. Чтение из стека, как и у очереди, разру­шающее (удаление!). Более строго, стеком называется множество некоторого переменного (возможно, нулевого) числа данных, на котором выполняются следующие операции:

Пополнение стека новыми данными; Проверка, определяющая пуст ли стек; Просмотр верхнего(самого нового) элемента, если он существует; Уничтожение последнего добавленного, но еще не уничтоженного элемента, если он есть.

1) Тип s_T или стек объектов типа т, характеризуется операциями: 2) Последовательность действий: 0

-> S_T

S_T -> {true, false}

S_T -> N

S_T x T -> S_T

S_T->S_T

S_T -> S_T

S_T ->0

Заносящая во вновь созданный пустой стек сначала элемент t1, а затем эл. t2, а затем извлекающая из нее два элемента инвертирует их порядок.

Стек. Логическое описание.

Самый свежий элемент стека, т. е. последний введенный и еще не уничтоженный играет особую роль; именно его можно рассмотреть или уничтожить. Этот элемент называет­ся верхушкой стека. Оставшуюся часть можно назвать телом стека и оно само является, но существу, стеком; если снять со стека верхушку, то тело превращается в сток. Таким образом, стек, как и очередь, является рекурсивной структурой данных и может быть описан рекурсивно как конкатенация элемента типа Т и некоторого стека s типа S_Т.Для обеспечения эффективной вычислимости необходим терминатор, ограничивающий глуби­ну рекурсии описания, роль которого, как в файлах и очередях, играет пустой стек:

type СТЕК-Т = (ПУСТО | НЕПУСТОЙСТЕК)

type НЕПУСТОЙСТЕК = (верхушка: Т; тело: СТЕК-Т) const int POOL_SIZE-100

Заметим, что рекурсивность описания может быть не только по глубине стека, но и по сложности типа его компонент Т: этот тип может быть произвольным, в том числе и рекурсивным, и даже стеком...

13 Стек. Физическое представление (массив).

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

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

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

Начало последовательности называется дном стека, конец последовательности, в который производится добавление элементов и их исключение - вершиной стека. Переменная, которая указывает на последний элемент последовательности в вершине стека - указатель стека. Операция добавления нового элемента (запись в стек) имеет общепринятое название Push (погрузить), операция исключения - Pop (звук выстрела). Операции Push и Pop являются безадресными в том смысле, что для их выполнения никакой дополнительной информации о месте размещения элементов не требуется (для этого достаточно указателя стека)

 

15 Линейный список. Функциональная спецификация. Линейный список — это представление в ЭВМ конечного упорядоченного динамиче­ского множества элементов типа Т. Точнее, это не множество, а мультимножество, т. к. в последовательности могут находиться элементы с одинаковыми значениями. Элементы этого множества линейно упорядочены, но порядок определяется не номерами (индексами), как в массиве, а относительным расположением элементов. Отношений порядка па этом множестве может быть не одно, а два, и тогда мы имеем дело с двусвязными (двусторонними или симметричными) списками. Для закольцевания списка необходимо доопределить в качестве следующего за. последним первый элемент списка, а в качестве предыдущего первому элементу — последний (голова указывает на хвост, а хвост на го­лову). Таким образом отношения порядка (предыдущий и /или следующий) становятся определенными для всех смежных (с точностью до закольцевания) пар элементов списка. Список обозначается простым перечислением элементов в заданном порядке в круглых скобках через запятую. Например, список l из пяти элементов типа T выглядит так: l = (t₁, t₂, t₃, t₄, t₅)

Полная функциональная спецификация двусвязного линейного списка L_T объектов типа T достаточно длинна:

СОЗДАТЬ: 0 -> L_T

ПУСТО: L_T -> boolean

ДЛИНА: L_T ->N

ПЕРВЫЙ: L_T -> T

ПОСЛЕДНИЙ: L_T -> T

СЛЕДУЮЩИЙ: L_T x T -> T

ПРЕДЫДУЩИЙ: L_T x T -> T

ВСТАВКА: L_T x T x T -> L_T

УДАЛЕНИЕ: L_T x T -> L_T

УНИЧТОЖИТЬ: L_T -> 0.

 

 

Свойства:

ПУСТО (СОЗДАТЬ) - true

ПУСТО (ВСТАВКА (l, t, t) — false ПРЕДЫДУЩИЙ(СЛЕДУЮЩИЙ(t)) = t СЛЕДУЮЩИЙ(11РЕДЫДУЩИЙ(t)) = t

l:— СОЗДАТЬ

l:— ВСТАВКА (l, t₂, t₂)

l: ВСТАВКА(l, t₂, t₁) ПЕРВЫЙ (l) = t₁ ПОСЛЕДНИЙ (l) = t₂

В левой части спецификации операции ВСТАВКА находится декартово произведение трех множеств: всевозможных списков, в которые должна быть проведена вставка, всех элементовПЕРЕДкоторыми необходимо ее произвести и различных вставляемых элементов.

16 Линейный список. Логическое описание. В отличие от очередей и стеков списковые структуры, хотя и не входят в стандартные языки программирования, но хорошо реализованы в альтернативных достаточно распро­страненных языках Лисп и Пролог. Более того, в языке Лисп это основная струк­тура.

Рассмотрим сначала как списки реализованы в Прологе. По определению, пустой спи­сок является списком, он обозначается символом [ ]. Функтор «.» (точка) образует новый список путем добавления нового элемента в начало исходного списка. Так список (t₁, t₂, t₃, t₄, t₅) может быть записан на Прологе как: .(t₁,.(t₂,.(t₃,.(t₄,.(t₅, [])))))

Логическое описание списков на Прологе базируется на встроенном предикате отде­ления головы списка «|» и реализованных на самом Прологе предикатах (программных единицах этого языка), более или менее соответствующих вышеприведенной функцио­нальной спецификации: проверка членства элемента или подсписка в заданном списке, вычисление длины, конкатенация, генерация перестановок элементов списка. Остальное может быть легко дописано на Прологе.

Примеры: [Tl, Т2, T₃ | Tail] * Отделение от списка трех первых элементов. В результате переменные Tl, Т2 и ТЗ получают значения, первых трех элементов списка, а 'Tail становится, остатком списка */

% Определение длин ы производится, рекурсивно length([], О).

length([_| Tail ], N):- length(Tail, N1), N is N1 + 1.