 |
Создание абстрактного типа данных.
|
|
|
|
Чтобы лучше понять всю важность описаний абстрактных типов данных, исследуем глубже потенциальные последствия использования физической реализации в качестве основы описания объектов.
Удобным и хорошо изученным примером является описание объектов типа стек. Объект стек служит для того, чтобы накапливать и доставать другие объекты в режиме "последним пришел - первым ушел" ("LIFO"), элемент, вставленный в стек последним, будет извлечен из него первым. Стек повсеместно используется в информатике и во многих программных системах, в частности, компиляторы и интерпретаторы усыпаны разными видами стеков.
Этот рисунок иллюстрирует три наиболее популярных представления стеков. Для удобства ссылок дадим каждому из них свое имя:
- МАССИВ_ВВЕРХ: представляет стек посредством массива representation и целого числа count, с диапазоном значений от 0 (для пустого стека) до capacity - размера массива representation, элементы стека хранятся в массиве и индексируются от 1 до count.
- МАССИВ_ВНИЗ: похож на МАССИВ_ВВЕРХ, но элементы помещаются в конец стека, а не в начало. Здесь число, называемое free, является индексом верхней свободной позиции в стеке или 0, если все позиции в массиве заняты и изменяется в диапазоне от capacity для пустого стека до 0 для заполненного. Элементы стека хранятся в массиве и индексируются от capacity до free+1.
- СПИСОЧНОЕ: при списочном представлении каждый элемент стека хранится в ячейке с двумя полями: item, содержащем сам элемент, и previous, содержащем указатель на ячейку с предыдущим элементом. Для этого представления нужен также указатель last на ячейку, содержащую вершину стека.
Для представлений с помощью массивов МАССИВ_ВВЕРХ и МАССИВ_ВНИЗ команды увеличивают или уменьшают указатель на вершину (count или free) и присваивают x соответствующему элементу массива. Так как эти представления поддерживают стеки с не более чем capacity элементами, то корректные реализации должны содержать защищающие от переполнения тесты соответствующего вида:
|
|
|
if count " capacity then...
if free " 0 then...,
(на рисунке они для простоты опущены).
Для представления СПИСОЧНОЕ вталкивание элемента требует четырех действий:
- создания новой ячейки n (здесь оно выполняется с помощью процедуры Паскаля new, которая выделяет память для нового объекта);
- присваивания x полю item новой ячейки;
- присоединения новой ячейки к вершине стека путем присвоения ее полю previous текущего значения указателя last;
- изменения last так, чтобы он ссылался на только что созданную ячейку.
4.06.2016. Характеристика принципов объектно-ориентированного анализа: абстрагирование, инкапсуляция, наследование, полиморфизм, модульность, сохраняемость, параллелизм.
Объектно-ориентированный подход в программировании предлагает все, что входит в состав приложения, считать объектами, которые взаимодействуют друг с другом и с пользователем в соответствии с заданными в программе свойствами и поведением, выполняя необходимые функции приложения. Таким образом, любое приложение при данном подходе представляет собой набор взаимосвязанных объектов, реализующих необходимые функциональные требования, предъявленные к приложению.
Каждый стиль программирования имеет свою концептуальную базу. Каждый стиль требует своего умонастроения и способа восприятия решаемой задачи. Для объектно-ориентированного стиля концептуальная база - это объектная модель.
Она имеет четыре главных элемента:
· абстрагирование;
· инкапсуляция;
· модульность;
· иерархия и наследование.
Эти элементы являются главными в том смысле, что без любого из них модель не будет объектно-ориентированной.
|
|
|
Кроме главных, имеются еще три дополнительных элемента:
· типизация и полиморфизм;
· параллелизм;
· сохраняемость.
Называя их дополнительными, имеется в виду, что они полезны в объектной модели, но не обязательны.
Абстрагирование
Абстрагирование является одним из основных методов, используемых для решения сложных задач. Абстрагирование проявляется в нахождении сходств между определенными объектами, ситуациями или процессами реального мира, и в принятии решений на основе этих сходств, отвлекаясь на время от имеющихся различий. Абстрагирование концентрирует внимание на внешних особенностях объекта и позволяет отделить самые существенные особенности поведения от несущественных. Такое разделение смысла и реализации называется барьером абстракции, который основывается на принципе минимизации связей, когда интерфейс объекта содержит только существенные аспекты поведения и ничего больше.
Инкапсуляция
Абстракция объекта всегда предшествует его реализации, и после того, как решение о реализации принято, оно должно трактоваться как секрет абстракции, скрытый от большинства клиентов. Абстракция и инкапсуляция дополняют друг друга: абстрагирование направлено на наблюдаемое поведение объекта, а инкапсуляция занимается внутренним устройством. Инкапсуляция выполняется посредством сокрытия информации, то есть маскировкой всех внутренних деталей, не влияющих на внешнее поведение. Обычно скрываются и внутренняя структура объекта и реализация его методов. Инкапсуляция, таким образом, определяет четкие границы между различными абстракциями. Возьмем для примера структуру растения: чтобы понять на верхнем уровне действие фотосинтеза, вполне допустимо игнорировать такие подробности, как функции корней растения или химию клеточных стенок. Инкапсуляция - это процесс отделения друг от друга элементов объекта, определяющих его устройство и поведение; инкапсуляция служит для того, чтобы изолировать контрактные обязательства абстракции от их реализации.
Модульность
Разделение программы на модули позволяет уменьшить ее сложность. Однако гораздо важнее тот факт, что внутри модульной программы создаются множества хорошо определенных и документированных интерфейсов. В некоторых языках программирования, например, в Smalltalk, модулей нет, и классы составляют единственную физическую основу декомпозиции. В других языках, включая Object Pascal, C++, Ada, CLOS, модуль - это самостоятельная языковая конструкция. В этих языках классы и объекты составляют логическую структуру системы, они помещаются в модули, образующие физическую структуру системы. Это свойство становится особенно полезным, когда система состоит из многих сотен классов.
|
|
|
Иерархия и наследование
Всегда, кроме самых простых ситуаций, число абстракций в системе намного превышает умственные возможности человека. Инкапсуляция позволяет в какой-то степени устранить это препятствие, убрав из поля зрения внутреннее содержание абстракций. Модульность также упрощает задачу, объединяя логически связанные абстракции в группы. Но этого оказывается недостаточно. Значительное упрощение в понимании сложных задач достигается за счет образования из абстракций иерархической структуры. Иерархия - это упорядочение абстракций, расположение их по уровням.
Основными видами иерархических структур применительно к сложным системам являются структура классов (иерархия "is-a") и структура объектов (иерархия "part of"). Один из примеров иерархии - одиночное наследование. Наследование означает такое отношение между классами (отношение родитель/потомок), когда один класс заимствует структурную или функциональную часть одного или нескольких других классов (соответственно, одиночное и множественное наследование). Иными словами, наследование создает такую иерархию абстракций, в которой подклассы наследуют строение от одного или нескольких суперклассов. Часто подкласс достраивает или переписывает компоненты вышестоящего класса.
Полиморфизм
Типизация - это способ защититься от использования объектов одного класса вместо другого. Для введения определения полиморфизма, рассмотрим два вида типизации - статическое и динамическое связывание. Сильная и статическая типизация - разные вещи. Строгая типизация следит за соответствием типов, а статическая типизация определяет время, когда имена связываются с типами. Статическая связь означает, что типы всех переменных и выражений известны во время компиляции; динамическое связывание (называемое также поздним связыванием) означает, что типы неизвестны до момента выполнения программы. Концепции типизации и связывания являются независимыми, поэтому в языке программирования может быть: типизация - сильная, связывание - статическое (Ada), типизация - сильная, связывание - динамическое (C++, Object Pascal), или и типов нет, и связывание динамическое (Smalltalk). Язык CLOS занимает промежуточное положение между C++ и Smalltalk. Определения типов, сделанные программистом, могут быть либо приняты во внимание, либо не приняты.
|
|
|
Параллелизм
Есть задачи, в которых автоматические системы должны обрабатывать много событий одновременно. В других случаях потребность в вычислительной мощности превышает ресурсы одного процессора. В каждой из таких ситуаций естественно использовать несколько компьютеров для решения задачи или задействовать многозадачность на многопроцессорном компьютере. Процесс (поток управления) - это фундаментальная единица действия в системе. Каждая программа имеет, по крайней мере, один поток управления. Параллельная система имеет много таких потоков: век одних недолог, а другие живут в течение всего сеанса работы системы. Реальная параллельность достигается только на многопроцессорных системах, а системы с одним процессором имитируют параллельность за счет алгоритмов разделения времени. Кроме этого "аппаратного" различия, можно различать "тяжелую" и "легкую" параллельность по потребности в ресурсах. "Тяжелые" процессы управляются операционной системой независимо от других, и под них выделяется отдельное защищенное адресное пространство. "Легкие" сосуществуют в одном адресном пространстве. "Тяжелые" процессы общаются друг с другом через операционную систему, что обычно медленно и накладно. Связь "легких" процессов осуществляется гораздо проще, часто они используют одни и те же данные.
|
|
|
