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 для упорядоченной вставки элементов.
Класс SeqList
private:
детали реализации public:
Косгруктор Find ListEmpty Delete ClearList DeleteFront ListSize GetData
Класс OrderedList
private: public:
Конструктор, 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 замещает метод базового класса с тем же именем. Она проходит по всему списку и вставляет элемент в положение, сохраняющее упорядочение списка.