авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |

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

-- [ Страница 5 ] --

При вызове конструктора выведенного класса всегда происходит вы зов (явный или неявный) конструктора его непосредственного базового класса. В случае явного вызова это реализуется с помощью оператора 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;

Глава III. Применение ООП к разработке программных проектов } } // Класс "одноугольник", реализующий интерфейс фигуры.

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;

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

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

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

• для методов, объявленных с ключевым словом static;

• для методов, объявленных с ключевым словом private;

• для методов, объявленных с ключевым словом final;

• для всех методов final-класса.

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

Квалификаторы доступа private, protected и public определяют доступность данных или метода, реализуя возможность инкапсуляции.

Только методы, описанные с использованием ключевого слова public, являются общедоступными. Именно они определяют интерфейс объекта.

Все внутренние данные объекта, как правило, описываются с квалифи катором private, что запрещает работу с ними извне объекта. Ключевое слово protected обеспечивает работу с так описанными компонентами 168 Глава III. Применение ООП к разработке программных проектов методам выведенных классов. Во всех рассмотренных выше примерах ин терфейс объекта (его 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.

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

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

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

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

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

Определение 1.8. Основными контейнерами являются вектор (vector), перечисление (enumeration), динамический вектор (dynamic §1. Основы объектно-ориентированного программирования 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;

i7;

i++) 170 Глава III. Применение ООП к разработке программных проектов 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);

§1. Основы объектно-ориентированного программирования ¦¤  ©§ ¤ ¤     ¤¦#!

§ $"      Рис. 1. Стек // Удалить элемент.

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.

Так как нашей очередной задачей после описания интерфейсов кон тейнерных классов для нас будет задача их реализации, то мы позволим 172 Глава III. Применение ООП к разработке программных проектов ¦!¦   ¦" $# ¦© §  ¦¤  § Рис. 2. Очередь себе упростить ее. Будем считать, что все рассматриваемые далее кон тейнеры предназначены для работы не с произвольными объектами, а исключительно с целыми числами.

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

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

interface Stack { // Пуст ли стек?

boolean empty();

// Сделать стек пустым.

void clear();

// Добавить число в стек (на вершину).

void push(int val);

// Удалить число с вершины стека.

int pop() throws Exception;

// Получить вершину стека (не удаляя ее).

int top() throws Exception;

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

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

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

interface Queue { // Пуста ли очередь?

boolean empty();

// Сделать очередь пустой.

void clear();

§1. Основы объектно-ориентированного программирования ¦    " $# ¦    ¦¦ © §    !¦"   ¦© §  $#  ¦!  ¦    § ¦¦"  ¦¤  $   § Рис. 3. Дек // Добавить число в очередь (в конец).

void push(int val);

// Удалить число из начала очереди.

int pop() throws Exception;

// Получить начало очереди (не удаляя его).

int front() throws Exception;

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

Дек (double ended queue, двусторонняя очередь) симбиоз стека и очереди. Его можно представлять себе в виде трубы с двумя открытыми концами, с каждым из которых можно работать независимо (рис. 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;

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

174 Глава III. Применение ООП к разработке программных проектов  © # ¦ §  !# # §  #  ¦!¤!¦¤ # " ¦¦!¤!¦¤ # # "  ¦!  ¦" $# "       "       ¦#   ©#   ©  ¦ ¤ § # " "       Рис. 4. L2-список Понятие множества является общеизвестным, как и основные опера ции над ним. Напомним только, что если в множество добавляется эле мент, который в нем уже содержался, то множество не меняется. Мно жество остается неизменным и при удалении элемента, которого в нем не было. Так как последнее замечание применимо и к пустому множеству, то при работе с данным контейнером исключительная ситуация возникнуть не может.

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

interface Set { // Пусто ли множество?

boolean empty();

// Сделать множество пустым.

void clear();

// Содержится ли число в множестве?

boolean search(int val);

// Добавить число в множество.

void insert(int val);

// Удалить число из множества.

void erase(int val);

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

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

§1. Основы объектно-ориентированного программирования Пример интерфейса.

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;

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

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

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

interface L1List { // Пуст ли список?

boolean empty();

176 Глава III. Применение ООП к разработке программных проектов // Сделать список пустым.

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]).

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

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

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

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

§1. Основы объектно-ориентированного программирования ¦¦¤  ©§ ¤    0 head-...

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

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

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

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

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

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

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

interface Stack { boolean empty();

void clear();

void push(int val) throws Exception;

int pop() throws Exception;

Глава III. Применение ООП к разработке программных проектов 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;

§1. Основы объектно-ориентированного программирования case 4:

System.out.println("Top = " + s.top());

break;

default:

System.out.println("Wrong action, ignore");

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

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

Задача 1.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();

} Глава III. Применение ООП к разработке программных проектов 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");

} } } } §1. Основы объектно-ориентированного программирования §¤  ¦ n- ©  ...

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

Графическая иллюстрация этой реализации приведена на рисунке 6.

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

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

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

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

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

182 Глава III. Применение ООП к разработке программных проектов    §¦     ¤    ©     Рис. 7. Идея ссылочной реализации односвязного списка Любая непрерывная реализация на базе вектора множества или, ска жем, трех стеков, имеет, однако, существенный недостаток некоторые из методов имеют линейную сложность ((n)), ибо требуют массовых сдвига части элементов вектора. Как правило, это неприем операций лемо высокая времення эффективность реализации обычно является а обязательным условием.

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

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

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

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

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

Элементы списка будут размещаться в массиве array, а второй мас сив next будем использовать для ссылок. Лучше всего представлять себе элементы списка в виде бусинок на ниточке. При этом все элементы §1. Основы объектно-ориентированного программирования n- 0 1 n-1 n+1 n 1 3 n-...

0 1 2 #$  (  ($6F$¤D¤¦ ( (© #!

 '&¦ §  §!3#6¦  Рис. 8. Ссылочная реализация односвязного списка массива, не содержащиеся в списке, нанизаны на другую нитку. Для того чтобы упростить работу с пустым и полностью заполненным списком, по лезно завести два фиктивных элемента, к которым прикрепляются концы этих двух нитей (см. рис. 7). По историческим причинам будем называть эти элементы нилом списка и нилом свободного места соответствен но, разместив их в двух дополнительных элементах массива ссылок next.

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

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

В приведенной ниже программе конструктор списка L1ListTest зано сит необходимые значения в массив next, используя метод link, обеспе чивающий связывание двух элементов. Все остальные методы класса имеют константную сложность (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 { Глава III. Применение ООП к разработке программных проектов // массив элементов.

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;

isize-1;

i++) link(i, i+1);

link(size-1, nilFree);

before = after = nilList;

} public boolean empty() { return next[nilList] == nilList;

} §1. Основы объектно-ориентированного программирования 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:

186 Глава III. Применение ООП к разработке программных проектов 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 M b[i] = 1.

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

§1. Основы объектно-ориентированного программирования M1 M2 M n M0...

h(x) 0 1 2 n...

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

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

Основная идея хеширования заключается в том, что исходное мно жество M представляется в виде объединения n непересекающихся мно n жеств: M = Mi, где множества Mi для i = 0, 1,..., n 1 определяются i= равенствами Mi = {x M : h(x) = i}.

После этого вся работа со множеством M сводится к работе с одним из его подмножеств Mi. В самом деле, для поиска элемента x в множестве достаточно найти h(x) и поискать этот элемент в подмножестве M h(x).

Добавление и удаление элемента x совершенно аналогично приводят к работе с подмножеством Mh(x) (см. рис. 9).

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

Весьма важный вопрос вопрос качества используемой хеш-функции.

Легко понять, что самой плохой является постоянная функция, а хоро шая функция должна максимально равномерно распределять элементы по подмножествам. На практике, работая со словами, часто применяют функции, подобные следующей: h(c1 c2... cn ) = (c1 + c2 +... + cn )%256, 188 Глава III. Применение ООП к разработке программных проектов где c1, c2 и т.д. символы слова и одновременно их десятичные коды (предполагается ASCII-кодировка, а не UNICODE).

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

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

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

Абстрактный класс (

Abstract

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

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

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

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

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

синоним: сборка мусора.

Базовый класс (base class) класс, из которого порождается другой класс;

синонимы: класс-предок, надкласс, родительский класс.

Динамическая переменная (dynamic variable) переменная, для кото рой память выделяется явной командой пользователя;

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

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

синонимы: подкласс, произ водный класс.

Закрытый метод (private method) метод, который не предназначен для вызова извне объекта;

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

§1. Основы объектно-ориентированного программирования Иерархия классов (class hierarchy) иерархия, образуемая классами в соответствии с их взаимосвязью класс подкласс.

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

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

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

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

Конструктор (constructor) метод, используемый для создания ново го объекта;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

метод подкласса имеет приоритет по сравнению с методом над класса.

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

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

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

полиморфной пере менной, например, может соответствовать несколько различных методов.

Получатель (receiver) объект, которому посылается сообщение;

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

Производный класс (derived class) расширение или подкласс другого класса;

синонимы: потомок, дочерний класс.

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

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

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

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

синонимы:

вызов метода, оператора.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

192 Глава III. Применение ООП к разработке программных проектов Класс может наследовать переменные и методы другого класса, не объявленные как private, становясь его подклассом, т.е. путем объявле ния другого класса в блоке extends.

Класс java.lang.Object суперкласс любого класса по умолчанию.

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

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

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

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

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

Это позволяет компилятору использовать inline-подстановку, оптимизи руя их вызов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

194 Глава III. Применение ООП к разработке программных проектов Задача 1.14. Создайте битовую реализацию множества целых чисел, которое может содержать элементы от 0 до n 1 включительно (n 2 31 ), и оцените эффективность полученной программы.

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

§ 2. Проект Выпуклая оболочка Этот параграф посвящен, прежде всего, решению одной конкретной задачи средней степени сложности нахождению выпуклой оболочки по следовательно поступающих точек плоскости и вычислению двух ее мет рических характеристик. Дополнительная информация об этом проекте может быть найдена в книге [9].

В нем также рассматриваются аплеты, которые используются в каче стве основы для создания простейшего графического интерфейса (GUI graphics user interface), что дает возможность решать задачи на изобра жение графиков функций и различных графических объектов. Вопросы создания аплетов обсуждаются практически во всех изданиях, посвящен ных языку Java, в том числе и в книгах [10], [11] и [13].

1. Постановка задачи. Напомним сначала два определения, связанные с важнейшим математическим понятием свойством выпуклости мно жеств.

Определение 2.1. Множество M называется выпуклым, если для лю бых двух его точек весь отрезок прямой, соединяющий эти точки, при надлежит множеству: M выпукло (x1, x2 M [x1, x2 ] M ).

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

Определение 2.2. Выпуклой оболочкой conv(M ) множества M назы вается наименьшее выпуклое множество, содержащее M.

Выпуклая оболочка любого выпуклого множества совпадает с ним.

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

Выпуклой оболочкой двух точек на плоскости является отрезок, их со единяющий;

выпуклая оболочка окружности круг;

выпуклая оболочка трех точек, не лежащих на одной прямой, треугольник.

Теперь можно сформулировать основную задачу.

§2. Проект Выпуклая оболочка Рис. 10. Выпуклая оболочка точек плоскости Задача 2.1. Напишите программу, находящую выпуклую оболочку последовательно поступающих точек плоскости и вычисляющую ее пери метр и площадь. Решение должно быть индуктивным, что означает опре деление выпуклой оболочки и вычисление ее характеристик сразу после поступления очередной точки с использованием методов теории индук тивных функций.

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

Мы будем трактовать поставленную задачу следующим образом: реа лизовать класс Convex с методами • add добавить новую точку и построить выпуклую оболочку;

• perimeter вычислить периметр;

• area вычислить площадь.

Договоримся придерживаться стратегии вычисления всех характери стик оболочки сразу при добавлении новой точки (в методе add);

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

Если обозначить множество R2 точек плоскости через X, а совокуп ность всех выпуклых фигур на плоскости через P, то тройка функций f : X P выпуклая оболочка последовательности точек, g : X R ее периметр и h : X R ее площадь в совокупности задает индуктивную функцию F : X P R R, F = (f, g, h).

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

Пусть для некоторой последовательности точек плоскости выпуклая обо лочка, а также ее периметр и площадь, уже известны. После добавления новой точки x X возможны две ситуации: либо точка x попадает внутрь оболочки, либо вне ее.

196 Глава III. Применение ООП к разработке программных проектов Рис. 11. Добавление новой точки В первом случае выпуклая оболочка (а также ее периметр и площадь) не изменяются. Во втором изменения происходят, но информации, хра нящейся в функции F (выпуклой оболочки, ее периметра и площади) вместе с координатами точки x явно достаточно для определения новой выпуклой оболочки и ее изменившихся характеристик.

Хорошей моделью для описания изменяющейся оболочки является следующая: предположим, что во вновь добавляемой точке x располо жена лампочка, освещающая часть ребер старой оболочки, которые мы так и будем называть освещенными. Для получения новой оболочки необходимо, как это хорошо видно из рисунка 11, удалить все освещенные ребра, а концы оставшейся ломаной соединить двумя новыми ребрами с добавляемой точкой x.

Если добавляемая точка лежит на продолжении одного из ребер, то оболочка должна измениться так, как показано на рисунке 12. Поэтому ребро, на продолжении которого лежит точка x, мы также будем считать освещенным.

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

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

§2. Проект Выпуклая оболочка Рис. 12. Добавление точки специальный случай Выпуклая оболочка, в любом случае являясь фигурой на плоскости, в процессе добавления точек модифицируется, превращаясь из пустого множества в точку, затем отрезок и, наконец, многоугольник. Подобная ситуация является типичной для использования интерфейса и нескольких различных классов, его реализующих.

Интерфейс Figure должен содержать общие для всех возможных слу чаев выпуклой оболочки методы add, perimeter и area, а его реализа циями будут являться классы нульугольник (Void), одноугольник (Point), двуугольник (Segment) и многоугольник (Polygon). Каждый из этих классов обязан обеспечивать реализацию всех методов интерфей са Figure, при этом метод add должен в качестве аргумента получать добавляемую точку, а возвращать выпуклую оболочку, перевычисленную с ее учетом.

Следовательно, необходим класс, который мы назовем R2Point, пред ставляющий точку на плоскости и обеспечивающий все необходимые дей ствия над объектами этого типа. Его вполне достаточно для реализации классов Void, Point и Segment, ибо в первом случае никакой информации в фигуре хранить вообще не нужно, а в двух последних нужно хранить только один (для одноугольника ) или два (для двуугольника ) эк земпляра класса R2Point, представляющие соответственно единственную или две концевых точки этих выпуклых оболочек.

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

198 Глава III. Применение ООП к разработке программных проектов Figure Deq R2Point Convex ConvexTest Void Point Segment Polygon Рис. 13. Иерархия классов проекта Выпуклая оболочка Итак, класс Deq будет представлять собой непрерывную реализацию дека объектов типа R2Point, а класс Polygon можно просто сделать выве денным (дочерним) для него. При этом класс Polygon оказывается одно временно реализующим (implements) интерфейс Figure и расширяющим (extends) класс Deq.

Это завершает проектирование иерархии классов, необходимой для ре шения поставленной задачи. Результат представлен на рисунке 13.

В заключение данной секции разберемся с тем, как должны быть устроены реализации классов Void, Point и Segment. Для нульуголь ника все очевидно методы perimeter и area возвращают нулевые зна чения, а возвращаемым значением метода add должен быть объект типа Point.

Класс одноугольник уже должен иметь конструктор с аргументом типа R2Point, сохраняющий эту точку в своей private-компоненте. Пе риметр и площадь здесь также являются нулевыми, а метод add может возвратить как объект типа Segment, так и неизмененный объект Point.

Последнее должно иметь место в случае совпадения вновь добавляемой точки с уже имеющейся. Таким образом, реализация класса Point тре бует наличия в классе R2Point метода equal, позволяющего сравнивать точки плоскости на равенство. Напомним, что оператор == для объектов ссылочных типов возвращает true только в случае равенства ссылок, а не внутреннего содержания объектов.


Класс двуугольник обязан иметь две компоненты типа R2Point, в которые конструктором класса заносятся его концевые точки. Площадь любого двуугольника нулевая, а периметром естественно считать удво енную длину отрезка (сравните двуугольник с треугольником). Добав ление точки в данном случае может привести к трем различным ситуаци ям: двуугольник может превратиться в треугольник, он может остаться двуугольником, но изменить одну из своих концевых точек, и, нако нец, он может совсем не измениться. Класс R2Point должен обеспечивать методы, которые позволят различать эти ситуации, а итоговый вариант §2. Проект Выпуклая оболочка реализации классов Void, Point и Segment приведен в последней секции данного параграфа на странице 212.

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

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

Ряд фактов из аналитической геометрии и векторной алгебры яв ляются необходимой базой для решения сформулированных задач, одна ко только знание элементов вычислительной геометрии позволяет полу чить достаточно эффективные решения. Простейшим примером может служить задача вычисления площади треугольника по известным коор динатам его вершин. Известная из средней школы формула Герона S= p(p a)(p b)(p c) требует большого числа умножений и четырех относительно медленно выполняемых операций извлечения квадратного корня. Основанная на связи площади с векторным произведением формула S = |a b| использует всего три умножения, одно из которых на самом деле сво дится к сдвигу, что позволяет найти площадь треугольника значительно быстрее.

Бльшую часть методов, о которых будет идти речь в текущей секции, о целесообразно реализовать в виде методов класса (статических методов).

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

Расстояние d между двумя точками на плоскости можно посчитать по известной формуле d = (x1 x2 )2 + (y1 y2 )2, которая и используется в реализации метода dist. Два объекта типа R2Point соответствуют сов падающим точкам плоскости тогда и только тогда, когда попарно равны их координаты, что позволяет реализовать метод equal.

public static double dist(R2Point a, R2Point b) { return Math.sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

200 Глава III. Применение ООП к разработке программных проектов } public static boolean equal(R2Point a, R2Point b) { return a.x==b.x && a.y==b.y;

} public static double area(R2Point a, R2Point b, R2Point c) { return 0.5*((a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x));

} Для вычисления площади треугольника в методе area применена уже цитированная выше формула, основанная на следующем факте из век торной алгебры: модуль векторного произведения двух векторов равен площади параллелограмма, натянутого на эти вектора. Напомним, что векторным произведением a b двух векторов a и b называется вектор c, перпендикулярный векторам a и b, такой, что |c| = |a||b| sin, где угол между векторами a и b. Одно из двух возможных направлений век тора c при этом определяется по правилу буравчика (при повороте ручки по направлению от a к b буравчик перемещается по направлению вектора c).

Часто полезно использовать запись этого определения в координатах.

Если a = (ax, ay, az ), а b = (bx, by, bz ), то координаты вектора c находятся по формуле ijk c= = (ay bz az by )i + (az bx ax bz )j + (ax by ay bx )k.

ax ay az bx by bz В том случае, когда вектора a и b расположены на плоскости, их век торное произведение имеет единственную не нулевую компоненту, вычис ление которой и реализовано в методе area. Обратите внимание на то, что так вычисленная площадь является ориентированной, то есть может быть отрицательной.

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

public static boolean isTriangle(R2Point a, R2Point b, R2Point c) { return area(a, b, c) != 0.0;

} public boolean inside(R2Point a, R2Point b) { return (a.x = x && x = b.x || a.x = x && x = b.x) && (a.y = y && y = b.y || a.y = y && y = b.y);

§2. Проект Выпуклая оболочка T T T A B A B B A a) S 0 b) S 0 c) S Рис. 14. Освещенность ребра из точки } Перед тем, как реализовать метод light, позволяющий выяснить, освещено ли ребро [a, b] выпуклой оболочки из точки t, дадим строгое определение освещенности.

Определение 2.3. Ребро [a, b] называется освещенным из точки t, если ориентированная площадь треугольника, образованного точками a, b и t отрицательна, либо если точка t расположена на прямой, проходящей через точки a и b, вне отрезка [a, b].

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

public boolean light(R2Point a, R2Point b) { double s = area(a, b, this);

return s 0.0 || ( s == 0.0 && ! inside(a, b));

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

На первом шаге решения этой задачи необходимо выяснить, пересека ются ли ограничивающие прямоугольники (bounding boxes) этих отрезков.

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

202 Глава III. Применение ООП к разработке программных проектов Пусть координаты граничных точек первого отрезка P1 P2 равны (x1, y1 ) и (x2, y2 ), а второго P3 P4 (x3, y3 ) и (x4, y4 ). Тогда координаты ле вого нижнего угла ограничивающего прямоугольника первого отрезка бу дут равны (x1, y1 ), а правого верхнего угла (x2, y2 ), где x1 = min(x1, x2 ), y1 = min(y1, y2 ), x2 = max(x1, x2 ) и y2 = max(y1, y2 ). Аналогично опреде ляются координаты (x3, y3 ) и (x4, y4 ) левого нижнего и правого верхнего углов ограничивающего прямоугольника второго отрезка.

Ограничивающие прямоугольники пересекаются тогда и только тогда, когда пересекаются их проекции на каждую из двух осей, что сводится к истинности следующего предиката x2 x3 x4 x1 y2 y3 y4 y1.

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

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

Проверка факта пересечения отрезка с прямой осуществляется с помо щью векторных произведений следующим образом. Точки P3 и P4 лежат по разные стороны от прямой P1 P2, если векторы P1 P3 и P1 P4 имеют различную ориентацию относительно вектора P1 P2, то есть, если знаки векторных произведений P1 P3 P1 P2 и P1 P4 P1 P2 различны.

Таким образом, отрезки P1 P2 и P3 P4 пересекаются тогда и только то гда, когда одновременно выполняются следующие три условия:

1) пересекаются ограничивающие их прямоугольники;

2) (P1 P3 P1 P2 ) · (P1 P4 P1 P2 ) 0;

3) (P3 P1 P3 P4 ) · (P3 P2 P3 P4 ) 0.

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

4. Реализация класса Polygon. Нам осталось реализовать методы perimeter, area и add класса Polygon. Как это уже отмечалось при уточ нении постановки задачи, вся работа по модификации выпуклой оболоч ки и перевычислению ее площади и периметра должна проводиться при добавлении новой точки, а действие методов perimeter и area будет сво диться просто к выдаче уже вычисленных ранее значений, хранящихся в private-компонентах.

§2. Проект Выпуклая оболочка class Polygon extends Deq implements Figure { private double s, p;

public double perimeter() { return p;

} public double area() { return s;

}...

} Для того чтобы реализовать метод add и конструктор класса Polygon, необходимо аккуратно разобраться с тем, как именно вершины выпуклой оболочки хранятся в деке. Определение 2.3 освещенности, данное выше, предполагает, что все вершины оболочки расположены в деке последова тельно, одна за другой. При этом важен порядок обхода против часовой стрелки, называемый также ориентацией.

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

public Polygon(R2Point a, R2Point b, R2Point c) { pushFront(b);

if (b.light(a, c)) { pushFront(a);

pushBack(c);

} else { pushFront(c);

pushBack(a);

} p = R2Point.dist(a, b) + R2Point.dist(b, c) + R2Point.dist(c, a);

s = Math.abs(R2Point.area(a, b, c));

} Назовем ребро AB (см. рис. 15), соединяющее конец дека с его нача лом, текущим. Так как в деке в каждый момент времени доступны только два элемента начало и конец, то и работать можно только с текущем ребром многоугольника. Текущее ребро многоугольника, впрочем, легко сменить: если переместить один элемент из начала дека в конец, то мно гоугольник не изменится, а текущем ребром станет ребро BC (следующее за AB в порядке против часовой стрелки). Если переместить из начала дека в конец еще один элемент, то текущим станет ребро CD и т.д.

204 Глава III. Применение ООП к разработке программных проектов B T A Рис. 15. Добавление новой точки При добавлении новой точки возможны два случая. Если в много угольнике освещенных ребер нет, то это означает, что новая точка попала внутрь или на границу старой выпуклой оболочки, и, следовательно, де лать ничего не надо. Если же освещенные ребра есть, то их надо удалить и соединить концы оставшейся ломаной с новой точкой.

При реализации метода add в этом случае необходимо для всех осве щенных ребер выпуклой оболочки выполнить следующие действия: уда лить это ребро, уменьшить периметр p оболочки на его длину и увеличить площадь s оболочки на величину, равную площади треугольника, обра зованного удаляемым ребром и добавляемой точкой. После этого необхо димо добавить к оболочке два новых ребра, а к ее периметру сумму их длин (см. рис. 15).

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

private void grow(R2Point a, R2Point b, R2Point t) { p -= R2Point.dist(a, b);

s += Math.abs(R2Point.area(a, b, t));

} Полный текст построенной программы приведен ниже, в последней секции текущего параграфа.

5. Аплеты и работа с ними. До сих пор мы не использовали бога тейших возможностей, предоставляемых различными библиотеками язы ка Java, которые позволяют создавать удобные графические интерфейсы (GUI), ограничиваясь вводом/выводом текстовой информации с помощью класса Xterm. Вопросы создания полноценных графических интерфейсов выходят за рамки нашего курса, однако с простейшими методами вывода графической информации познакомиться весьма полезно.

Наилучший способ для этих целей использование аплетов (applets).

Аплеты значительно отличаются от обычных программ на языке Java, §2. Проект Выпуклая оболочка которые мы рассматривали до сих пор. Одним из важнейших отличий является то, что аплет не содержит метода main и не может быть запущен самостоятельно.

Аплеты запускаются с помощью браузера или специализированной программы для просмотра аплетов appletviewer, а для создания апле тов необходимо реализовывать подкласс класса Applet, определенного в пакете java.applet, являющимся составной частью библиотеки AWT.

Для целей вывода графической информации достаточно в классе, вы веденном из класса Applet, переопределить метод paint. Мы познако мимся только с несколькими простейшими графическими примитивами:

• setColor установить цвет, которым будут изображаться выво димые объекты;

• drawLine изобразить отрезок прямой линии;

• drawRect изобразить границу прямоугольника;

• drawOval изобразить границу овала;

• fillRect изобразить заполненный прямоугольник;

• fillOval изобразить заполненный овал.

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

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

Вот одно из возможных решений этой задачи.

Текст аплета.

import java.awt.*;

import java.applet.*;

public class Primitives extends Applet { public void paint (Graphics g) { g.fillRect(20, 20, 40, 60);

g.setColor(Color.red);

g.drawLine(2, 2, 80, 80);

g.drawOval(120, 120, 30, 40);

g.drawRect(170, 170, 10, 15);

g.setColor(Color.blue);

g.fillOval(20, 150, 30, 30);

} } Операторы import обеспечивают подключение необходимых клас сов библиотеки AWT для компиляции этой программы, выполняемой обычным образом. После того, как компилятором будет создан файл Глава III. Применение ООП к разработке программных проектов Primitives.class, аплет можно запустить только создав дополнитель но еще один файл Primitives.html. Именно он должен быть указан в качестве аргумента программе appletviewer или браузеру. Содержимое этого файла может быть примерно таким.

HTML-файл.

HTMLBODY APPLET code="Primitives.class" width=200 height=200/APPLET /BODY/HTML Содержательная информация здесь сводится к указанию имени запус каемого аплета и размеру окна, в котором этот аплет будет работать. По сле создания данного файла можно, наконец, запустить аплет, выполнив команду appletviewer Primitives.html Заметим, что начало координат размещается в левом верхнем углу окна, а ось ординат направлена вниз. Других комментариев созданный нами аплет не требует.

Рассмотрим более интересную задачу на построение графика функ ции.

Задача 2.3. Создайте аплет, изображающий в окне размером 200x оси координат и график функции y = x3 x на промежутке [2, 2].

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

Текст аплета.

import java.awt.*;

import java.applet.*;

public class FuncGraph extends Applet { private static final int SIZE = 200;

private static final double k = 50.;

private int f(double x) { return SIZE/2 - (int)(k * (x*(x*x-1)));

} public void paint (Graphics g) { g.drawLine(0, SIZE/2, SIZE-1, SIZE/2);

g.drawLine(SIZE/2, 0, SIZE/2, SIZE-1);

g.setColor(Color.red);

§2. Проект Выпуклая оболочка Рис. 16. Результат работы аплета for (int i=0;

iSIZE;

i++) { double x = (i - SIZE/2) / k;

g.drawOval(i, f(x), 1, 1);

} } } Файл для запуска аплета вполне аналогичен предыдущему случаю:

HTML-файл.

HTMLBODY APPLET code="FuncGraph.class" width=200 height=200/APPLET /BODY/HTML Построим теперь график функции, заданной в полярных координатах.

Задача 2.4. Создайте аплет, изображающий в окне размером 200x график функции, задаваемой в полярных координатах (r, ) соотношени ем r = sin 3.

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

Текст аплета.

208 Глава III. Применение ООП к разработке программных проектов import java.awt.*;

import java.applet.*;

public class FuncPolGraph extends Applet { private static final int SIZE = 200;

private static final double k = 95.;

private int x(double fi) { return SIZE/2 + (int)(k * Math.sin(3.*fi) * Math.cos(fi));

} private int y(double fi) { return SIZE/2 - (int)(k * Math.sin(3.*fi) * Math.sin(fi));

} public void paint (Graphics g) { setBackground(Color.white);

g.setColor(Color.blue);

int xp = x(0.), yp = y(0.);

for (double fi=0.;

fi2.*Math.PI;

fi+=Math.PI/180.) { if (Math.sin(3.*fi) 0) continue;

g.drawLine(xp, yp, x(fi), y(fi));

xp = x(fi);

yp = y(fi);

} } } HTML-файл.

HTMLBODY APPLET code="FuncPolGraph.class" width=200 height=200/APPLET /BODY/HTML Результат работы этой программы приведен на рисунке 16.

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

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

Задача 2.6. Создайте аплет, изображающий в окне границу объеди нения двух стандартных прямоугольников (со сторонами, параллельными осям координат), координаты углов которых предварительно вводятся с помощью методов класса Xterm.

Задача 2.7. Создайте аплет, изображающий в окне размером 600x график функции, заданной параметрически: x = sin 2, y = cos 3.

§2. Проект Выпуклая оболочка Задача 2.8. Создайте аплет, изображающий в окне размером 600x линии уровня функции z = xy.

Задача 2.9. Создайте аплет, изображающий в окне размером 600x траекторию движения шара с начальными координатами (x1, x2 ) и скоро стью (v1, v2 ) в квадратном билльярде со стороной единичной длины.

Задача 2.10. Модифицируйте текст эталонного проекта Выпуклая оболочка так, чтобы индуктивно определить:

a) среднее арифметическое значений функции sin(xy) в вершинах выпук лой оболочки;

b) максимальное значение функции sin(xy) в серединах сторон выпуклой оболочки;

c) мощность множества пересечения границы выпуклой оболочки с поло сой 1 y 1;

d) площадь части выпуклой оболочки, расположенной внутри кольца 1 x2 + y 2 4;

e) периметр части выпуклой оболочки, расположенной внутри кольца 1 x2 + y 2 4;

f) количество ребер выпуклой оболочки, целиком расположенных внутри квадрата с вершинами (0, 0), (0, 3), (3, 0) и (3, 3);

g) количество ребер выпуклой оболочке, параллельных осям координат;

h) количество ребер выпуклой оболочке, параллельных сторонам задан ного треугольника;

i) угол между максимальным и минимальным ребрами выпуклой оболоч ки;

j) лежит ли заданная точка плоскости внутри выпуклой оболочки.

Задача 2.11. Модифицируйте текст эталонного проекта Выпуклая оболочка так, чтобы индуктивно определить:

a) расстояние от выпуклой оболочки до заданной точки;



Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.