1. Абстрактные типы данных
Абстракция данных – центральное понятие в разработке программ. Абстракция определяет область и структуру данных вместе с набором операций, которые имеют доступ к данным. Абстракция, называемая абстрактным типом данных (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
1.1. ADT – формат
Для описания ADT используется формат, который включает заголовок с именем ADT, описание типа данных и список операций. Для каждой операции определяются входные (input) значения, предоставляемые клиентом, предусловия (preconditions), применяемые к данным до того, как операция может быть выполнена, и процесс (process), который выполняется операцией. После выполнения операции определяются выходные (output) значения, которые возвращаются клиенту, и постусловия (postconditions), указывающие на любые изменения данных. Большинство ADT имеют инициализирующую операцию (initializer), которая присваивает данным начальные значения. В среде языка C++ такой инициализатор называется конструктором (constructor). Мы используем этот термин для упрощения перехода от ADT к его преставлению в C++.
ADT - формат
ADT ADT_Name
Данные
Описание структуры данных
Операции
Конструктор
Начальные значения: Данные, используемые для инициализации объекта
Процесс: Инициализация объекта
Операция1
Вход: Данные от клиента
Предусловия: Необходимое состояние системы перед выполнением операций
Процесс: Действия, выполняемые с данными
Выход: Данные, возвращаемые клиенту
Постусловия: Состояние системы после выполнения операций
Операция2
Операция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++ и использования объектов при программировании приложений.
ADT Circle
Данные
Неотрицательное действительное число, определяющее радиус окружности.
Операции
Конструктор
Начальные значения: Радиус окружности
Процесс: Присвоить радиусу начальное значение
Area
Вход: Нет
Предусловия: Нет
Процесс: Вычислить площадь круга
Выход: Возвратить площадь круга
Постусловия: Нет
Circumference
Вход: Нет
Предусловия: Нет
Процесс: Вычислить длину окружности
Выход: Возвратить длину окружности
Постусловия: Нет
конец ADT Circle
1.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=р*raduis2. Здесь методы являются открытыми членами класса, которые могут вызываться всеми внешними единицами программы.
Передача сообщений
В приложении доступ клиентов к открытым членам какого-либо объекта может быть реализован вне этого объекта. Доступом управляют главная программа и подпрограммы (master control modules), которые наблюдают за взаимодействием между объектами. Управляющий код руководит объектом для доступа к его данным путем использования одного из его методов или операций. Процесс управления деятельностью объектов называется передачей сообщений (message passing). Отправитель передает сообщение получающему объекту и указывает этому объекту выполнить некоторую задачу.
В нужный момент отправитель включает в сообщение информацию, которая используется получателем. Эта информация передается как данные ввода для операции. После выполнения задачи получатель может возвращать информацию отправителю (данные вывода) или передавать сообщения другим объектам, запрашивая выполнение дополнительных задач. Когда получающий объект выполняет операцию, он может обновлять некоторые из его собственных внутренних значений. В этом случае считается, что происходит изменение состояния (state change) объекта и возникают новые постусловия.
1.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
Программа 1. Конструкция и использование класса Circle
Программа 1.1 реализует приложение для бассейна. Для оказания помощи в чтении кода C++ в тексте имеются комментарии. Объявление класса Circle показывает представление Circle ADT и использование закрытых и открытых директив для контроля за доступом к членам класса.
Главная программа запрашивает клиента ввести радиус бассейна. Это значение используется для объявления объекта Pool. Второй объект – PoolRim объявляется как имеющий дополнительные три фута к его радиусу для размещения дорожки вокруг бассейна. Стоимость строительства ограды и стоимость бетонирования дорожки выводятся для печати.
Вне главного модуля программа определяет класс Circle. Читатель может обратить внимание на использование спецификатора const для указания на то, что функция-член не изменяет данные. Этот спецификатор используется с методами Circumference и Area в их объявлении и определении. Стоимость строительных материалов для сетки ограды и стоимость бетона задаются как константы.
// рr01_01.срр
#include <iostream.h>
const float PI = 3.14152;
const float FencePrice = 3.50;
const float ConcretePrice= 0.50;
// Объявление класса Circle, данных и методов
class Circle
{
private:
// член класса radius - число с плавающей запятой
float radius;
public:
// конструктор
Circle (float r);
// вычисляющие функции
float Circumference (void) const;
float Area (void) const;
};
// class implementation
// конструктор инициализирует член класса radius
Circle::Circle (float r): radius (r)
{ }
// возвратить длину окружности
float Circle:: Circumference (void) const
{
return 2*PI*radius;
}
// возвратить площадь круга
float Circle::Area (void) const
{
return PI*radius*radius;
}
void main ( )
{
float radius;
float FenceCost, ConcreteCost;
// настраивает поток вывода на выдачу двух знаков
// после десятичной точки
cout.setf(ios::fixed);
cout.setf(ios::showpoint);
cout.precision(2) ;
// запрос на ввод радиуса
cout << "Введите радиус бассейна:'';
cin >> radius;
// объявить объекты Circle
Circle Pool (radius);
Circle PoolRim(radius+3) ;
// вычислить стоимость ограды и выдать ее значение
FenceCost=PoolRim.Circumference()*FencePrice;
cout << "Стоимость ограды: $" << FenceCost << endl;
// вычислить стоимость бетона и выдать ее значение
ConcreteCost=(PoolRim.Area()-Pool.Area())*ConcretePrice;
cout << "Стоимость бетона: $" << ConcreteCost << endl;
/*
Запуск программы pr01_01 . cpp
Введите радиус бассейна: 40
Стоимость ограды: $945.60
Стоимость бетона: $391.12
*/