В этой статье детально изучается абстракция данных, как способ повышения модульности программы. Абстракция данных позволяет возвести стены между программой и структурами данных. При решении задач нужно выполнять разные операции над данными, поэтому возникает необходимость определить абстрактные типы данных (АТД). На примере простых абстрактных типов данных в статье демонстрируются преимущества ATI вцелом. Это позволяет сосредоточиться решении отдельной задачи, не отвлекаясь на другие. Таким образом, программу легче писать, читать и модифицировать. Модульность программы позволяет локализовать ошибки, а также исключить избыточный код.
При этом следует сосредоточивать внимание на том, что именно делает модуль, а не на том, как он это делает. Это позволяет разрабатывать функции в относительной изоляции друг от друга, обращая внимание лишь на то, что они делают, и не вникая в детали их внутреннего устройства. Принцип сокрытия информации (information hiding) подразумевает не только утаивание деталей внутреннего устройства модуля от других частей программы, но и невозможность доступа к ним извне. Сокрытие информации ассоциируется со стенами, возведенными между разными частями программы. Эти стены предотвращают перепутывание данных.
Оно невелико и не позволяет увидеть детали внутреннего устройства функции, но достаточно широкое, чтобы обмениваться через него данными. Например, в функцию сортировки через это окошко можно передать массив и получить его обратно уже упорядоченным. То, что функция получает извне, и то, что она возвращает внешнему миру, описывается в терминах ее спецификации, или контракта (contract) в нем указывается, что именно делает функция, и какие условия для этого должны выполняться.
В общих чертах, их можно свести к трем разновидностям:
1. Добавление (add) данных в набор.
2. Удаление (remove) данных из набора.
3. Проверка (ask question) данных, содержащихся в наборе.
Упорядоченный массив совместно с алгоритмом бинарного поиска можно рассматривать в качестве абстрактного типа данных, позволяющего решить эту задачу.
Тогда — и только тогда — можно приступать к реализации операций над структурой данных. Если операции реализованы правильно, их можно применять и в остальной части программы, т.е. считается, что условия контракта выполнены.
В спецификациях указывается, что делают операции АТД, но не описывается их реализация
Для того чтобы лучше понять разницу между абстрактными типами данных и структурами данных, рассмотрим морозильное устройство. На его вход поступает вода, из которой получается либо охлажденная вода, либо измельченный лед, либо кубики льда, в зависимости от того, на какую кнопку нажать. Кроме того, имеется индикатор, который загорается, если льда внутри нет. Это устройство представляет собой пример абстрактного типа данных. Аналогом данных является вода, а операциями — охладить, измельчить. На этом уровне проектирования нас не интересует, как именно морозильное устройство выполняет указанные операции. Если мы хотим измельчить лед, незачем нам вдаваться в технические тонкости устройства холодильника, если он и так работает правильно. Таким образом, описав функции, выполняемые морозильным устройством, операции, использующие измельченный лед, можно применять, не зная, как он получается.
Морозильное устройство для получения охлажденной воды, измельченного льда и кубиков льда.
Однако в конце концов кто-то же должен создать морозильное устройство. Как все-таки получается измельченный лед? Сначала нужно сделать кубик льда, а затем измельчить его с помощью двух стальных роликов, или разбить молотком на мелкие кусочки. Для этого можно придумать много способов.
Несмотря на то что владельца холодильника не интересуют технические подробности, он или она хотят, чтобы устройство работало как можно эффективнее. Те же самые понятия используют при выборе структуры данных для реализации абстрактного типа данных в языке С. Даже если вы не реализуете АТД сами, а используете уже готовые компоненты, вы как и человек, купивший холодильник, должны стремиться, крайней мере, к эффективности.
Таким образом, внутренний механизм устройства не только скрыт от пользователя, но и недоступен. Кроме того, механизм выполнения одной операции недоступен для другой.
Такой модульный подход имеет преимущества. Например, операцию мельчить можно усовершенствовать, изменив ее модуль. Кроме того, можно добавить новую операцию, подключив к машине новый модуль и оставив первые три операции без изменения. Таким образом, в холодильнике применяется и абстракция, и принцип сокрыт информации.
Этот процесс напоминает использование торговых автоматов. Вы нажимаете кнопки и получаете нечто в ответ. Внешний дизайн автомата подсказывает вам, что нужно делать, так же как спецификации АТД описывают операции и их предназначение. Раз вы пользуетесь подсказками автомата, технические детали его внутреннего устройства становятся для вас безразличными. Аналогично, согласившись на доступ к данным только через операции АТД, можно забыть о любых изменениях структур данных, реализующих этот АТД.
На следующих страницах мы покажем, как использовать абстрактные типы данных для отделения операций над данными от реализации этих операций. Для этого мы рассмотрим несколько примеров АТД.
Описанные все списки, в которых манипуляции над элементами производились либо в начале, либо в конце, либо и в начале, и в конце, не соответствуют реальному списку продуктов. Нам может понадобиться доступ к любому элементу списка. Это значит, что мы можем просматривать элемент, находящийся на позиции и, удалять его или вставлять новый элемент в эту позицию. Эти операции являются частью абстрактного типа данных под названием список (list).
Операции над абстрактным списком:
— Создать пустой список.
— Уничтожить список.
— Определить, пуст ли список.
— Определить количество элементов в списке.
— Вставить элемент в указанную позицию списка.
— Удалить элемент, находящийся в указанной позиции списка.
— Просмотреть (извлечь) элемент, находящийся в указанной позиции списка.
Абстрактный список представляет собой упорядоченный набор элементов, каждый из которых имеет свой номер.
Если поведение абстрактного типа описано правильно, можно приступать к разработке приложения, манипулирующего его данными, пользуясь лишь названиями операций и не вникая в детали их реализации. Допустим, к примеру, что мы хотим вывести на экран элементы списка. Несмотря на то что стены, отделяющие реализацию абстрактного списка от остальной программы, скрывают способ его хранения, можно написать функцию displayList, операции, определенные для этого типа.
Поскольку абстрактный список реализован правильно, функция displayList будет успешно выполнена. В этом случае функция retrieve сможет извлечь любой элемент списка, так как значение параметра position всегда корректно, следовательно, аргументом success можно пренебречь.
Если удаление выполнено успешно, функция remove присвоит параметру success значение true. Проверив значение этого параметра, функция replace приступит к вставке, только если удаление действительно произошло. Операции абстрактного типа данных можно применять, не вникая в детали их реализации
В обоих примерах, описанных ве, мы не вникали в детали реализации списка. Нам было все равно, хранятся ли его записи в массиве
или в другой структуре данных. Это относится и к созданию программ на языке С. Кроме того, поскольку операции iInsert и replace не зависят от реализации типа, их содержание никак не изменяется, именно поэтому такие операции часто называют турникетными. Итак, функционирование абстрактного типа данных можно определять независимо от его реализации. Имея такую спецификацию и ничего не зная о том, как именно будет реализован АТД, можно приступать к разработке приложения, применяющего операции АТД для доступа к его данным.