Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 112
Текст из файла (страница 112)
Пример Предположим, что необходимо создать абстрактный тип данных для стека, который имеет следующие абстрактные операции. сгеаге(маей) Создает и, возможно, инициализирует объект типа 5(ас)с. дезггоу(згас)5) Освобождает память, занимаемую стеком. етр(у(5(ас)с) Предикатная (булевская) функция, которая возвращает значение "истина", если стек пуст, и "ложь" — в противном случае.
риза(5)ас)г,е!ешепт) Помешает указанный элемент а указанный стек. рор(зшсй) Удаляет верхний элемент из указанного стека. гор(5)аск) Возвращает копию верхнего элемента из указанного стека. Заметим, что некоторые реализации абстрактных типов данных не предусматривают операций создания и разрушения объектов. Например, простое определение переменной некоторого абстрактного типа данных может неявно создавать соответствующую структуру данных и инициализировать ее. Клиент типа маей может содержать следующую последовательность операторов: сгеате(ЯТК1)з рез)1(ЯТК1, СОЬОК1]) рие)т(ЯТК1, ООЬОК2]г хх(пес енсу(ЯТК1)) КЬеп ТЕМР := тор(ЯТК1)г Предположим, что первоначальная реализация абстракции стека представляет его в виде следующих один за другим элементов массива.
Позднее, из-за проблем с управлением памятью, связанных с массивами, стек стали представлять в виде связного списка. Поскольку была использована абстракция данных, такие изменения можно вносить в код, определяющий тнп згасх, но при этом не нужно вносить изменения в код ни одного Глава 10. Абстрактные типы данных .- ента. использующего абстракцию стека. В частности, приведенную выше последова-: ьность операторов можно оставить без изменения.
Конечно, изменение в протоколе сбой операции может потребовать изменения кодов клиентов. Если бы стек не был реализован как абстрактный тип данных, такие изменения при:-: л бы к изменению кодов клиентов. использующих тип жасй, в соответствии с новым --. г вставлением стека. Предположим, что операции со стеком были реализованы в языке э как операции с массивами. Изменение представления стека с массива на связный . -'сок потребовало бы модификации кодов клиентов, которые теперь должны были бы ч задавать указатели, а не имена массивов в качестве параметров процедур, реализуюгх операции со стеками.
В этом случае протоколы некоторых операций должны быть :ченены, следствием чего является внесение изменений в коды клиентов. В заключение отметим, что цель абстракции данных — дать возможность программам . -эеэелять типы данных, с которыми можно обращаться как со встроенными типами. 10.4. Вопросы разработки типов Средства определения абстрактных типов данных в языке программирования должны : 5еспечивать создание синтаксических единиц, которые могут инкапсулировать определе- е типа и подпрограмм, выполняющих абстрактные операции.
Должна существовать воз". жность делать имя типа и заголовки подпрограмм видимыми в клиентах абстракции. Это -:зволяет клиентам объявлять переменные абстрактного типа и манипулировать их значе-,.ями. Несмотря на то что имя типа должно быть видимым извне, его определение должно . ыть скрыто.
То же самое зачастую относится и к определениям подпрограмм — заголовки сэлжны быть видимыми, но тела подпрограмм должны быть скрыты. Существует очень мало общих встроенных операций, которые можно выполнять с .оъектами абстрактных типов, в отличие от операций, предусмотренных определением -ипа. Просто не существует большого количества операций, которые можно было бы —.Рименить к широкому кругу возможных абстрактных типов данных. К таким операциям "тносятся присваивания.
а также проверки равенства и неравенства. Если язык не позволяет пользователям перегружать операцию присваивания, то она должна быть встроенной. Проверки равенства и неравенства в одних случаях должны быть заранее определены. а в других — нет. Например, если тип — указатель, то равенство может означать равенство указателей, но пользователь может пожелать, чтобы такое равенство означало "эвенство структур, адреса которых хранятся в этих указателях. Некоторые операции нужны для большинства абстрактных типов данных, но, поскольку они не универсальны, разработчик типа должен определить их сам.
К таким операциям относятся итераторы, конструкторы и деструкторы. Итераторы обсуждались в ;лаве 7. Конструкторы используются лля инициализации частей вновь создаваемых объектов. Деструкторы используются лля освобождения областей динамической памяти, которые мокнут быть заняты частями объектов абстрактного типа. Как указывалось ранее, абстрактный тип данных инкапсулирует отдельный тип данных и связанные с ним операции. Языки Сопсатепг Разса1 (Вг1псЬ Напзеп, 1975), Бвайдайс (ОоИЬег8 апд йоЬзоп, 1983), Сьь и )ага непосредственно поддерживают абстрактные типы данных.
Альтернативой этому является поддержка более общих конструкций, которые определяют любое количество сущностей, каждую из которых по отдельности можно сделать видимой вне содержащего ее модуля. Этот подход реализован в языках программирования азу 10.4. Вопросы разработки типов Мо<!ц1а-2 и А<!а. Мы назвали эти конструкции инлиисузя<1идии, Инкапсуляции являются не абстрактными типами ланных, а их обобщениями, и в этом качестве инкапсуляции можно использовать для определения абстрактных типов данных.
Отметим основные вопросы разработки типов с помощью инкапсуляции. Во-первых, слелуез ди ограничивать множество типов, которые могут быть абстрактными? Такое ограничение имеет некоторые преимушества. В частности, если абстрактными могут быть лишь указатели. то при разработке программ можно избежать больших проблем, связанных с повторной компиляцией.
С другой стороны, некоторые исследователи считают зто очень сильным ограничением, поскольку оно имеет существенные недостатки. Второй вопрос разработки типов — можно ли параметризовать абстрактные типы двинь<к?> Например, если язык программирования поддерживает параметризованные типы данных. можно разработать абстралтные типы данных для очерелей, которые состоят из элементов любого скалярного типа. Параметризованные абстрактные типы данных обсуждаются в разлеле 10.6. В заключение отметим, что существуют также вопросы, связанн>ле с тем.
как именно осуществляется управление доступом к данным, и как такое управление определяется. 10.5. Примеры абстракции данных в разных языках В этом разделе рассматривается поддержка абстракции данных в языках программирова><ия б!М1Л.А 67, А<!а, С++ и Зача. 10.5.1.
Классы в языке $1М$вв.А 67 Первые средства лля прямой поддержки абсзракции данных в языке. хотя и не полносгью соответствующие нашему определению, появились в конструкции классов в языке ЫМНВА 67. 10.5. 1. $. Инкапсуляция Определение класса в языке ЯМАМ!.А 67 является описанием типа. Экземпляры !объекты класса! созлаются в динамической памяти по запросу пользовательской программь>. и поступ к ним можно получить только через указатели. Таким образом, объекты класса являются динамическими. Общая синтаксическая форма определения класса в языке ЯМ<11.А 67 имеет вид: о1авв с1аез газе; Ьеазп объявления переменных класса опоелеления подпрограмм класса -- раздел кола класса ел<1 с' .. в г>а>ае> Ращсл определения класса. содержащий код, выполняется только один раз, в момент создания объекта.
Он служит конструктором класса и в этом качестве используется для инициализашш переменных, определенных в классе. Вклад языка б!МУ!.А 67 в разработку абстракции данных заключается в возможности инкапсуляции. которой обладает конструкция класса. Интересно, что значимость Глава 1О. Абстрактные типы данных 436 с войс гва классов не признавалась еше несколько лет после завершения ра ~)хаботки с)Ч(п.А 67.
Важность абстракции ланных не осознавалась до конца 70-х илов. ' О.5. 1.2.Сокрытие информации :.ременные. объявленные в классе языка ЯМЫ.А 67. не скрыты от клиентов. котом юют обьекты этого класса. Доступ к таким переменным можно получить через .7:ции. выполняемые подпрограммами класса, или непосредственно по их именам. . зрушает требование сокрытия информации при определении абстрактного типа ' х. поскольку существует много способов доступа к сущностям класса. В результа...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
