yandex rtb 1
ГоловнаЗворотній зв'язок
yande share

Объектно-ориентированное программирование

        Лекция 3.      

Пример проектирования совокупности классов. Абстрактные типы данных.

 

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

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

Рассмотрим каждую из этих структур: как они должны быть устроена и какие услуги мы предоставляем пользователю этих структур.

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

Для списка нам необходимо определить следующие основные операции:

- добавить новый узел в список в определенной позиции;

- удалить узел из списка;

- найти первый элемент списка;

- найти следующий элемент списка;

- подсчитать число элементов в списке;

- очистить список.

В качестве дополнительных услуг можно было бы предложить следующие операции:

 - найти последний элемент списка;

- найти предыдущий элемент списка.

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

1.      Массив указателей на структуру, хранящую данные;

2.      Классический однонаправленный список, в котором каждый узел имеет указатель на следующий узел и указатель на структуру хранения;

3.      Классический двунаправленный список, в котором помимо указателя на следующий узел имеется указатель и на предыдущий.

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

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

Кроме структуры хранения типа «узел» нам могут потребоваться также некоторые вспомогательные поля:

- максимальное количество элементов в списке;

- текущее количество элементов в списке;

- указатель на первый элемент.

В зависимости от реализации нам может потребоваться хранение и указателя на последний элемент.

Стек – это последовательность элементов, которые могут добавляться и удаляться только с одного конца. Опять же для пользователей неважно, как внутри устроен стек. Важен набор операций над этим стеком. Мы можем себе представить его следующим образом:

- поместить элемент в стек;

- извлечь элемент из стека;

- определить количество элементов в стеке;

- очистить стек.

Очередь – это последовательность элементов, которые могут добавляться только с одного конца, а удаляться с другого. Заметим, что набор операций, определенных для стека и для очереди, идентичен. Единственное отличие – в операции «извлечь». Да и структура хранения для стека и очереди может быть одна и та же.

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

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

Операция «поместить элемент» легко осуществляется с помощью операций «найти первый» и «добавить узел в список».

В зависимости от производного класса операция «извлечь элемент» будет соответствовать последовательности операций «найти первый» и «удалить узел» или «найти последний» и «удалить узел».

Операции «определить количество элементов» и «очистить» могут определяться через соответствующие методы класса «список».

Возникает вопрос: а может ли непосредственно использоваться класс «упорядоченный список»? По-видимому, ответ на этот вопрос должен быть отрицательным. Ведь в случае использования этого класса непонятно, как будет работать метод «извлечь элемент». В базовом классе эта функция никак не будет определена. Ее реализация возможна только в производном классе. Мы можем запретить использование пользователями этого класса.

Следует различать запрет на использование класса «узел» и класса «упорядоченный список». Класс «узел» - это наш дополнительный класс, необходимый для работы всех остальных классов. При этом внутри класса «список» мы спокойно можем создавать новые объекты типа «узел», пользоваться соответствующими методами этого класса для создания нужной нам структуры. Мы только ограничиваем извне доступ к этому классу.

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

Таким образом, можно представить себе такую структуру классов:

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

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

Объектно-ориентированное программирование позволяет легко создавать и использовать абстрактные типы данных. Определим их следующим образом:

Абстрактный тип данных (АТД, abstract data type) – это определяемое пользователем расширение исходных типов языка. АТД состоит из набора значений и операций, которые могут влиять на эти значения.

Реализация АТД может быть осуществлена таким образом, что пользователь такого АТД будет обращаться с ними так же, как и с исходными типами данных языка. Рассмотрим, например, класс «деньги». Понятно, что в большинстве языков программирования такой класс отсутствует. Для данного класса определен свой набор операций:

- сложение;

- вычитание;

- умножение на действительное число

и др.

Естественно, пользователю языка хотелось бы иметь механизм, который позволял обращаться с этими типами данных как, например, с обычными числами:

currency a, b;

a=12;

b=13.2;

a+=b;

a*=1.05;

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

 

 

 

5