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

Рассмотрим задачу на реализацию класса с заданными свойствами.

Задача 10.1. Реализуйте класс R2Vector, позволяющий выполнять над векторами на плоскости следующие операции: сложение, вычитание, умножение на число и вычисление скалярного произведения.

Ее решение, приведенное ниже, в комментариях не нуждается.

Текст программы

class R2Vector {
    private double x, y;

    public R2Vector(double x, double y) {
        this.x = x; this.y = y;
    }
    public R2Vector() throws Exception {
        x = Xterm.inputDouble("x -> ");
        y = Xterm.inputDouble("y -> ");
    }
    public static R2Vector plus(R2Vector a, R2Vector b) {
        return new R2Vector(a.x+b.x, a.y+b.y);
    }
    public static R2Vector minus(R2Vector a, R2Vector b) {
        return new R2Vector(a.x-b.x, a.y-b.y);
    }
    public static R2Vector mult(R2Vector a, double k) {
        return new R2Vector(k*a.x, k*a.y);
    }
    public static double product(R2Vector a, R2Vector b) {
        return a.x*b.x + a.y*b.y;
    }
}

Одним из достоинств объектно-ориентированного подхода является возможность использования уже существующих типов для порождения новых с автоматическим наследованием уже имеющихся свойств. Язык Java реализует эту возможность с помощью двух механизмов — расширения или наследования классов (ключевое слово extends ) и реализации интерфейсов (ключевое слово implements ).

Примером использования первого из этих механизмов является следующий программный фрагмент.

Пример расширения класса

class Stack {
    private static final int DEFSIZE = 16;
    private char[] array;
    private int    head;

    public Stack() {
        array = new char[DEFSIZE];
        head = 0; 
    }
    public final void push(char c) {
        array[head++] = c;
    }
    public final char pop() {
        return array[--head];
    }
} 
public class Compf extends Stack {
    private void processSymbol(char c) {
        switch (c) {
          case '(':
            push(c); break;
          case ')':
            pop(); break;
          case '+': case '-': case '*': case '/':
            push(c); break;
          default:
            break;
        }
    }

    public Compf() {
        super();
    }
    public final void compile(String str) { 
        for(int i = 0; i < str.length(); i++)
            processSymbol(str.charAt(i));
    }
}

Класс Stack (стек символов) в данном случае используется в качестве базового для нового класса Compf (стековый компилятор формул), называемого в этом случае дочерним или выведенным. Все те методы, которые были реализованы в базовом классе (или суперклассе ) Stack могут быть использованы и для объектов типа Compf, что и делается в методе processSymbol. Принято говорить, что между классами Stack и Compf возникает отношение наследования.

В языке Java каждый существующий класс неявно наследует класс Object, что превращает последний в суперкласс любого класса. Сам же класс Object является единственным классом, не имеющим суперкласса. Если изобразить иерархию классов графически, то получится дерево с корнем Object.

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

Перед завершением рассмотрения примера отметим, что используемые в реальном проекте классы Stack и Compf существенно отличаются от рассмотренных нами сейчас. Это замечание в полной мере применимо и к следующему примеру механизма создания новых типов — использованию интерфейсов.

Пример реализации интерфейса

// Интерфейс, задающий новый тип - фигуру.
interface Figure {
    // Периметр фигуры.
    public double perimeter();
    // Площадь фигуры.
    public double area();
}
// Класс "нульугольник", реализующий интерфейс фигуры.
class Void implements Figure {
    public double perimeter() {
        return 0.0;
    }
    public double area() {
        return 0.0;
    }
}
// Класс "одноугольник", реализующий интерфейс фигуры.
class Point implements Figure {
    private R2Point p;

    public Point(R2Point p) {
        this.p = p;
    }
    public double perimeter() {
        return 0.0;
    }
    public double area() {
        return 0.0;
    }
} 
// Класс "двуугольник", реализующий интерфейс фигуры.
class Segment implements Figure {
    private R2Point p, q;
  
    public Segment(R2Point p, R2Point q) {
        this.p = p; this.q = q;
    }
    public double perimeter() {
        return 2.0 * R2Point.dist(p, q);
    }
    public double area() {
        return 0.0;
    }
}
// Класс "многоугольник", реализующий интерфейс фигуры.
class Polygon extends Deq implements Figure {
    private double s, p;
  
    public Polygon(R2Point a, R2Point b, R2Point c) {
        ; // Значительное упрощение.
    }
    public double perimeter() {
        return p;
    }
    public double area() {
        return s;
    }
}

Интерфейс Figure определяет геометрическую фигуру, которая характеризуется периметром и площадью. При этом конкретными реализациями этой абстрактной идеи могут быть "нульугольник" (пустое множество), "одноугольник" (точка), "двуугольник" (отрезок) и многоугольник. Каждый из этих классов имеет свою особую внутреннюю структуру: "одноугольник" содержит координаты его единственной точки, "двуугольник" — двух его концевых точек, а класс Polygon (многоугольник) вообще выведен из класса Deq, что позволяет ему хранить координаты всех его вершин. Каждый из этих классов обеспечивает свои варианты реализации для всех методов, имеющихся в описании интерфейса.

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

Динамический поиск метода никогда не используется в следующих ситуациях:

Поясним смысл этих и некоторых других ключевых слов языка Java, которые были использованы в приведенных выше примерах. Ключевое слово final, примененное к методу, запрещает переопределять его в выведенных классах. Применение его к полю данных превращает эти данные в неизменяемые (константу). Особенно часто для этой цели используется комбинация двух ключевых слов — static final. Будучи примененным к описанию класса, final запрещает использование данного класса в качестве базового.

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

Теперь мы в состоянии полностью объяснить программу "Здравствуй, мир!", с которой в самом начале книги началось знакомство с языком Java.

Текст программы

public class Hello {
    public static void main(String[] args) {    
        System.out.println("Здравствуй, мир!");
    }
}

Общедоступный ( public ) статический ( static ) метод main класса Hello, с которого начинается выполнение программы, получает в качестве аргумента массив строк args, не возвращая после своего завершения никакого результата (являясь void -методом). Выполнение main сводится к вызову метода println с аргументом "Здравствуй, мир!" для объекта, на который ссылается поле (компонента) out объекта System.

Контейнеры

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

Определение 10.7. Контейнерные классы (container classes) — классы, которые используются как структуры данных, содержащие набор элементов.

Пакет java.util предоставляет интерфейс Enumeration и классы Vector, Stack, Dictionary, Hashtable и BitSet, предназначенные для решения сформулированной задачи при программировании на языке Java. По целому ряду причин мы не будем использовать классы этого пакета в нашем курсе.

Стандартная библиотека (STL) языка C++ содержит более широкий набор так называемых стандартных контейнеров. Используемые нами в данной секции имена классов и методов будут в значительной мере напоминать имена из этой стандартной библиотеки, более подробное знакомство с которой предусмотрено в рамках последующего курса "Методы хранения и обработки информации".

Определение 10.8. Основными контейнерами являются вектор (vector), перечисление (enumeration), динамический вектор (dynamic vector), стек (stack), очередь (queue), дек (deq), множество (set), одно- и двусвязные списки (lists).

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

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

Пример интерфейса

interface Enumeration {
    // Есть ли еще элементы?
    public boolean hasMoreElements();
    // Взять следующий элемент.
    public Object nextElement(); 
}
// Реализация перечисления для работы с целыми числами.
class Enum implements Enumeration {
    // Вектор, в котором хранятся числа.
    private int[] values;
    // Количество уже извлеченных чисел.
    private int   current;

    // Конструктор.
    public Enum(int[] values) {
        this.values = values;
        current = 0;
    }
    public boolean hasMoreElements() {
        return current < values.length;
    }
    public Object nextElement() {
        return new Integer(values[current++]);
    }
    // Тестовая программа для работы с перечислением.
    public static void main(String[] args) {
        int[] val = new int[7];
        for (int i=0; i<7; i++)
            val[i] = 17 + i;
        Enum e = new Enum(val);
        while (e.hasMoreElements()) {
            System.out.println( ((Integer)(e.nextElement()))
                                .intValue() );
        }
    }
}

Важным моментом здесь является то, что целые числа в языке Java не являются объектами, а из перечисления Enumeration, как это следует из его интерфейса, должны извлекаться объекты. Справиться с этой проблемой помогает класс Integer, определенный в пакете java.lang, обеспечивающий преобразование целого числа в объект "целое число" и обратно. При извлечении очередного элемента с помощью метода nextElement из целого числа, хранящегося в массиве values, конструируется объект Integer, который и возвращается в качестве результата.

Приведенная выше тестовая программа, иллюстрирующая работу с перечислением, создает контейнер, содержащий 7 целых чисел (начиная с 17), а затем последовательно извлекает их. До тех пор, пока в контейнере еще содержатся элементы, осуществляются следующие действия: извлекается очередной объект, который преобразуется к типу Integer, а затем определяется его значение, которое и печатается.

Пакет java.util содержит класс Vector, реализующий динамический вектор. Он несколько более функционален и универсален, чем тот интерфейс, к рассмотрению которого мы сейчас приступим, однако для первого знакомства с данным контейнерным типом наш вариант предпочтительнее. Динамический вектор отличается от обычного тем, что его размер может произвольным образом изменяться в процессе работы с ним.

Пример интерфейса

interface Vector {
    // Конструктор.
    public Vector();
    // Построить перечисление из вектора.
    public Enumeration elements();
    // Пуст ли вектор?
    public boolean isEmpty();	
    // Сделать вектор пустым.
    public void removeAllElements();
    // Получить значение элемента.
    public Object elementAt(int index);
    // Изменить значение элемента.
    public void setElementAt(Object obj, int index);
    // Удалить элемент.
    public void removeElementAt(int index);
    // Добавить элемент в заданную позицию.
    public void insertElementAt(Object obj, int index);
    // Добавить элемент в конец вектора.
    public void addElement(Object obj);
}

Этот интефейс содержит метод elements(), возвращающий контейнер типа Enumeration, что позволяет работать с динамическим вектором, как с перечислением. Назначение остальных методов вполне ясно из комментариев к ним.

Отметим, что элементами этого контейнера могут быть произвольные объекты. В него можно поместить, например, несколько элементов типа Enumeration, несколько строк (тип String ) и векторов (тип Vector ). Единственное, о чем должен заботиться программист при работе с данным контейнером, — это преобразование извлекаемого объекта к его реальному типу.

Для определения типа объекта, извлеченного из контейнера, можно использовать бинарный оператор instanceof, возвращающего true, если его левый операнд принадлежит классу C, указанному в качестве правого операнда. Такое же значение будет и в тех случаях, когда левый операнд является экземпляром любого подкласса класса C, реализует интерфейс C, или принадлежит подклассу, реализующему интерфейс C. В остальных случаях значением данного оператора будет false.

Хранить в динамическом векторе целые или действительные числа, не являющиеся объектами, нельзя. Можно, однако, помещать в вектор объекты типов Integer или Double, соответствующие этим величинам. Подобная техника работы была проиллюстрирована выше на примере класса Enum.

Так как нашей очередной задачей после описания интерфейсов контейнерных классов для нас будет задача их реализации, то мы позволим себе упростить ее. Будем считать, что все рассматриваемые далее контейнеры предназначены для работы не с произвольными объектами, а исключительно с целыми числами.

Стек (см. рис. 10.1) — контейнер, который можно представлять себе в виде трубы с одним запаянным концом, в которую можно добавлять элементы (и вынимать их). Говорят, что стек реализует дисциплину обслуживания LIFO (Last in — first out, последним пришел — первым ушел).

Пример интерфейса

interface Stack {
    // Пуст ли стек?
    boolean empty();
    // Сделать стек пустым.
    void    clear();
    // Добавить число в стек (на вершину).
    void    push(int val);
    // Удалить число с вершины стека.
    int     pop() throws Exception;
    // Получить вершину стека (не удаляя ее).
    int     top() throws Exception;
}

Из пустого стека нельзя взять элемент. По этой причине при работе методов pop и top может возникнуть исключительная ситуация.

Очередь можно представлять себе в виде трубы с двумя концами, движение по которой возможно лишь в одном направлении — от конца очереди к ее началу (рис. 10.2). Говорят, что очередь реализует дисциплину обслуживания FIFO (First in — first out, первым пришел — первым ушел).

Пример интерфейса

interface Queue {
    // Пуста ли очередь?
    boolean empty();
    // Сделать очередь пустой.
    void    clear();
    // Добавить число в очередь (в конец).
    void    push(int val);
    // Удалить число из начала очереди.
    int     pop() throws Exception;
    // Получить начало очереди (не удаляя его).
    int     front() throws Exception;
}

Из пустой очереди, как и из стека, элементы извлекать нельзя.

Дек (double ended queue, двусторонняя очередь) — симбиоз стека и очереди. Его можно представлять себе в виде трубы с двумя открытыми концами, с каждым из которых можно работать независимо (рис. 10.3).

Пример интерфейса

interface Deq {
    // Пуст ли дек?
    boolean empty();
    // Сделать дек пустым.
    void    clear();
    // Добавить число в начало дека.
    void    pushFront(int val);
    // Добавить число в конец дека.
    void    pushBack(int val);
    // Удалить первый элемент дека.
    int     popFront() throws Exception;
    // Удалить последний элемент дека.
    int     popBack() throws Exception;
    // Получить первый элемент дека (не удаляя его).
    int     front() throws Exception;
    // Получить последний элемент дека (не удаляя его).
    int     back() throws Exception;
}

Пустой дек ведет себя аналогично ранее рассмотренным контейнерам.

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

Пример интерфейса

interface Set {
    // Пусто ли множество?
    boolean empty();
    // Сделать множество пустым.
    void    clear();
    // Содержится ли число в множестве?
    boolean search(int val);
    // Добавить число в множество.
    void    insert(int val);
    // Удалить число из множества.
    void    erase(int val);
}

L2-список — линейный двусвязный список — можно представлять себе в виде перекидного календаря или бус, нанизанных на нить. Для списка определены его начало и конец, а также указатель. Указатель всегда находится между элементами списка (в случае перекидного календаря указателю соответствует то место, на котором календарь раскрыт). Графическая иллюстрация L2-списка представлена на рис. 10.4.

Как это видно из приведенного ниже интерфейса, добавление или удаление элементов из списка возможно только рядом с указателем (для того, чтобы вынуть лист из календаря, надо раскрыть его на нужном месте).

Пример интерфейса

interface L2List {
    // Пуст ли список?
    boolean empty();
    // Сделать список пустым.
    void    clear();
    // Передвинуть указатель в начало списка.
    void    toFront();
    // Передвинуть указатель в конец списка.
    void    toBack();
    // Указатель в начале списка?
    boolean begin();
    // Указатель в конце списка?
    boolean end();
    // Передвинуть указатель вперед.
    void    forward() throws Exception;
    // Передвинуть указатель назад.
    void    backward() throws Exception;
    // Получить число за указателем;
    int     after() throws Exception;
    // Получить число перед указателем;
    int     before() throws Exception;
    // Добавить число за указателем;
    void    insertBack(int val);
    // Добавить число перед указателем;
    void    insertFront(int val);
    // Удалить число за указателем.
    int     eraseBack() throws Exception;
    // Удалить число перед указателем.
    int     eraseFront() throws Exception;
}

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

L1-список — линейный односвязный список отличается от L2-списка тем, что двигаться по нему можно только в одном направлении (календарь не разрешается листать назад), а вставлять и удалять элементы — только за указателем.

Пример интерфейса

interface L1List {
    // Пуст ли список?
    boolean empty();
    // Сделать список пустым.
    void    clear();
    // Передвинуть указатель в начало списка.
    void    toFront();
    // Указатель в конце списка?
    boolean end();
    // Передвинуть указатель вперед.
    void    forward() throws Exception;
    // Получить число за указателем;
    int     after() throws Exception;
    // Добавить число за указателем;
    void    insert(int val);
    // Удалить число за указателем.
    int     erase() throws Exception;
}

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

Простое и понятное описание интерфейсов всех рассмотренных выше типов содержится в первой главе учебного пособия [9]. Для получения более полной информации по рассмотренным вопросам можно обратиться к описанию стандартных контейнеров библиотеки языка C++ (книга [12]) и описанию пакета java.util (книги [11] и [13]).

Реализации контейнеров на базе вектора

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

Легко понять, однако, что невозможно реализовать потенциально бесконечные структуры данных, рассмотренные выше, на базе конечного вектора. По этой причине все наши реализации будут реализациями ограниченных контейнеров. При попытке добавить элемент в уже заполненный контейнер должна возникать исключительная ситуация ( Exception ). Фактически это означает необходимость внесения изменений в приведенные выше интерфейсы контейнерных классов, хотя иногда мы будем позволять себе игнорировать данную проблему и не заботиться об обеспечении генерации исключительной ситуации.

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

Определение 10.9. Реализация на базе вектора называется непрерывной, если все элементы контейнера хранятся в векторе непрерывным куском и порядок элементов в имитируемой структуре (если он существует) соответствует порядку элементов в векторе.

В качестве первого примера рассмотрим следующую задачу.

Задача 10.2. Создайте непрерывную реализацию ограниченного стека целых чисел на базе вектора и оцените эффективность полученной программы.

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

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

Идея реализации стека чрезвычайно проста — его дно размещается в начале вектора, а при добавлении элементов они помещаются в последовательные ячейки массива (см. рис. 10.5). Кроме вектора array, содержащего элементы стека, реализация использует переменную head (количество элементов стека). При этом вершина стека имеет индекс head-1, а значения элементов массива с большими индексами не играют никакой роли.

Текст программы

interface Stack {
    boolean empty();
    void    clear();
    void    push(int val) throws Exception;
    int     pop() throws Exception;
    int     top() throws Exception;
}
class StackTest implements Stack {
    private static final int DEFSIZE = 5;
    private int[] array;
    private int   head;

    public StackTest(int size) {
        array = new int[size];
        head = 0;
    }
    public StackTest() {
        this(DEFSIZE);
    }
    public boolean empty() {
        return head == 0;
    }
    public void clear() {
        head = 0;
    }
    public void push(int val) throws Exception {
        array[head++] = val;
    }
    public int pop() throws Exception {
        return array[--head];
    }
    public int top() throws Exception {
        return array[head-1];
    }
    public static void main(String[] args) throws Exception {
        StackTest s = new StackTest();
        while (true) {
            switch (Xterm.inputInt("Action [01234] -> ")) {
              case 0:	
                System.out.println("Stack is " + (s.empty() ?
                                                 "empty" :
                                                 "not empty"));
                break;
              case 1:
                s.clear(); break;
              case 2:
                s.push(Xterm.inputInt("Push int: ")); break;
              case 3:
                System.out.println("Pop int " + s.pop()); break;
              case 4:
                System.out.println("Top = " + s.top()); break;
              default:
                System.out.println("Wrong action, ignore");
            }
        }
    }
}

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

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

Задача 10.3. Создайте непрерывную реализацию ограниченной очереди целых чисел на базе вектора и оцените эффективность полученной программы.

Текст программы

interface Queue {
    boolean empty();
    void    clear();
    void    push(int val) throws Exception;
    int     pop() throws Exception;
    int     front() throws Exception;
}
class QueueTest implements Queue {
    private int[] array;
    private int size, head, tail;
    private int forward(int index) {
        return ++index < array.length ? index : 0;
    }

    public QueueTest(int size) {
        array = new int[size];
        clear();
    }
    public boolean empty() {
        return size == 0;
    }
    public void clear() {
        size = head = 0;
        tail = array.length - 1;
    }
    public void push(int val) throws Exception {
        if(++size >= array.length) throw new Exception();
        array[tail=forward(tail)] = val;
    }
    public int pop() throws Exception {
        int val = front();
        head = forward(head);
        size -= 1;
        return val;
    }
    public int front() throws Exception {
        if(empty()) throw new Exception();
        return array[head];
    }
    public static void main(String[] args) throws Exception {
        QueueTest q = new QueueTest(5);
        while (true) {
            switch (Xterm.inputInt("Action [01234] -> ")) {
              case 0:	
                System.out.println("Queue is " + (q.empty() ?
                                                 "empty" :
                                                 "not empty"));
                break;
              case 1:
                q.clear(); break;
              case 2:
                q.push(Xterm.inputInt("Push int: ")); break;
              case 3:
                System.out.println("Pop int " + q.pop()); break;
              case 4:
                System.out.println("Front = " + q.front()); break;
              default:
                System.out.println("Wrong action, ignore");
            }
        }
    }
}

Основная идея, используемая в этой реализации — "сворачивание вектора в кольцо", что реализуется с помощью метода forward, вычисляющего индекс элемента, следующего за данным. При этом следующим за последним элементом массива считается его самый первый элемент (с индексом 0).

Графическая иллюстрация этой реализации приведена на рис. 10.6. Переменная size здесь содержит количество элементов в очереди, head — индекс самого первого элемента в (непустой) очереди, а tail — последнего ее элемента. Первая из этих трех переменных необходима для того, чтобы отличить пустую очередь от полностью заполненной.

Если не "сворачивать" вектор, то после выполнения $$n$$ (где $$n$$ — длина вектора) последовательных пар операций push и pop над изначально пустой очередью она по-прежнему будет пуста, но положение указателей head и tail сделает невозможным добавление в нее новых элементов.

Интерфейс Queue был изменен так, чтобы попытка добавить элемент в полностью заполненную очередь также приводила к возникновению исключительной ситуации. Реализация на базе "циклического вектора" не приводит к автоматическому возникновению исключительной ситуации, связанной с выходом за границу массива, как это было в предыдущем примере. Поэтому здесь приходится возбуждать исключительную ситуацию явным образом с помощью оператора throw.

Также как и для стека, реализация очереди является достаточно эффективной — все методы имеют константную сложность $$\Theta(1)$$.

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

Любая непрерывная реализация на базе вектора множества или, скажем, трех стеков, имеет, однако, существенный недостаток — некоторые из методов имеют линейную сложность ( $$\Theta(n)$$ ), ибо требуют массовых операций — сдвига части элементов вектора. Как правило, это неприемлемо — высокая временная эффективность реализации обычно является обязательным условием.

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

Определение 10.10. Реализация на базе вектора называется ссылочной, если все элементы контейнера хранятся в одном векторе, а другой вектор — вектор ссылок, определяет реально содержащиеся в имитируемой структуре элементы и их порядок (если он существует).

Иногда (например, в случае двусвязного списка) ссылочная реализация требует использования двух векторов ссылок.

Типичным примером ссылочной реализации является реализация односвязного списка.

Задача 10.4. Постройте ссылочную реализацию ограниченного односвязного списка целых чисел на базе вектора с применением двух векторов ссылок и оцените эффективность полученной программы.

Элементы списка будут размещаться в массиве array, а второй массив — next будем использовать для ссылок. Лучше всего представлять себе элементы списка в виде бусинок на ниточке. При этом все элементы массива, не содержащиеся в списке, нанизаны на другую нитку. Для того чтобы упростить работу с пустым и полностью заполненным списком, полезно завести два фиктивных элемента, к которым прикрепляются концы этих двух нитей (см. рис. 10.7). По историческим причинам будем называть эти элементы "нилом списка" и "нилом свободного места" соответственно, разместив их в двух дополнительных элементах массива ссылок next.

Добавление элемента в список при этом сводится к тому, что элемент (бусинку) надо снять с одной нити и переместить на другую. Удаление из списка производится точно также, только нити меняются местами.

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

В приведенной ниже программе конструктор списка L1ListTest заносит необходимые значения в массив next, используя метод link, обеспечивающий "связывание" двух элементов. Все остальные методы класса имеют константную сложность $$\Theta(1)$$.

Текст программы

interface L1List {
    boolean empty();
    void    clear();
    void    toFront();
    boolean end();
    void    forward() throws Exception;
    int     after() throws Exception;
    void    insert(int val) throws Exception;
    int     erase() throws Exception;
}
class L1ListTest implements L1List {
    // массив элементов.
    private int[] array;
    // массив ссылок.
    private int[] next;
    // "нил" списка.
    private int nilList;
    // "нил" свободного места.
    private int nilFree;
    // индексы элементов до и после указателя.
    private int before, after;
    // связать два элемента, заданные индексами.
    private void link(int first, int second) {
        next[first] = second;
    }
    // захватить место.
    private int mallocIndex() {
        int index = next[nilFree];
        link(nilFree, next[index]);
        return index;
    }
    // освободить место.
    private void freeIndex(int index) {
        link(index, next[nilFree]);
        link(nilFree, index);
    }

    public L1ListTest(int size) {
        array = new int[size];
        next  = new int[size + 2];
        nilList = size;
        nilFree = size + 1;

        link(nilList, nilList);

        link(nilFree, 0);
        for (int i=0; i<size-1; i++)
            link(i, i+1);
        link(size-1, nilFree);

        before = after = nilList;
    }
    public boolean empty() {
        return next[nilList] == nilList;
    }
    public void clear() {
        try {
            toFront();
            while (true)
               erase();
        } catch(Exception e) {
            ;
        }
    }
    public void toFront() {
        before = nilList;
        after  = next[nilList];
    }
    public boolean end() {
        return after == nilList;
    }
    public void forward() throws Exception {
        if(after == nilList) throw new Exception();
        before = after;
        after  = next[after];
    }
    public int after() throws Exception {
        return array[after];
    }
    public void insert(int val) throws Exception {
        int index = mallocIndex();
        link(before, index);
        link(index, after);
        after = index;
        array[index] = val;
    }
    public int erase() throws Exception {
        int val   = array[after];
        int index = after;
        after = next[index];
        link(before, after);
        freeIndex(index);
        return val;
    }
    public static void main(String[] args) throws Exception {
        L1ListTest l = new L1ListTest(5);
        while (true) {
            switch (Xterm.inputInt("Action [01234567] -> ")) {
              case 0:	
                System.out.println("List is " + (l.empty() ?
                                                 "empty" :
                                                 "not empty"));
                break;
              case 1:
                l.clear(); break;
              case 2:
                l.toFront(); break;
              case 3:	
                System.out.println("Pointer " + (l.end() ?
                                                 "is" :
                                                 "is not")+
                                   " in the end of the list");
                break;
              case 4:
                l.forward(); break;
              case 5:
                System.out.println("elem = " + l.after()); break;
              case 6:
                l.insert(Xterm.inputInt("insert: ")); break;
              case 7:
                l.erase(); break;
              default:
                System.out.println("Wrong action, ignore");
            }
        }
    }
}

Более подробные комментарии к ссылочной реализации односвязного списка и других контейнеров можно найти в третьей главе учебного пособия [9].

Ссылочные реализации могут быть применены и для множества, однако для него существует еще одна чрезвычайно изящная реализация, называемая битовой. Она применима, если в множестве $$M$$ могут содержаться только числа в диапазоне от $$0$$ до $$n-1$$ включительно. В этом случае, используя битовый массив $$b[0..n-1]$$, можно полностью описать текущее состояние множества следующим образом: $$i\in M \Leftrightarrow b[i] = 1$$.

Поиск элемента в такой реализации сводится к проверке значения соответствующего элемента массива, а добавление или удаление — к присваиванию единицы или нуля.

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

Определение 10.11. Любая целочисленная функция $$h\colon M \rightarrow \{0 .. n-1\}$$ называется хеш-функцией ( to hash означает разрезать, разделять ).

Основная идея хеширования заключается в том, что исходное множество $$M$$ представляется в виде объединения $$n$$ непересекающихся множеств: $$\displaystyle M = \bigcup_{i=0}^{n-1} M_i$$, где множества $$M_i$$ для $$i=0,1,\ldots, n-1$$ определяются равенствами $$\displaystyle M_i = \{x\in M\colon h(x) = i\}$$.

После этого вся работа со множеством $$M$$ сводится к работе с одним из его подмножеств $$M_i$$. В самом деле, для поиска элемента $$x$$ в множестве достаточно найти $$h(x)$$ и поискать этот элемент в подмножестве $$M_{h(x)}$$. Добавление и удаление элемента $$x$$ совершенно аналогично приводят к работе с подмножеством $$M_{h(x)}$$ (см. рис. 10.9).

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

Весьма важный вопрос — вопрос качества используемой хеш-функции. Легко понять, что самой плохой является постоянная функция, а хорошая функция должна максимально равномерно распределять элементы по подмножествам. На практике, работая со словами, часто применяют функции, подобные следующей: $$h(c_1c_2\ldots c_n) = (c_1 + c_2 + \ldots + c_n) \% 256$$, где $$c_1$$, $$c_2$$ и т.д. — символы слова и одновременно их десятичные коды (предполагается ASCII-кодировка, а не UNICODE).

Словарик ООП

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

Абстрагирование (abstraction) — метод решения задачи, при котором объекты разного рода объединяются общим понятием (концепцией), а затем сгруппированные сущности рассматриваются как элементы единой категории.

Абстракция (abstraction) — существенные характеристики объекта, которые отличают его от всех других видов объектов и четко определяют особенности данного объекта с точки зрения дальнейшего рассмотрения и анализа.

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

Абстрактный метод (abstract method) — метод, который не может быть вызван без предварительного доопределения.

Автоматическая переменная (automatic variable) — переменная, для которой память выделяется автоматически при входе в процедуру (функцию, метод или блок); противопоставляется динамической переменной, память для которой отводится явной командой пользователя.

Автоматическое управление памятью (automatic storage management) — алгоритм распределения памяти, при котором исполнительная система нижнего уровня отвечает за нахождение и повторное использование недоступных (а следовательно, ненужных) блоков памяти; синоним: сборка мусора.

Базовый класс (base class) — класс, из которого порождается другой класс; синонимы: класс-предок, надкласс, родительский класс.

Динамическая переменная (dynamic variable) — переменная, для которой память выделяется явной командой пользователя; противопоставляется автоматической переменной, память для которой отводится автоматически при входе в процедуру (функцию, метод или блок).

Дочерний класс (child class) — класс, определяемый как расширение другого класса, называемого родительским; синонимы: подкласс, производный класс.

Закрытый метод (private method) — метод, который не предназначен для вызова извне объекта; получатель сообщения, которое приводит к вызову такого метода, должен быть обязательно экземпляром того же класса, которому принадлежит отправитель сообщения.

Иерархия классов (class hierarchy) — иерархия, образуемая классами в соответствии с их взаимосвязью "класс — подкласс".

Инкапсуляция (encapsulation) — техника, при которой информация прячется внутри структуры.

Интерфейс (interface) — внешние особенности класса или объекта, придающие ему абстрактную форму и одновременно скрывающие его внутреннее устройство и поведение.

Класс (class) — множество объектов, связанных общностью структуры и поведения; абстрактное описание данных и поведения для совокупности похожих объектов, представители которой называются экземплярами класса.

Конструктор (constructor) — метод, используемый для создания нового объекта; обеспечивает решение двух задач: выделяет память под новую переменную и гарантирует, что переменная инициализируется надлежащим образом.

Контейнерные классы (container classes) — классы, которые используются как структуры данных, содержащие набор элементов.

Метод (method) — процедура или функция, связанная с классом, вызываемая в стиле пересылки сообщений.

Множественное наследование (multiple inheritance) — свойство языка, которое позволяет подклассу наследовать свойства сразу от нескольких надклассов.

Надкласс (superclass) — синоним терминов класс-предок, базовый класс.

Наследование (inheritance) — свойство объектов, посредством которого экземпляры класса получают доступ к данным и методам классов-предков без их повторного определения.

Область видимости, контекст (scope) — применяемый к имени переменной, этот термин означает часть исходного текста программы, в которой идентификатор переменной обозначает именно ее, а не что-либо другое.

Объект (object) — конкретная реализация класса, обладающая характеристиками состояния, поведения и индивидуальности, синоним экземпляра.

Объектно-ориентированное программирование или сокращенно ООП (object-oriented programming) — методология программирования, основанная на представлении программы в виде совокупности объектов, каждый из который является реализацией определенного типа, использующая механизм пересылки сообщений и классы, организованные в иерархию наследования.

Ограничение доступа (encapsulation) — защита отдельных элементов объекта, не затрагивающих существенных характеристик объекта, как целого.

Открытый метод (public method) — метод, который может быть вызван без ограничения извне объекта.

Перегрузка (overload) — использование одного идентификатора для нескольких различных методов или операторов.

Переменная класса (class variable) — поле данных, являющееся общим для всех экземпляров данного класса.

Переменная экземпляра (instance variable) — внутренняя переменная экземпляра класса.

Переопределение метода (override) — действие, происходящее в том случае, когда метод подкласса имеет то же самое имя, что и метод надкласса; метод подкласса имеет приоритет по сравнению с методом надкласса.

Поведение (behavior) — описание объекта в терминах изменения его состояния и передачи сообщений в процессе воздействия или под действием других объектов.

Подкласс (subclass) — синоним потомка, производного или дочернего класса.

Полиморфизм (polymorphism) — свойство, позволяющее использовать один и тот же интерфейс для различных действий; полиморфной переменной, например, может соответствовать несколько различных методов.

Получатель (receiver) — объект, которому посылается сообщение; внутри метода, соответствующего сообщению, получатель идентифицируется в случае языка Java с помощью ключевого слова this.

Производный класс (derived class) — расширение или подкласс другого класса; синонимы: потомок, дочерний класс.

Реализация (implementation) — внутреннее строение класса или объекта, учитывающее особенности его поведения.

Родительский класс (parent class) — непосредственный надкласс данного класса, класс-предок.

Сборка мусора (garbage collector) — техника распределения памяти, при которой исполнительная система во время выполнения программы определяет, какие блоки памяти больше не нужны, и автоматически помечает их, как свободные.

Сообщение (message) — операция связи между объектами; синонимы: вызов метода, оператора.

Терминальный класс (final class) — класс, объявленный с ключевым словом final, обозначающим, что он не может использоваться в качестве базового при определении новых классов и наследовании.

Терминальный метод (final method) — метод, объявленный с ключевым словом final, обозначающим, что он не может переопределяться в подклассах.

Терминатор (finalizer) — метод с именем finalize без аргументов и без возвращаемого значения, автоматически вызываемый исполнительной системой во время выполнения программы перед тем, как объект, для которого этот метод определен, будет уничтожен, если он уже не используется.

Экземпляр (instance) — синоним объекта.

Свойства классов и объектов в языке Java

В этой секции в краткой форме сформулированы основные проявления общих принципов ООП в языке Java.

Класс состоит из данных и методов, работающих с данными.

Объект является конкретным экземпляром класса.

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

Копия переменных экземпляра (не статических) содержится в каждом объекте (экземпляре) класса.

Статические переменные класса связаны с классом. Всегда существует ровно одна копия переменной класса независимо от числа экземпляров класса.

Методам экземпляра (не статическим) неявно передается аргумент this, идентифицирующий объект, над которым производится действие.

Статическим методам класса не передается аргумент this, и, следовательно, они не владеют текущим экземпляром класса, который можно использовать для неявной ссылки на переменные экземпляра или для неявного вызова методов экземпляра.

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

Объект не уничтожается явно. Сборщик мусора автоматически утилизирует объекты, которые больше не используются.

Если в первой строке конструктор не вызывает другой конструктор при помощи this() или конструктор суперкласса при помощи super(), то автоматически вызывается конструктор суперкласса, который не имеет аргументов. В любом случае порождается цепочка вызовов конструкторов.

Если конструктор в классе не определен, то автоматически создается конструктор по умолчанию.

Класс может наследовать переменные и методы другого класса, не объявленные как private, становясь его подклассом, т.е. путем объявления другого класса в блоке extends.

Класс java.lang.Object — суперкласс любого класса по умолчанию. Это корневой класс иерархии классов в языке Java, не имеющий суперкласса. Все классы наследуют методы класса Object.

Перегрузка методов — определение множества методов, имеющих одинаковое имя, но разные списки аргументов.

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

Динамический поиск методов гарантирует вызов корректного метода для объекта, даже если это — экземпляр класса, в котором метод переопределен.

Методы, объявленные как static, final, или private, не могут быть переопределены и не могут служить объектами динамического поиска. Это позволяет компилятору использовать inline-подстановку, оптимизируя их вызов.

Из подклассов можно явно вызывать переопределенные методы суперкласса с помощью ключевого слова super.

Можно явно ссылаться на скрытые переменные с помощью ключевого слова super.

Данные и методы могут быть скрыты и инкапсулированы внутри класса благодаря модификаторам видимости private и protected. Переменные класса, объявленные как public, видимы везде. Переменные класса без модификаторов видимости видны только внутри пакета.

Абстрактный метод не имеет тела (т.е. реализации).

Абстрактный класс содержит абстрактные методы. Методы должны быть реализованы в подклассе прежде, чем будут созданы экземпляры этого подкласса.

Интерфейс в языке Java — это набор абстрактных методов и констант (переменных, объявленных как final static ). Объявление интерфейса создает новый тип данных.

Класс реализует интерфейс, объявляя его в блоке implements и создавая тело метода для каждого из абстрактных методов интерфейса.

Задачи для самостоятельного решения

Задача 10.5. Реализуйте класс Complex, позволяющий выполнять над комплексными числами четыре основных арифметических действия, а также вычислять модуль и аргумент данного числа.

Задача 10.6. Реализуйте класс R3Vector, позволяющий выполнять над векторами в пространстве следующие операции: сложение, вычитание, умножение на число, вычисление скалярного, векторного и смешанного произведений.

Задача 10.7. Реализуйте класс Matrix2, позволяющий выполнять над квадратными матрицами порядка два следующие операции: сложение, вычитание, умножение на число, перемножение, вычисление определителя и обратной матрицы.

Задача 10.8. Создайте непрерывную реализацию ограниченного дека целых чисел на базе вектора и оцените эффективность полученной программы.

Задача 10.9. Создайте непрерывную реализацию ограниченного множества целых чисел на базе вектора, называемую "последовательный поиск", и оцените эффективность построенной программы.

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

Задача 10.10. Создайте непрерывную реализацию ограниченного множества целых чисел на базе вектора, называемую "двоичный поиск", и оцените эффективность построенной программы.

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

Задача 10.11. Создайте непрерывную реализацию двух стеков целых чисел, ограниченных в совокупности, на базе вектора и оцените эффективность полученной программы.

Указание Интерфейс этого контейнера предполагает наличие дополнительного аргумента (по сравнению с классом Stack ), указывающего номер стека, у методов empty, push, pop и top. Ограниченность в совокупности означает, что добавление в любой из стеков не должно приводить к возникновению исключительной ситуации, если только суммарное количество элементов в стеках меньше, чем длина вектора.

Задача 10.12. Создайте непрерывную реализацию трех стеков целых чисел, ограниченных в совокупности, на базе вектора и оцените эффективность полученной программы.

Указание См. указание к предыдущей задаче.

Задача 10.13. Постройте ссылочную реализацию ограниченного двусвязного списка целых чисел на базе вектора с применением двух векторов ссылок и оцените эффективность полученной программы.

Задача 10.14. Создайте битовую реализацию множества целых чисел, которое может содержать элементы от $$0$$ до $$n-1$$ включительно ( $$n < 2^{31}$$ ), и оцените эффективность полученной программы.

Задача 10.15. Создайте реализацию ограниченного множества целых чисел с помощью хеширования, взяв в качестве хеш-функции остаток от деления числа на 10.