Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 67

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 67)

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

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

Вся эта деятельность по определению объекта группа представляет собой разработку спецификации для абстрактного типа данных груплсе (то есть разработку необходимых атрибутов н операций). Реализация объектов типа группа происходит на следующем этапе конструирования программы. Выбор конкретного вида реализации для объектов этого типа должен быть сделан на основе типов данных, определенных в языке; также могут быть использованы другие абстрактные типы данных, например студена, преподаватель и т. д. Так, имя преподавателя может быть реализовано как строка длиной не более 10 символов или как целое число (идентификационный номер, присвоенный преподавателю), в то время как список зачисленных на курс студентов может быть представлен одномерным массивом целых чисел (идентификационные номера студентов).

Когда реализация типа данных группи определена, можно переходить к реализации операций над объектами этого типа, например, в виде подпрограмм, аргументами которых являются эти объекты. В американских университетах студенты могут сами выбирать курсы, которые они желают прсклушать, заранее записавшись на них. — Примеч. науч ред. Глава 6. Инкапсуляция 237 Если программа достаточно велика, над другими ее частями могут работать другие программисты; но теперь они также могут использовать тип данных группа, В их распоряжении находятся определенные ранее представления этого типа и подпрограммы, позволяющие манипулировать группами (объектами данных типа группа), используя спецификацию на подпрограммы, совершенно не заботясь о том, как они на самом деле реализованы.

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

Одна из задач, стоящих в наше врсмя персд разработчиком языка, — добиться того, чтобы различия между формами представления типов данных не были заметны для программиста, использующего эти типы данных при создании программ. Иначе говоря, синтаксические структуры языка, используемыс для работы с целочисленными переменными и с переменными типа группа, не должны различаться. Подобным же образом сигнатуры операций целочисленного сложения словить: целое х целое -~ целое и добавления студента в объект раздел курса добавить к курсу; сгудек1 х группа — + группадолжныобладатьпохожимсинтаксясом и иметь сопоставимую семантику.

Для того чтобы обеспечить программистам возмолгность создания новых типов данных и определения для них операций, существуют четыре механизма, 1. Структурированные данные, Практически во всех языках предусмотрена возможность создания сложных объектов данных из элементарных объектов, входящих в определение языка. Совокупность однородных объектов может быть определена как массив, список или множество. Совокупность неоднородных объектов можно создать при помощи записей. 2. Подпрограммы. Программист может создавать подпрограммы, реализующие желаемую функциональность нового типа данных; однако корректность использования этого типа почти целиком зависит от программиста, так как автоматическая поддержка со стороны языка программирования весьма незначительна.

3. Объявления типов. В языке предусмотрена возможность определения новых типов и операций над ними. Понятие абапрактиих типов данных (см. раздел 6.2), позволяющее программисту создавать новые типы данных, реализовано в языках типа Ада и С. 4. Наследование. Возможности определения новых типов данных и операций над ними значительно расширились благодаря использованию понятий объектно-ориентированного программирования и наследования. Кроме того, появилась возможность автоматической проверки правильности использования этих типов.

Концепция наследования рассматривается отдельно в главе 7. 238 Глава б. Инкапсуляция 6.1. Структурированные типы данных Структура данных — зто такой объект данных, который содержит другие объекты данных в качестве своих элементов или компонентов. В предыдущей главе мы рассматривали понятия объектов и типов данных на простых примерах элементарных типов данных. В этом разделе рассматриваются аналогичные вопросы, но уже в более сложном случае структур данных; в частности, обсуждаются такие важные типы данных, как массивы, записи, стеки, списки и множества. 6.1.1.

Структурированные объекты данных и типы данных Объект данных, сконструированный как совокупность других объектов данных (компонентов), называется структурированным объектом данных, илп структурой данных. Компонентом этой структуры может быть элементарный объект данных или структура данных (например, компонентом массива может быть число, а может быть и символьная строка, запись или другой массив), Многие вопросы и концепции, касающиеся структур данных, мы уже обсуждали при рассмотрении элементарных типов данных; иначе говоря, эти концепции одинаковы для структур и для элементарных типов.

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

Требуют особого внимания и вопросы распределения памяти при выполнении многих операций над структурами данных, которые не возникают в случае элементарных типов данных. 6.1.2. Спецификация типов структур данных Основные атрибуты структур данных следующие. 1. Количество компонентов, Структура данных может иметь фиксированный размер, если количество входящих в нее компонентов неизменно в течение времени жизни этой структуры, либо переменный размер, если зто количество динамически изменяется.

Для типов структур данных переменного размера обычно определены операции вставки н удаления компонентов, Массивы и записи обычно приводятся в качестве примеров типов структур данных фиксированной длины; стеки, списки, множества, таблицы и файлы являются примерами типов структур данных переменного размера. Программисты часто используют указагпели, позволяющие явным образом связывать объекты данных фиксированного размера для получения объектов данных переменной длины.

Б,1. Структурированные типы данных 239 Тип каждого компонента. Структура данных является однородной (гомогенной), если все ее компоненты одного типа. В противном случае она называется неоднородной (гетерогениой). Массивы, множества и файлы обычно однородны, в то время как записи и списки, как правило, неоднородны. Имени, используемые для выбираемых компонентов.

Тип, определяющий структуру данных, должен быть снабжен механизмом выборки, позволяющим идентифицировать и выбирать отдельные компоненты структуры данных Для массива именем отдельного компонента может являтъся целочисленный индекс или последовательность индексов; в случае записи именем обычно служит определенный программистом идентификатор; так же может определяться имя для компонента таблицы. В некоторых структурах данных, например в стеках и файлах, в каждый конкретный момент времени возможен доступ только к определенным компонентам (например, к верхнему или текущему элементу) и определены операции, при помощи которых можно изменять доступный в данный момент компонент.

Максимальное количество компонентов. Для структуры данных переменной длины, например для стека, может быть указан максимальный размер (максимальное число входящих компонентов). Организация компонентов. Наиболее распространенным видом организации компонентов в структуре данных является их простая линейная последовательность. Примерами структур данных с линейной организацией являются векторы (одномерные массивы), записи, стеки, списки и файлы. Но массив, список и запись, однако, обычно расширяются до многомерных форм: многомерные массивы, записи, компонентами которых являются другие записи, и списки, состоящие из списков.

Эти расширенные формы могут рассматриваться как отлельные типы пли просто как базовые последовательные типы, в которых компонентами являемся структуры данных того же типа. Например, двухмерный массив (матрицу) можно рассматривать как отдельный тип (как в языке РОСТКАХ й(1 з )) или как вектор векторов (как в С дО ) (й) ), то есть вектор, компонентами которого (строками или столбцами) являются также векторы. Для записей тоже имеются варианты — альтернативные множества компонентов, из которых только один включен в каждый объект данных этого типа. Операции над структурами данных Спецификация области определения и диапазона значения для операций над структурами данных задается почти так же, как и в случае элементаРных типов данных. Большое значение имеют следующие новые классы операций, специфические для структур данных.

Характеристики

Список файлов книги