Начальные значения: Данные, используемые для инициализации объекта

Абстрактные типы данных

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

Пример 1

1. Программа учета для малого предприятия сопровождает инвентаризационную информацию. Каждый элемент в описи представлен записью данных, которая включает идентификационный номер этого элемента, текущий уровень запаса, ценовую информацию и информацию упорядочивания. Набор операций по обработке списка обновляет различные информационные поля и инициирует переупорядочивание запаса, когда его уровень падает ниже определенного порога. Абстракция данных описывает какой-либо элемент как запись, содержащую серию информационных полей и операций, необходимых менеджеру компании для инвентаризационного сопровождения. Операции могут включать изменение значения Stock on Hand (имеющийся запас) при продаже этого товара, изменение Unit Price (цены за единицу) при использовании новой ценовой политики и инициализации упорядочивания при падении уровня запаса ниже уровня переупорядочивания (Reorder Level).

Данные

 

Identification

Stock on Hand

Unit Price

Reorder Level

Операции

UpdateStockLevel

AdjustUnitPrice

Reorderltem

2. Игровая программа моделирует бросание набора костей. В этой разработке игральные кости описываются как абстрактный тип данных, которые включают число бросаемых костей, сумму очков в последнем бросании и список со значениями очков каждой кости в последнем бросании. Операции включают бросание костей (Toss), возвращение суммы очков в одном бросании (Total) pi вывод очков для каждой отдельной кости (DisplayToss).

Данные

N		diceTotal			Dice List

Операции

Toss

Total

DisplayToss

ADT – формат

Для описания ADT используется формат, который включает заголовок с именем ADT, описание типа данных и список операций. Для каждой операции определяются входные (input) значения, предоставляемые клиентом, предусловия (preconditions), применяемые к данным до того, как операция может быть выполнена, и процесс (process), который выполняется операцией. После выполнения операции определяются выходные (output) значения, которые возвращаются клиенту, и постусловия (postconditions), указывающие на любые изменения данных. Большинство ADT имеют инициализирующую операцию (initializer), которая присваивает данным начальные значения. В среде языка C++ такой инициализатор называется конструктором (constructor). Мы используем этот термин для упрощения перехода от ADT к его преставлению в C++.

 

 

ADT - формат

ADT ADT_Name

Данные

Описание структуры данных

Операции

Конструктор

Начальные значения: Данные, используемые для инициализации объекта

Процесс: Инициализация объекта

Операция₁

Вход: Данные от клиента

Предусловия: Необходимое состояние системы перед выполнением операций

Процесс: Действия, выполняемые с данными

Выход: Данные, возвращаемые клиенту

Постусловия: Состояние системы после выполнения операций

Операция₂

Операция_n

Конец ADT

 

Пример 2

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

ADT Dice

Данные

Число костей в каждом бросании – целое, большее либо равное 1. Целое значение, содержащее сумму очков всех костей в последнем бросании. Если N – число бросаемых костей, то число очков находится в диапазоне от N до 6N, Список, содержащий число очков каждой кости в бросании. Значение любого элемента списка находится в диапазоне от 1 до 6.

Операции

Конструктор

Начальные значения: Число бросаемых костей

Процесс: Инициализировать данные, определяющие число костей в каждом бросании

Toss

Вход: Нет

Предусловия: Нет

Процесс: Бросание костей и вычисление общей суммы очков

Выход: Нет

Постусловия: Общая сумма содержит сумму очков в бросании, а в списке находятся очки каждой кости

DieTotal

Вход: Нет

Предусловия: Нет

Процесс: Находит значение элемента, определяемого как сумма очков в последнем бросании

Выход: Возвращает сумму очков в последнем бросании

Постусловия: Нет

Display Toss

Вход: Нет

Предусловия: Нет

Процесс: Печатает список очков каждой кости в последнем бросании

Выход: Нет

Постусловия: Нет

Конец ADT Dice

2. Окружность определяется как набор точек, равноудаленных от точки, называемой центром. С целью графического отображения абстрактный тип данных для окружности включает как радиус (radius), так и положение центра. Для измеряющих приложений абстрактному типу данных требуется только радиус. Мы разрабатываем Circle ADT и включаем операции для вычисления площади (area) и длины окружности (circumference). Этот ADT применяется в следующем разделе для иллюстрации описания класса C++ и использования объектов при программировании приложений.

Circumference  Area

ADT Circle

Данные

Неотрицательное действительное число, определяющее радиус окружности.

Операции

Конструктор

Начальные значения: Радиус окружности

Процесс: Присвоить радиусу начальное значение

Area

Вход: Нет

Предусловия: Нет

Процесс: Вычислить площадь круга

Выход: Возвратить площадь круга

Постусловия: Нет

Circumference

Вход: Нет

Предусловия: Нет

Процесс: Вычислить длину окружности

Выход: Возвратить длину окружности

Постусловия: Нет

конец ADT Circle

2. Классы C++ и абстрактные типы

Язык C++ поддерживает определяемый пользователем тип классов для представления абстрактных типов данных. Класс состоит из членов (members), которые включают значения данных и операции по обработке этих данных. Операции также называются методами (methods), поскольку они определяют методы доступа к данным. Переменная типа класса называется объектом (object). Класс содержит две отдельные части. Открытая (public) часть описывает интерфейс, позволяющий клиенту манипулировать объектами типа класса. Открытая часть представляет ADT и позволяет клиенту использовать объект и его операции без знания внутренних деталей реализации.

Класс

private: Данные-члены: переменная1, переменная2 Внутренние операции

public: Конструктор Операция1 Операция2

Закрытая (private) часть содержит данные и внутренние операции, помогающие в реализации абстракции данных. Например, класс для представления ADT Circle содержит один закрытый член класса – radius. Открытые члены включают конструктор и методы вычисления площади круга и длины окружности

Circle Класс

private: radius

public: Конструктор Area Circumference

Инкапсуляция и скрытие информации

Класс инкапсулирует (encapsulates) информацию, связывая вместе члены и методы и обращаясь сними как с одним целым. Структура класса скрывает реализацию деталей и тщательно ограничивает внешний доступ как к данным, так и к операциям. Этот принцип, известный как скрытие информации (information hiding), защищает целостность данных.

Класс использует свои открытую и закрытую части для контроля за доступом клиентов к данным. Члены внутри закрытой части используются методами класса и изолированы от внешней среды. Данные обычно определяются в закрытой части класса для предотвращения нежелательного доступа клиента. Открытые члены взаимодействуют с внешней средой и могут использоваться клиентами.

Например, в Circle-классе radius является закрытым членом класса, доступ к которому может осуществляться только тремя методами. Конструктор присваивает начальное значение члену radius. Каждый из других методов использует radius. Например, area=р*raduis². Здесь методы являются открытыми членами класса, которые могут вызываться всеми внешними единицами программы.

Передача сообщений

В приложении доступ клиентов к открытым членам какого-либо объекта может быть реализован вне этого объекта. Доступом управляют главная программа и подпрограммы (master control modules), которые наблюдают за взаимодействием между объектами. Управляющий код руководит объектом для доступа к его данным путем использования одного из его методов или операций. Процесс управления деятельностью объектов называется передачей сообщений (message passing). Отправитель передает сообщение получающему объекту и указывает этому объекту выполнить некоторую задачу.

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

3. Объекты в приложениях C++

Абстрактный тип данных реализует общее описание данных и операций над данными. Класс C++ обычно вводится сначала объявлением этого класса без определения функций-членов. Это известно как объявление класса (class declaration) и является конкретным представлением ADT. Фактическое определение методов дается в реализации класса (class implementation), отдельной от объявления.

Реализация классов C++ и использование объектов иллюстрируются следующей завершенной программой, которая определяет стоимость планировки бассейна. Программа объявляет Circle класс и показывает, как определяются и используются объекты. В коде содержатся определения открытого и закрытого разделов класса и используются функции C++ для определения операций. Главная программа – это клиент, который объявляет объекты, и затем использует их операции для выполнения вычислений. Главная программа отвечает за передачу всех сообщений в приложении.

Приложение: класс Circle

Объекты Circle используются для описания плавательного бассейна и дорожки вокруг него. С помощью методов Circumference (вычисление длиныокружности) и Area (вычисление площади круга) мы можем вычислить стоимость бетонирования дорожки и строительства ограды вокруг бассейна. К нашему приложению применяются следующие условия.

Строительные правила требуют, чтобы плавательный бассейн окружала бетонная дорожка (темная область на следующем рисунке) и вся территория была огорожена. Текущая стоимость ограды составляет $3,50 за погонный фут, а стоимость бетонирования - $0,5 за кв. фут. Приложение предполагает, что ширина дорожки, окружающей бассейн, составляет 3 фута и что клиент указывает радиус круглого бассейна, В качестве результата приложение должно определить стоимость строительства ограды и дорожки при планировании бассейна.

PoolRim

Мы объявляем объект Circle с именем Pool, описывающий площадь плавательного бассейна. Второй объект - PoolRim, - это объект Circle, включающий как бассейн, так и окружающую дорожку. Конструктор вызывается при определении объекта. Для объекта Pool клиент задает радиус в качестве параметра, и затем использует радиус плюс 3 фута для определения объекта PoolRim.

Для вызова операции класса задайте имя объекта, за которым следует точка (.) и операция. Например, Pool.Area() и Circumference() вызывают операции Circle для Pool.

Ограда располагается вдоль наружной стороны PoolRim. Вызовите операцию вычисления окружности PoolRim.Circumference() для вычисления стоимости ограды.

FenceCost = PoolRim.Circumference() * 3.50

Площадь бетонной поверхности определяется вычитанием площади Pool из внешней площади PoolRim.

ConcreteCost = (PoolRim.Area() - Pool.Area()) * 0.5

Разработка объектов

В этой книге разрабатываются структуры данных с классами и объектами. Мы начинаем с классов, которые определяются простыми данными-членами и операциями класса. Для более сложных структур классы могут содержать члены класса, которые сами являются объектами. Результирующие классы, созданные посредством композиции (composition), имеют доступ к функциям-членам в составляющих объектах. Использование композиции объектов расширяет понятия инкапсуляции и скрытия информации и обеспечивает повторное использование кода. Объектно-ориентированные языки также позволяют классу быть порожденным из других классов путем наследования (inheritance). Это дает возможность разработчику создавать новые классы как усовершенствования других классов и повторно использовать код, который был разработан ранее. Наследование является фундаментальным средством объектно-ориентированного программирования на языке C++. Эта тема вводится формально в главе 12 и используется для разработки и реализации улучшенных структур данных.

Объекты и композиция

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

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

Линия образуется из точек, а две точки определяют линию. Последний факт используется для создания модели отрезка (line segment), который определяется своими конечными точками р! и р2 [Рис. 1.1 (А)].

Базовая точка	1	2	3	4	5
1			Р(3,1)
2

Прямоугольник – это четырехсторонняя фигура, чьи смежные стороны встречаются в прямых углах. Для рисования прямоугольник определяется двумя точками, которые отмечают верхний левый угол (ul) и нижний правый угол (lr) рамки.

 

(А) Отрезок L(p1, р2)    (В) Прямоугольник R(ul, Ir)

 

Класс Point		Класс Line		Класс Rectangle
private: х у координаты		private: Point p1, p2		private: Point ul, Ir
public: Конструктор, Draw, GetX, GetY		public Конструктор, Draw		public: Конструктор, Draw

Мы используем эти факты для создания классов Point, Line и Rectangle. Члены в классах Line и Rectangle являются объектами типа Point. Композиция – это важный инструмент в создании классов с объектами из других классов. Заметьте, что каждый класс имеет метод Draw для отображения рисунка на поверхности рисования. Класс Point содержит функции-члены для доступа к координатам х и у точки.

Пример 3

Определите геометрический объект, задавая фигуру, за которой следуют имя объекта и параметры для указания объекта.

 

1) Point Р (1,3 ); // объявляет объект point (1,3)

2) Point pl(4,2), р2(5,1);

Line 1(р1,р2); // линия: от (4,2) до (5,1)

3) Point pl(4,3), р2(6,4);

Rectangle r(pl,p2); // прямоугольник: от (4,3) до р2(6,4)

4) Метод Draw в каждом классе делает наброски рисунка на поверхности рисования.

р.Draw(); l.Draw(); г.Draw();

C ++ геометрические классы

Далее следуют объявления C++ для классов Point и Line. Заметьте, что конструктору для класса Line передаются координаты двух точек, определяющих линию. Каждый класс имеет функцию-член Draw, отображающую рисунок в области рисования.

Спецификация класса Point

ОБЪЯВЛЕНИЕ

class Point

private:

float x, у; public: // горизонтальная и вертикальная позиция

Point (float h, float v) ;

float GetX(void) const; // возвратить координату х

float GetY(void) const; // возвратить координату у

void Draw(void) const; // нарисовать точку (х,у)

Класс посредством композиции Line включает два объекта Point. Эти объекты инициализируются конструктором.

Спецификация класса Line

ОБЪЯВЛЕНИЕ

class Line

{

private:

Point PI, P2; // две конечные точки отрезка

public:

Line (Point a, Point b);// инициализировать P1 и Р2

void Draw(void) const; // нарисовать отрезок

};

Объекты и наследование

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

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

В иерархической цепочке класс наследует все характерные черты своего класса-предка. Например, собака имеет все черты млекопитающего плюс те, которые отличают ее от кошек, слонов и т.д. Порядок расположения классов указывает что

Колли есть собака. Собака есть млекопитающее

 

 

Рис. 1.2. Цепочка наследования у животных

В этой цепочке класс млекопитающих определяется в качестве базового класса (base class) для собаки, а собака называется производным классом (derived class). Используя аналогию семейного наследования, мы говорим о базовом и производном классах как о родительском классе и класее-наследнике, соответственно. В случае расширенной цепочки наследник наследует характерные черты своего родительского и прародительского класса.

Разработка

Программная разработка описывает объекты, которые являются основными строительными блоками программы. Разработка описывает также управляющие модули, руководящие взаимодействием между объектами.

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

Фаза разработки управления процессом использует нисходящую разработку путем создания главной программы и подпрограмм для управления взаимодействием между объектами. Главная программа и подпрограммы образуют каркас разработки (design framework).

Главный управляющий модуль соответствует главной функции в программе C++ и отвечает за поток данных программы. При нисходящей программной разработке система делится на последовательность действий, которые выполняются как независимые подпрограммы. Главная программа и ее подпрограммы организуются в нисходящую иерархию модулей, называемую структурным деревом (structure tree). Главный модуль является корнем этого дерева. Каждый модуль заключается в прямоугольник, а каждый класс, который используется модулем, заключается в овал. Мы представляем каждый модуль, указывая имя функции, входные и выходные параметры и краткое описание ее действия.

 

Кодирование

В фазе кодирования пишутся главная программа и подпрограммы, реализующие каркас программной разработки.

Тестирование

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

Замечание

Эмпирическая вероятность определяется моделированием большого количества событий и записью результатов. Отношение количества появлений некоторого события к количеству всех моделируемых событий представляет эмпирическую вероятность того, рассматриваемое событие произойдет. Например, если бросание костей повторится 100000 раз и сумма 4 возникнет 10000 раз, то эмпирическая вероятность этой суммы равна 0,10.

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

Определение программы. Программа запрашивает пользователя ввести число N – количество бросаний двух костей. Поскольку бросание костей имеет случайный результат, используем для моделирования N бросаний случайные числа. Программа ведет запись количества появлений каждой возможной суммы S (2 < S < 12). Эмпирическая вероятность определяется делением количества результатов S на N. Что касается выхода, это дробное значение используется для определения высоты прямоугольника на нашей диаграмме. Результаты выводятся на экран как столбцовая диаграмма.

Объектная разработка. Программа использует класс Line для создания осей координат и класс Rectangle – для построения столбцов. Эти классы вводятся в разделе 1.4 Разработка объектов. Бросание костей – это метод в классе Dice, который обрабатывает две кости. Далее следует объявление класса Dice. Его реализация и тестирование приводятся в программе вместе с реализацией и тестированием классов Line и Rectangle.

#include random.h

class Dice

private:

// данные-члены

int diceTotal; // сумма д вух костей

int diceList[2]; // список очков двух костей

// класс генератора случайных чисел, используемый для

// моделирования бросаний

RandomNumber rnd;

public:

// конструктор

Dice(void);

// методы

void Toss(void);

int Total(void) const;

void DisplayToss(void) const;

};

Разработка управления процессом. Для построения диаграммы бросания костей главный модуль вызывает три подпрограммы, которые выполняют основные действия программы. Функция SimulateDieToss использует методы из класса Dice для бросания костей N раз. Draw Axes вызывает метод Draw в классе Line для рисования осей координат графика, a Plot рисует серию прямоугольников, которые образуют столбцовую диаграмму. Функция Plot вызывает Мах для определения максимального количества появлений любой возможной суммы. Это значение позволяет нам вычислить относительную высоту каждого прямоугольника диаграммы. Структурное дерево этой программы показано на рис. 1.8. Далее следуют объявления для каждого управляющего модуля в структурном дереве.

 

 

 

 

Рис. 1.8. Древовидная структура программы Dice Graph

 

main

Передаваемые параметры: Нет

Выполнение:

Запросить у пользователя количество бросаний костей в моделировании. Вызвать функцию SimulateDieToss для выполнения бросаний и записать количество раз, когда возникает каждая возможная сумма: (2 < Total <. 12). Нарисовать оси координат функцией DrawAxes и создать столбцовую диаграмму функцией Plot.

Возвращаемые параметры: Нет

SimulateDieToss

Передаваемые параметры:

tossTotal Массив tossTotal содержит количество появлений каждой суммы в диапазоне от 2 до 12. tossTotal [i] – это количество появлений суммы i при бросании костей tossCount раз.

tossCount Количество бросаний N при моделировании.

Выполнение:

Создать объект Dice и использовать его для бросания костей указанное количество раз, записывая в массив tossTotal количество раз, когда возникает сумма 2, количество раз, когда возникает сумма 3, . . . , количество раз, когда возникает сумма 12.

Возвращаемые параметры:

Массив tossTotal с количеством раз, когда возникает каждая сумма.

DrawAxes

Передаваемые параметры:

Нет Выполнение:

Создать два объекта Line: один – для вертикальной оси (оси у) и один – для горизонтальной оси (оси х). Ось у – это линия от (1.0, 3.25) до (1.0, 0.25) . Ось х – это линия от (0.75, 3.0) до (7.0, 3.0) . Вертикальный диапазон графика равен 2,75.

Возвращаемые параметры: Нет

Передаваемые параметры:

а Массив, содержащий длинные значения данных,

n Количество значений данных в а.

Выполнение:

Найти максимальное значение элементов в массиве а.

Возвращаемый параметр:

Максимальное значение в массиве.

Plot

Передаваемый параметр:

tossTotal Массив, содержащий количество появлений каждой возможной суммы, вычисленной в SimulateDieToss.

Выполнение:

Поиск максимальной суммы (maxTotal) в массиве tossTotal для диапазона индекса 2-12. Затем каждый элемент в массиве генерирует соответствующую часть (tossTotal [i]/ maxTotal) вертикального диапазона графика. Разделить 6-дюймовый интервал оси х от (1.0, 3.0) до (7.0, 3.0) на 23 равных сегмента и построить соответствующие прямоугольники, чьи высоты – это функция (tossTotal [i]) / maxTotal*2.75, 2 < i < 12.

Возвращаемые параметры: Нет

Объектное тестирование

Тип класса – это самодостаточная структура данных, которая может передавать информацию внешнему компоненту программы и от него. Мы можем тестировать каждый класс, создав короткую программу, вызывающую каждый public-метод. Эта дополнительная программа иллюстрирует тестирование методов в классе Dice.

 

Абстрактные типы данных

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

Пример 1

1. Программа учета для малого предприятия сопровождает инвентаризационную информацию. Каждый элемент в описи представлен записью данных, которая включает идентификационный номер этого элемента, текущий уровень запаса, ценовую информацию и информацию упорядочивания. Набор операций по обработке списка обновляет различные информационные поля и инициирует переупорядочивание запаса, когда его уровень падает ниже определенного порога. Абстракция данных описывает какой-либо элемент как запись, содержащую серию информационных полей и операций, необходимых менеджеру компании для инвентаризационного сопровождения. Операции могут включать изменение значения Stock on Hand (имеющийся запас) при продаже этого товара, изменение Unit Price (цены за единицу) при использовании новой ценовой политики и инициализации упорядочивания при падении уровня запаса ниже уровня переупорядочивания (Reorder Level).

Данные

 

Identification

Stock on Hand

Unit Price

Reorder Level

Операции

UpdateStockLevel

AdjustUnitPrice

Reorderltem

2. Игровая программа моделирует бросание набора костей. В этой разработке игральные кости описываются как абстрактный тип данных, которые включают число бросаемых костей, сумму очков в последнем бросании и список со значениями очков каждой кости в последнем бросании. Операции включают бросание костей (Toss), возвращение суммы очков в одном бросании (Total) pi вывод очков для каждой отдельной кости (DisplayToss).

Данные

N		diceTotal			Dice List

Операции

Toss

Total

DisplayToss

ADT – формат

Для описания ADT используется формат, который включает заголовок с именем ADT, описание типа данных и список операций. Для каждой операции определяются входные (input) значения, предоставляемые клиентом, предусловия (preconditions), применяемые к данным до того, как операция может быть выполнена, и процесс (process), который выполняется операцией. После выполнения операции определяются выходные (output) значения, которые возвращаются клиенту, и постусловия (postconditions), указывающие на любые изменения данных. Большинство ADT имеют инициализирующую операцию (initializer), которая присваивает данным начальные значения. В среде языка C++ такой инициализатор называется конструктором (constructor). Мы используем этот термин для упрощения перехода от ADT к его преставлению в C++.

 

 

ADT - формат

ADT ADT_Name

Данные

Описание структуры данных

Операции

Конструктор

Начальные значения: Данные, используемые для инициализации объекта

Процесс: Инициализация объекта

Операция₁

Вход: Данные от клиента

Предусловия: Необходимое состояние системы перед выполнением операций

Процесс: Действия, выполняемые с данными

Выход: Данные, возвращаемые клиенту

Постусловия: Состояние системы после выполнения операций

Операция₂

Операция_n

Конец ADT

 

Пример 2

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

ADT Dice

Данные

Число костей в каждом бросании – целое, большее либо равное 1. Целое значение, содержащее сумму очков всех костей в последнем бросании. Если N – число бросаемых костей, то число очков находится в диапазоне от N до 6N, Список, содержащий число очков каждой кости в бросании. Значение любого элемента списка находится в диапазоне от 1 до 6.

Операции

Конструктор

Начальные значения: Число бросаемых костей

Процесс: Инициализировать данные, определяющие число костей в каждом бросании

Toss

Вход: Нет

Предусловия: Нет

Процесс: Бросание костей и вычисление общей суммы очков

Выход: Нет

Постусловия: Общая сумма содержит сумму очков в бросании, а в списке находятся очки каждой кости

DieTotal

Вход: Нет

Предусловия: Нет

Процесс: Находит значение элемента, определяемого как сумма очков в последнем бросании

Выход: Возвращает сумму очков в последнем бросании

Постусловия: Нет

Display Toss

Вход: Нет

Предусловия: Нет

Процесс: Печатает список очков каждой кости в последнем бросании

Выход: Нет

Постусловия: Нет

Конец ADT Dice

2. Окружность определяется как набор точек, равноудаленных от точки, называемой центром. С целью графического отображения абстрактный тип данных для окружности включает как радиус (radius), так и положение центра. Для измеряющих приложений абстрактному типу данных требуется только радиус. Мы разрабатываем Circle ADT и включаем операции для вычисления площади (area) и длины окружности (circumference). Этот ADT применяется в следующем разделе для иллюстрации описания класса C++ и использования объектов при программировании приложений.

Circumference  Area

ADT Circle

Данные

Неотрицательное действительное число, определяющее радиус окружности.

Операции

Конструктор

Начальные значения: Радиус окружности

Процесс: Присвоить радиусу начальное значение

Area

Вход: Нет

Предусловия: Нет

Процесс: Вычислить площадь круга

Выход: Возвратить площадь круга

Постусловия: Нет

Circumference

Вход: Нет

Предусловия: Нет

Процесс: Вычислить длину окружности

Выход: Возвратить длину окружности

Постусловия: Нет

конец ADT Circle

2. Классы C++ и абстрактные типы

Язык C++ поддерживает определяемый пользователем тип классов для представления абстрактных типов данных. Класс состоит из членов (members), которые включают значения данных и операции по обработке этих данных. Операции также называются методами (methods), поскольку они определяют методы доступа к данным. Переменная типа класса называется объектом (object). Класс содержит две отдельные части. Открытая (public) часть описывает интерфейс, позволяющий клиенту манипулировать объектами типа класса. Открытая часть представляет ADT и позволяет клиенту использовать объект и его операции без знания внутренних деталей реализации.

Класс

private: Данные-члены: переменная1, переменная2 Внутренние операции

public: Конструктор Операция1 Операция2

Закрытая (private) часть содержит данные и внутренние операции, помогающие в реализации абстракции данных. Например, класс для представления ADT Circle содержит один закрытый член класса – radius. Открытые члены включают конструктор и методы вычисления площади круга и длины окружности

Circle Класс

private: radius

public: Конструктор Area Circumference

Инкапсуляция и скрытие информации

Класс инкапсулирует (encapsulates) информацию, связывая вместе члены и методы и обращаясь сними как с одним целым. Структура класса скрывает реализацию деталей и тщательно ограничивает внешний доступ как к данным, так и к операциям. Этот принцип, известный как скрытие информации (information hiding), защищает целостность данных.

Класс использует свои открытую и закрытую части для контроля за доступом клиентов к данным. Члены внутри закрытой части используются методами класса и изолированы от внешней среды. Данные обычно определяются в закрытой части класса для предотвращения нежелательного доступа клиента. Открытые члены взаимодействуют с внешней средой и могут использоваться клиентами.

Например, в Circle-классе radius является закрытым членом класса, доступ к которому может осуществляться только тремя методами. Конструктор присваивает начальное значение члену radius. Каждый из других методов использует radius. Например, area=р*raduis². Здесь методы являются открытыми членами класса, которые могут вызываться всеми внешними единицами программы.

Передача сообщений

В приложении доступ клиентов к открытым членам какого-либо объекта может быть реализован вне этого объекта. Доступом управляют главная программа и подпрограммы (master control modules), которые наблюдают за взаимодействием между объектами. Управляющий код руководит объектом для доступа к его данным путем использования одного из его методов или операций. Процесс управления деятельностью объектов называется передачей сообщений (message passing). Отправитель передает сообщение получающему объекту и указывает этому объекту выполнить некоторую задачу.

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

3. Объекты в приложениях C++

Абстрактный тип данных реализует общее описание данных и операций над данными. Класс C++ обычно вводится сначала объявлением этого класса без определения функций-членов. Это известно как объявление класса (class declaration) и является конкретным представлением ADT. Фактическое определение методов дается в реализации класса (class implementation), отдельной от объявления.

Реализация классов C++ и использование объектов иллюстрируются следующей завершенной программой, которая определяет стоимость планировки бассейна. Программа объявляет Circle класс и показывает, как определяются и используются объекты. В коде содержатся определения открытого и закрытого разделов класса и используются функции C++ для определения операций. Главная программа – это клиент, который объявляет объекты, и затем использует их операции для выполнения вычислений. Главная программа отвечает за передачу всех сообщений в приложении.

Приложение: класс Circle

Объекты Circle используются для описания плавательного бассейна и дорожки вокруг него. С помощью методов Circumference (вычисление длиныокружности) и Area (вычисление площади круга) мы можем вычислить стоимость бетонирования дорожки и строительства ограды вокруг бассейна. К нашему приложению применяются следующие условия.

Строительные правила требуют, чтобы плавательный бассейн окружала бетонная дорожка (темная область на следующем рисунке) и вся территория была огорожена. Текущая стоимость ограды составляет $3,50 за погонный фут, а стоимость бетонирования - $0,5 за кв. фут. Приложение предполагает, что ширина дорожки, окружающей бассейн, составляет 3 фута и что клиент указывает радиус круглого бассейна, В качестве результата приложение должно определить стоимость строительства ограды и дорожки при планировании бассейна.

PoolRim

Мы объявляем объект Circle с именем Pool, описывающий площадь плавательного бассейна. Второй объект - PoolRim, - это объект Circle, включающий как бассейн, так и окружающую дорожку. Конструктор вызывается при определении объекта. Для объекта Pool клиент задает радиус в качестве параметра, и затем использует радиус плюс 3 фута для определения объекта PoolRim.

Для вызова операции класса задайте имя объекта, за которым следует точка (.) и операция. Например, Pool.Area() и Circumference() вызывают операции Circle для Pool.

Ограда располагается вдоль наружной стороны PoolRim. Вызовите операцию вычисления окружности PoolRim.Circumference() для вычисления стоимости ограды.

FenceCost = PoolRim.Circumference() * 3.50

Площадь бетонной поверхности определяется вычитанием площади Pool из внешней площади PoolRim.

ConcreteCost = (PoolRim.Area() - Pool.Area()) * 0.5

1234567Следующая ⇒

Поделиться: