Абстракция данных
То, какие новые типы данных необходимы, зависит от области применения программы. При реализации интерпретатора полезны стеки, а при определении пакета численных функций - матрицы, в банковской системе естественной абстракцией являются счета. В каждом конкретном случае абстракция данных состоит из набора объектов (стеков, полиномов, матриц и т.д.) и набора операций над ними. Например, матричные операции включают в себя сложение, умножение...
Новые типы данных должны включать в себя абстракции как через параметризацию, так и через спецификацию. Абстракция через параметризацию может быть осуществлена также как и для процедур, - использованием параметров там, где это имеет смысл. Абстракция через спецификацию достигается за счет того, что мы представляем операции как часть типа. Чтобы понять зачем, почему необходимы операции, посмотрим, что получится, если рассматривать тип просто как набор объектов. В этом случае, все, что необходимо сделать для реализации типа - это выбрать представление памяти для объектов. Тогда все программы могут быть реализованы в терминах этого представления. Однако, если представление изменяется, все программы, которые используют этот тип, должны быть изменены.
С другой стороны, предположим, что операции включены в определение типа следующим образом:
абстракция данных = <объекты, операции>
При этом потребуем, чтобы пользователи употребляли эти операции непосредственно, не обращаясь к представлению. Затем для реализации типа мы реализуем операции в терминах выбранного представления. При изменении представления нужно заново реализовывать только операции. Однако переделывать программы уже нет необходимости, так как они не зависят от представления, а зависят только от операций. Следовательно, мы получаем абстракцию через спецификацию.
Если обеспечено большое количество операций, отсутствие прямого доступа к представлению не будет создавать для пользователя трудностей, все что они хотят сделать с объектами, может быть сделано при помощи операций. Обычно имеются операции для создания и модификации объектов, а так же для получения информации об их значениях. Пользователи могут увеличивать набор операций определением процедур, но такие процедуры не должны использовать представление.
Абстракция данных - наиболее важный метод в проектировании программ. Выбор правильных структур данных играет решающую роль для создания эффективных программ. При отсутствии абстракций данных структуры данных должны быть определены до начала реализации модулей. Абстракция же данных позволяет отложить окончательный выбор структур данных до момента, когда эти структуры станут вполне ясны. Вместо того чтобы определять структуру непосредственно, мы вводим абстрактный тип со своими объектами и операциями. Затем можно осуществлять реализацию модулей в терминах этого абстрактного типа, решение же о конкретной реализации типа может быть принято позже, когда использование данных станет вполне понятным.
Абстракции данных полезны при модификации программ, когда предпочтительнее изменить структуру данных в реализации типа, не меняя при этом самой программы.
Для реализации типа данных мы выбираем представление для объектов и реализуем операции в терминах этого представления. Выбранное представление должно предоставлять возможности для довольно простой и эффективной реализации всех операций. Кроме того, если некоторые операции должны выполняться быстро, представление должно предоставлять и эту возможность. Заметим, что, вообще говоря, следует различать новый абстрактный тип и тип его представления. Предполагается, что с типом представления мы имеем дело только при реализации. Все, что мы можем делать с объектами абстрактного типа, - это применять к ним соответствующие данному типу операции.
Если абстракция данных определена, то она не отличается от встроенных типов и ее объекты и операции должны использоваться точно также как объекты и операции встроенных типов. Определенные пользователем типы могут также использоваться для представления других определяемых пользователем типов.
Теперь, когда мы немного уяснили, что же такое операции над абстрактными типами данных, дадим им некоторую классификацию.
