Абстрактные типы данных, модули и классы.

Прошу сообщать об ошибках, несуразностях, неясностях в изложении...

Абстрактные типы данных, модули и классы.

Тип данных - мы изначально понимаем, как множество возможных значений и набор операций над ними. Такое понимание ближе всего соответствует математическому понятию - алгебраическая модель.

Абстрактные типы данных - типы данных, являющиеся таковыми в содержательно-математическом смысле, но не присутствующие явно в конкретном языке программирования.

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

Пример 1. Для математиков простой, но достаточно полноценный, пример - понятие «комплексное число». Если речь идет о решении задач в поле комплексных чисел, то программисту приятно было бы иметь возможности - описать переменные типа Complex, использовать арифметические выражения этого типа... В стандартном Паскаль такой тип данных отсутствует.

Пример 2. Банковский счет. С этим понятием программист работает при решении задач о расчетно-денежных операциях в банке.

Значение типа «Банковский счет» может содержать, например, следующие сведения: номер счета, текущий остаток денежных средств на счете, владелец счета, даты открытия и закрытия счета...

Операции со значениями типа «Банковский счет»: открыть счет, закрыть счет, положить сумму на счет (увеличив этим остаток счета), снять сумму со счета, получить сведения о текущем остатке, о владельце счета...

Пример 3. Region (Word).

Стеки и очереди.

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

Пусть нас интересует процесс, который преобразует входной поток данных в выходной поток.

Какую-то часть данных входного потока процесс возможно «непосредственно» преобразует и посылает в выходной поток. Однако процесс может иметь «память», сохранять в ней некую часть информации из входного потока и использовать её для формирования данных выходного потока.

В каких-то ситуациях можно предполагать, что процесс имеет достаточную память для того, чтобы сначала запомнить весь входной поток, потом обработать информацию и по окончании обработки передать её в выходной поток. Однако сейчас нас интересует именно ситуация, когда входной поток трактуется как «потенциально неиссякаемый» источник данных, а память - как локальный (ограниченный) ресурс процесса.

Собственно преобразования нас не будут интересовать, поэтому мы будем считать, что входные данные просто передаются на выход. Больше нас будут интересовать возможности управлять формированием выходного потока, которые возникают благодаря наличию памяти(*). Возможности эти зависят от объема памяти и от способа доступа к её компонентам.

Объем памяти. Фактически мы не будем интересоваться количественной мерой объема, а ограничимся лишь качественной характеристикой: статическая память - количество компонентов ограничено сверху константой, динамическая память - количество компонентов ограничено сверху функцией от входа (обычно, функцией от количества поступивших компонентов входного потока). Статическая память в Паскаль может быть представлена простыми переменными базовых типов, записями или массивами, динамическая - файлами.

Способ доступа к компонентам памяти. В этом случае тоже, ограничимся лишь качественной классификацией способов доступа с точки зрения поставленного вопроса. Будем различать - прямой и последовательный доступ. Прямой доступ: Обозначение компонента ® Значение компонента. Обозначение компонента - «имя» (например, в случае простой переменной), «имя, уточненное селектором компонента» (указатель поля в записи, переменная с индексами)... Последовательный доступ - разновидности случаев, когда механизм доступа по сути задается средствами перечисления компонентов в некоей последовательности.

Важно осознавать, что по сути базовым является именно последовательный доступ, поскольку прямой подразумевает, что известно «обозначение компонента», например вычислимы индексы интересующего нас компонента массива... В задаче «Проверить имеется ли в массиве x[1..n] компонент x[i]=a» возможность прямого доступа к любому x[j] фактически не может быть использована по существу, нужна лишь возможность последовательно перечислить все компоненты... Если массив x[1..n] упорядочен, то возможность прямого доступа уже может играть важную роль, например в «дихотомическом поиске», но не решает проблему полностью, поскольку остается необходимость последовательного перечисления компонентов (пусть и не всех, пусть и в «нетиповом» порядке, отличном от порядка индексации компонентов). Если значения, хранимые в упорядоченном массиве, сгруппировать не в «массив», а в подходящее «поисковое дерево» с последовательным доступом к компонентам, то и при отсутствии прямого доступа можно сохранить применимость модифицированного варианта «дихотомического поиска».

Файлы, стеки и очереди можно трактовать как модели динамической памяти с последовательным доступом к компонентам, специфическим в каждом из этих трех случаев(*).

Стек - динамическая память с последовательным доступом типа «последние события вспоминаем в первую очередь» (LIFO - Last Input First Output - последний пришел первый ушел)(**).

Стек как абстрактный тип данных:

¨ множество возможных значений - (конечные) последовательности компонентов одинакового типа;

¨ набор операций:

· создать пустой стек - с семантикой, тождественной семантике оператора ReWrite;

· проверить стек на пустоту - на условие быть пустой последовательностью;

· добавить (компонент в конец последовательности), положить в стек - с семантикой, тождественной семантике оператора Write;

· удалить (последний компонент последовательности), вытолкнуть из стека - с семантикой, удовлетворяющей двум требованиям:

§ операция допустима Û стек непустой,

§ последовательность операций «добавить; удалить» не изменяет значения стека:

;

· посмотреть - возвращает значение последнего компонента последовательности (вершина стека), операция применима только к непустому стеку.

Очередь - динамическая память с последовательным доступом типа «события вспоминаем в порядке их поступления, но с задержкой» (FIFO - First Input First Output - первый пришел первый ушел). Такая память ещё известна, как «окно просмотра» («угол-поле зрения»).

(**)

Очередь как абстрактный тип данных:

¨ множество возможных значений - (конечные) последовательности компонентов одинакового типа;

¨ набор операций:

· создать пустую очередь - с семантикой, тождественной семантике оператора ReWrite;

· проверить очередь на пустоту - на условие быть пустой последовательностью;

· добавить (компонент в конец последовательности) в очередь - с семантикой, тождественной семантике оператора Write;

· удалить (первый компонент последовательности) из очереди - с семантикой, удовлетворяющей двум требованиям:

§ операция допустима Û очередь непустая,

§ «добавить(a); удалить»=«удалить; добавить(a)» при условии, что исходная очередь была непустая, т.е. обе последовательности операций дают одинаковый результат (при оговоренном условии):

;

· посмотреть - возвращает значение первого компонента последовательности (фронт очереди), операция применима только к непустой очереди.