- •Рекурсивные определения и вычисления. Рекурсивные функции и процедуры. Модель исполнения рекурсивных подпрограмм компьютером. (Лек 1.1)
- •. Рекурсивные определения и вычисления
- •If b then e1 else e2 (где e1, e2 - выражения)
- •Накапливающие параметры. (Лек 1.2)
- •Абстрактная модель последовательности и линейные сд (стек, очередь, дек). (Лек 4)
- •Аксиомы
- •Реализация с массивом
- •Алгоритм перестроения дерева Хаффмана
- •Идеально сбалансированные бинарные деревья. (Лек 8).
Абстрактная модель последовательности и линейные сд (стек, очередь, дек). (Лек 4)
Абстрактные типы данных (АТД)
АТД – это тип данных (набор значений+ совокупность операций для них), доступ к которым осуществляется только через интерфейс.
Программу, которая использует АТД, называют клиентом, а программу со спецификацией этого типа данных – реализацией.
Клиенту доступен интерфейс.
Реализация отделена интерфейсом от клиента.
Клиент не может видеть реализацию через интерфейс – говорят, что интерфейс непрозрачен.
Потребителям (клиентам) нужно точно (но без ненужных подробностей) знать, как они могут использовать операции над СД и что они для этого должны делать.
Спецификация АТД предоставит эту информацию.
Спецификация АТД состоит из четырех разделов:
ТИПЫ
ФУНКЦИИ
АКСИОМЫ
ПРЕДУСЛОВИЯ
Замечание о степени формальности спецификации
Абстракция (модель) последовательности
Функции над последовательностями:
First, Last, Rest, Lead, Prefix, Postfix
Тип последовательности Sequence (El)
w = [ x1, x2, ..., xn] из элементов xi типа El
Для непустых последовательностей (w ∆):
First: Sequence (El) El; First (w) = x1;
Last: Sequence (El) El; Last (w) = xn;
Rest: Sequence (El) Sequence (El); Rest (w) = [ x2, ..., xn ];
Lead: Sequence (El) Sequence (El); Lead (w) = [ x1, x2, ...,xn1].
Сигнатуры функций – списки типов аргументов и результата
Функции Prefix и Postfix определены для любых последовательностей:
Prefix: El Sequence (El) Sequence (El);
Postfix: Sequence (El) El Sequence (El);
Prefix (x0, w) = [ x0, x1, x2, ..., xn ]; Postfix (w, x) = [ x1, x2, ..., xn, x ].
Функции First, Rest, Last, Lead селекторы, а функции Prefix и Postfix конструкторы типа Sequence (El)
стек (или магазин) Stack |
First, Rest, Prefix |
Last, Lead, Postfix |
|
очередь (англ. queue) |
First, Rest, Postfix |
Last, Lead, Prefix |
|
дек (от англ. deq = double-ended-queue, «очередь с двумя концами») |
First, Rest, Last, Lead, Postfix , Prefix |
Подструктуры Sequence (El)
СД |
Prefix |
Postfix |
First |
Last |
Rest |
Lead |
Null |
deq |
+ |
+ |
+ |
+ |
+ |
+ |
+ |
stack |
+ |
|
+ |
|
+ |
|
+ |
|
+ |
|
+ |
|
+ |
+ |
|
queue |
+ |
|
|
+ |
|
+ |
+ |
|
+ |
+ |
|
+ |
|
+ |
Стек. Формальные определения, спецификации, программные реализации. (Лек 4)
First = Top,
Rest = Pop,
Prefix = Push
Top верхушка стека,
Pop {up} вытолкнуть (вверх), Push {down} – втолкнуть, вжать (вниз)).
Формальная спецификация стека из элементов типа α (Stack of α Stack (α)).
Функциональная спецификация
(Non_null_stack - множество непустых стеков):
1) Create: Stack (α);
2) Null: Stack (α) Boolean;
3) Top: Non_null_stack (α) α;
4) Pop: Non_null_stack (α) Stack (α);
5) Push: α Stack (α) Stack (α)