Программа 1. Конструкция и использование класса Circle
АБСТРАКТНЫЕ ТИПЫ ДАННЫХ
Абстракция данных – центральное понятие в разработке программ. Абстракция определяет область и структуру данных вместе с набором операций, которые имеют доступ к данным. Абстракция, называемая абстрактным типом данных (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
Данные
Описание структуры данных
Операции
Конструктор
Начальные значения: Данные, используемые для инициализации объекта
Процесс: Инициализация объекта
Операция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++ и использования объектов при программировании приложений.
|
|
|
|
|
Circumference Area
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
*/
Разработка объектов
В этой книге разрабатываются структуры данных с классами и объектами. Мы начинаем с классов, которые определяются простыми данными-членами и операциями класса. Для более сложных структур классы могут содержать члены класса, которые сами являются объектами. Результирующие классы, созданные посредством композиции (composition), имеют доступ к функциям-членам в составляющих объектах. Использование композиции объектов расширяет понятия инкапсуляции и скрытия информации и обеспечивает повторное использование кода. Объектно-ориентированные языки также позволяют классу быть порожденным из других классов путем наследования (inheritance). Это дает возможность разработчику создавать новые классы как усовершенствования других классов и повторно использовать код, который был разработан ранее. Наследование является фундаментальным средством объектно-ориентированного программирования на языке C++. Эта тема вводится формально в главе 12 и используется для разработки и реализации улучшенных структур данных.
1.4.1. Объекты и композиция
Геометрические фигуры состоят из наборов точек, которые образуют линии, прямоугольники и т.д. Основными строительными блоками фигур являются точки, сочетающиеся с серией аксиом для определения геометрических объектов. В данном разделе мы рассматриваем точку как примитивный геометрический объект, а затем описываем линии и прямоугольники. Эти геометрические фигуры используются для иллюстрации объектов и композиции.
Точка – это местоположение на плоской поверхности. Мы предполагаем, что объект точка расположена на сетке с координатами, которые измеряют горизонтальное (х) и вертикальное (у) расстояние от базовой точки. Например, точка р (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();
1.4.2. 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.4.3. Объекты и наследование
Наследование – это интуитивное понятие, из которого мы можем извлекать примеры, основанные на каждодневном опыте. Все из нас наследуют характерные черты от своих родителей такие, как раса, цвет глаз и тип крови. Мы можем думать о родителе как о базе, из которой мы наследуем характерные черты. Взаимосвязь иллюстрируется двумя объектами, связанными стрелкой, острие которой направлено к базовому объекту.
Зоология формально изучает наследование у животных. На рис. 1.2 показана иерархия животных для млекопитающих, собак и колли. Млекопитающее – это теплокровное животное, которое имеет шерсть и вскармливает своих детенышей молоком. Собака – это млекопитающие, которое имеет клыки, ест мясо, имеет определенное строение скелета и является общественным животным. Колли – это собака с заостренной мордой, имеющая белый с рыжим окрас и хорошо развитые пастушеские инстинкты.
В иерархической цепочке класс наследует все характерные черты своего класса-предка. Например, собака имеет все черты млекопитающего плюс те, которые отличают ее от кошек, слонов и т.д. Порядок расположения классов указывает что
Колли есть собака. Собака есть млекопитающее
 |
Рис. 1.2. Цепочка наследования у животных
В этой цепочке класс млекопитающих определяется в качестве базового класса (base class) для собаки, а собака называется производным классом (derived class). Используя аналогию семейного наследования, мы говорим о базовом и производном классах как о родительском классе и класее-наследнике, соответственно. В случае расширенной цепочки наследник наследует характерные черты своего родительского и прародительского класса.
1.4.4. Наследование в программировании
Объектно-ориентированное программирование предоставляет механизм, посредством которого производному классу разрешается наследовать данные и операции от базового класса. Этот механизм, называемый наследование класса (class inheritance), позволяет производному классу использовать данные и операции, которые были определены ранее в базовом классе. Производный класс может добавлять новые операции или переписывать некоторые операции, так как он устанавливает методы для обработки его данных. Аналогично, ребенок может наследовать дом или автомашину от его (или ее) родителя. Затем он может затем н: пользовать этот дом или автомашину. Если необходимо, наследник может модифицировать дом, чтобы он соответствовал его (или ее) особым условиям.
Проиллюстрируем наследование класса с помощью линейного списка, названного SeqList, который сохраняет информацию в последовательном порядке. Список – это важная и знакомая структура, используемая для ведения инвентаризационных записей, графика деловых встреч, типов и количества необходимых гастрономических товаров и т.д. Наследование возникает, когда мы объявляем упорядоченный список, который является особым типом последовательного списка. Упорядоченный список использует все базовые методы обработки списка из последовательного списка и обеспечивает свою собственную операцию вставки для того, чтобы элементы списка сохранялись в возрастающем порядке.
В линейном списке, содержащем N элементов, любой элемент занимает одно из положений от 0 до N-1. Первое положение является передним, а последнее – конечным. На рис. 1.3 показан неупорядоченный список целых чисел с шестью элементами.
0 5
1 3
2 22
3 45
4 23
5 8
Рис. 1.3. Неупорядоченный линейный список
Базовые операции SeqList включают операцию Insert, которая добавляет новый элемент в конец списка (Рис. 1.4), и операцию Delete, которая удаляет первый элемент списка, соответствующий ключу. Вторая функция удаления, называемая DeleteFront, удаляет первый элемент в списке (Рис. 1.5). Структура определяет размер списка с помощью ListSize и предоставляет операцию Find, выполняющую поиск элемента в списке. Для управления данными пользователь может определить, является ли список пустым, и удалить его операцией Clear-List.
Insert (10)
0 5
1 3
2 22
3 45
4 23
5 8
6 10
Рис. 1.4. Вставка значения 10
0 5
1 3
2 22
3 23
4 8
5 10
Delete (45)
0 3
1 22
2 45
3 23
4 8
5 10
DeleteFront
Рис. 1.5. Удаление элемента 45 и удаление первого элемента в списке
Данный класс предоставляет метод GetData, позволяющий клиенту читать значение любого элемента списка. Например, для нахождения максимального значения в списке мы можем начать сканирование списка с нулевого элемента. Процесс заканчивается при достижении конца списка, который определяется с помощью ListSize. В каждом положении следует обновлять максимальное значение, если текущее значение (GetData) больше, чем текущий максимум. Например, для второго элемента списка число 22 сравнивается с предыдущим максимумом, равным 3, поэтому текущее максимальное значение заменяется на 22. В конечном счете, число 23 определяется как максимальный элемент в списке.
ADT SeqList
Данные
Неотрицательное целое число, указывающее количество элементов, находящихся в данный момент в списке (размер), и список элементов данных.
Операции
Конструктор
Начальные значения: Нет
Процесс: Установка размера списка на 0
ListSize
Вход: Нет
Предусловия: Нет
Процесс: Чтение размера списка
Выход: Размер списка
Постусловия: Нет
ListEmpty
Вход: Нет
Предусловия: Нет
Процесс: Проверка размера списка
Выход: Возвращать TRUE, если список пустой; в противном случае – возвращать FALSE.
Постусловия: Нет
ClearList
Вход: Нет
Предусловия: Нет
Процесс: Удаление всех элементов из списка и установка размера списка на 0.
Выход :Нет
Постусловия: Список пустой
Find
Вход: Элемент, который необходимо найти в списке.
Предусловия: Нет
Процесс: Сканирование списка для нахождения соответствующего элемента.
Выход: Если соответствующий элемент списка не найден, возвращать FALSE; если он найден, возвращать TRUE и этот элемент.
Постусловия: Нет
Insert
Вход: Элемент для вставки в список
Предусловия: Нет
Процесс: Добавление этого элемента в конец списка.
Выход: Нет
Постусловия: Список имеет новый элемент; его размер увеличивается на 1.
Delete
Вход: Значение, которое должно быть удалено из списка.
Предусловия: Нет
Процесс: Сканирование списка и удаление первого найденного элемента в списке. Не выполнять никакого действия, если этот элемент не находится в списке.
Выход: Нет
Постусловия: Если соответствующий элемент найден, список уменьшается на один элемент.
DeleteFront
Вход: Нет
Предусловия: Список не должен быть пустым.
Процесс: Удаление первого элемента из списка.
Выход: Возвращать значение удаляемого элемента
Постусловия: Список имеет на один элемент меньше.
GetData
Вход: Положение (роs) в списке.
Предусловия: Генерируется ошибка доступа, если роз меньше 0 или больше 0 (размер -1)
Процесс: Получать значение в положении роs в списке.
Выход: Значение элемента в положении роs.
Постусловия: Нет
Конец AQT SeqList
1.4.5. Упорядоченные списки и наследование
Операции ListSize, ListEmpty, ClearList, Find и GetData независимы от любого упорядочения элементов. Операции Delete и DeleteFront удаляют элемент, но сохраняют остающиеся элементы упорядоченными. Далее следует ADT, отражающий сходство операций упорядоченного списка и SeqList.
ADT OrderedList
Данные
те же, что и для SeqList ADT
Операции
Конструктор выполняет конструктор базового класса
ListSize тот же, что и для SeqList ADT
ListEmpty тот же, что и для SeqList ADT
ClearList тот же, что и для SeqList ADT
Find тот же, что и для SeqList ADT
Delete тот же, что и для SeqList ADT
DeleteFront тот же, что и для SeqList ADT
GetData тот же, что и для SeqList ADT
Insert
Вход: Элемент для вставки в список.
Предусловия: Нет
Процесс: Добавление элемента в положение, сохраняющее упорядочение.
Выход: Нет
Постусловия: Список имеет новый элемент, и его размер увеличивается на 1.
Конец ADT OrderedList
Класс OrderedList является производным от класса SeqList. Он наследует операции базового класса и модифицирует операцию Insert для упорядоченной вставки элементов.
 |
1.4.6. Повторное использование кода
Объектно-ориентированный подход к структурам данных способствует повторному использованию кода, который уже был разработан и протестирован, и может быть вставлен в ваше приложение. Мы уже рассматривали повторное использование кода с композицией. Наследование также является мощным инструментом для этой цели. Например, реализация класса упорядоченного списка требует от нас написания только методов Insert и конструктора. Все другие операции задаются кодом из класса SeqList. Повторное использование кода является важнейшим преимуществом в объектно-ориентированной разработке, поскольку оно сокращает время разработки и способствует инородности приложений и вариантов программного продукта. Например, при модернизации операционной системы к ней добавляются новые функции. В то же время, эта модернизация должна позволять выполнение существующих приложений. Одним из подходов является определение оригинальной операционной системы в качестве базового класса. Модернизированная система действует как производный класс с его новыми функциями и операциями.
1.4.7. Спецификации класса SeqList и OrderedList
Формальное описание класса SeqList приводится в главе 4. В этом разделе мы даем только спецификацию класса для того, чтобы вы могли соотнести этот класс и его методы с очень общим ADT. Класс OrderedList определяется для иллюстрации наследования. Тип элемента данных в списке представлен параметрическим именем DataType.
Спецификация класса SeqList
ОБЪЯВЛЕНИЕ
class SeqList
{
private:
// массив для хранения списка и число элементов текущего списка
DataType listitem[ARRAYSIZE];
int size;
public:
// конструктор
SeqList(void);
// методы доступа списка
int ListSize(void) const;
int ListEmpty(void) const;
int Find (DataType& item) const;
DataType GetData (int pos) const;
// методы модификации списка
void Insert (const DataType& item);
void Delete (const DataTypes item);
DataType DeleteFront (void);
void ClearList (void);
};
ОПИСАНИЕ
Методы ListSize, ListEmpty, Find и GetData завершаются словом const после объявления функции. Они называются постоянными функциями, поскольку не изменяют состояние списка. Функции Insert, Delete имеют слово const как часть списка параметров. Этот синтаксис C++ передает ссылку на элемент, но указывает, что значение этого элемента не изменяется.
C++ использует простой синтаксис для объявления производного класса. В заголовке базовый класс указывается после двоеточия (:). Далее следует объявление класса OrderedList. Особенности описываются в главе 12, в которой содержится формальное введение в наследование.
Спецификация класса OrderedList
ОБЪЯВЛЕНИЕ
class OrderedList: public SeqList // наследование класса SeqList
{
public:
OrderedList (void);// инициализировать базовый класс
// для создания пустого списка
void Insert(const DataType& item); //вставить элемент по порядку
};
ОПИСАНИЕ
Insert замещает метод базового класса с тем же именем. Она проходит по всему списку и вставляет элемент в положение, сохраняющее упорядочение списка.
Дата добавления: 2018-10-25; просмотров: 310; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!