3.      Розробка алгоритмів

Для виконання геометричних перетворень над графічною фігурою необхідно спочатку визначитися, як такі операції виконувати з точкою.

Відображення відносно довільної прямої:

)        Перенести все, щоб пряма проходила через початок координат;

)        Повернути все на кут, щоб пряма співпала з віссю х;

)        Виконати відображення точки відносно осі х;

)        Повернути точку на той же кут, тільки у зворотному напрямку;

)        Виконати перенос протилежний переносу у п. 1 (тобто на таку ж відстань, але у протилежному напрямку.)

Відображення відносно заданої точки:

)        Перенести все, щоб задана точка співпадала з початком координат;

)        Виконати відображення точки відносно центру координат;

)        Перенести точку у протилежному до п. 1 напрямку.

Відстань до заданої точки:

Відстань до заданої прямої:

На базі цих операцій достатньо легко виконати операції перетворення для лінії, дуги та усього об’єкту «Комбо».

Наприклад, щоб виконати зсув лінії уздовж довільної прямої необхідно це перетворення виконати для обох точок лінії.

Але для лінії та дуги додаються такі питання, як обчислення довжини і пошук центру фігури.

Пошук центру та довжини півкола:

Тепер перейдемо до побудови алгоритмів роботи зі списками об’єктів.

Тепер розглянемо алгоритм створення списку об’єктів, що відповідають деяким вимогам.

4.      Розробка програмного забезпечення

У вузлах зв'язаних списків ми будемо зберігати значення типу IceCream.

Клас «Вузол» SListNode

Кожний вузол однозв’язного списку складається з двох змінних. У першій зберігається значення. Друга представляє із себе вказівник на наступний вузол.

Найпростіший список можна реалізувати за допомогою всього лише одного класу, який буде представляти вузли:

SListNode // SListNode - назва класу, що представляє

{ // вузол однозв’язного списку:data; // змінна «Комбо» зберігає данні вузла* next; // вказівник на наступний вузол списку

};

Клас зберігає змінну типу «Морозиво» і вказівник на наступний вузол (вузол - node).

При цьому ми створюємо вказівник на перший вузол і через нього отримуємо доступ до всіх наступних вузлів.

Для реалізації однозв'язного списку, нам знадобиться три класи. Перший буде представляти вузли списку (ми вже почали його писати - SListNode), другий - сам однозв'язний список (SLinkedList) а третій - ітератор списку (SListIterator).

:SListNode(void) {d (SemiCircle(MyPoint (0,0), 0,0), SemiCircle (MyPoint(0,0), 0,0), MyLine (MyPoint(0,0), MyPoint (0,0)), MyLine (MyPoint(0,0), MyPoint (0,0)));= d;= 0;

}

Тут все просто, полю data, яке зберігає значення вузла, присвоюється екземпляр класу IceCream. А полю next, в якому зберігається вказівник на наступний вузол, присвоюється 0.

Крім конструктора, в класі Node буде одна функція. Назвемо її InsertAfter (вставити після). Її завданням буде вставка нового елемента списку після поточного:

SListNode: InsertAfter (Combo d) {* new_node = new SListNode; / / Створюємо вказівник на вузол._node-> data = d; / / Заповнюємо поле data._node-> next = next; / / Заповнюємо поле next. Цьому полю присвоюємо

/ / Значення поля next поточного елемента= new_node; / / Міняємо поле next поточного елемента. Тепер, поточний

} / / Вузол вказує на новостворений

Функція приймає один аргумент - значення, яке буде вставлено в поле data.

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

На цьому реалізація класу SListNode закінчена. Приступимо безпосередньо до створення списку.

Клас однозв'язного списку SLinkedList

SLinkedList {:* head; / / перший елемент списку* tail; / / останній елемент спискуcount;

};

У списку будуть зберігається три змінні. Два вказівники на вузли: на перший (head) і на останній (tail) і змінна цілого типу count, в якій буде зберігатися кількість елементів (вузлів) зв'язного списку.

Деструктор списку:

:~SLinkedList() {* delNode = head;* temp;(delNode!= 0) {= delNode->next;delNode;

}

Необхідність деструктора обумовлена тим, що при знищенні класу SLinkedList, також необхідно знищити і всі об'єкти класу SListNode, які є вузлами списку. Але між цими класами немає ніякого зв'язку, і автоматично вузли не знищаться. В результаті чого може виникнути витік пам'яті.

У функції нам необхідні два вказівника на вузли: який ми будемо зараз видаляти, і вказівник на наступний вузол, щоб не загубитися.

У циклі йде перевірка значення поточного елементу списку. Якщо у вказівникові міститься 0, значить список скінчився.

Якщо у списку ще є вузли, то ми зберігаємо вказівник на наступний вузол у тимчасовому вузлі temp. Потім видаляємо поточний вузол операцією delete. Тепер ми не можемо вказати на наступний вузол за допомогою поточного вузла:> next; / / цей код не працює!

Пам'ять виділену під delNode ми вже відпустили, а вказівник тепер вказує на зовсім іншу область пам'яті. Саме для цього нам і потрібна була допоміжна змінна temp. Якби її не було, ми б втратили всі наступні вузли. Тепер вказівнику delNode присвоюється next і у наступній ітерації циклу все повторюється.

Метод додавання елемента у кінець списку

SLinkedList: PushBack (Combo d) {(count == 0) {/ / У списку немає елементів.= tail = new SListNode;> data = d;

}{/ / У списку є хоча б один елемент>InsertAfter(d);= tail->next;

}++;

}

При додаванні вузла у кінець списку, можливі два варіанти: у списку зовсім немає елементів або в списку є хоча б один елемент. Ці умови ми перевіряємо за допомогою поля count, що зберігає кількість елементів списку.

Так от, якщо у списку немає елементів, то ми створюємо новий вузол, а вказівниками tail і head присвоюємо адресу цього елемента.

Якщо ж у списку є хоча б один елемент, то ми створюємо вузол після вузла tail, а потім пересуваємо tail вперед (щоб цей вказівник вказував на новий елемент).

Звичайно ж, у функції PushBack потрібно не забути збільшити змінну count, так як кількість вузлів збільшилась.

Тепер, коли у нас є функція додавання вузла у кінець списку, непогано було б навчити наш список додавати елементи у початок.

Метод додавання вузлів у початок зв'язного списку

SLinkedList: PushFront (Combo d) {(count == 0) {= tail = new SListNode;>data = d;

}{* new_node = new SListNode;_node->next = head;= new_node;

}++;

}

Також як і у функції PushBack, тут можливі два варіанти: список порожній або в списку вже є хоча б один вузол.

У разі якщо список пустий, ми робимо те ж саме, що і у функції PushBack.

Якщо ж у списку є елементи, ми створюємо новий вузол. Полю next нового вузла присвоюємо head. А потім міняємо значення head, щоб він вказував на новий вузол.

Тепер наш список вміє додавати вузли у кінець і на початок. Крім того, список коректно знищується за допомогою деструктора. Непогано було б мати можливість видаляти вузли зі списку під час виконання програми. В рамках класу SLinkedList ми можемо видалити елементи з початку і з кінця. Видалення елементів із середини, у даному класі реалізувати неможливо. Тому видалення елементів з середини списку ми розглянемо пізніше, коли будемо розглядати ітератори.

Функція видалення першого елемента списку

SLinkedList: PopFront() {(count!= 0) {* temp = head;= head->next;temp;-;(head == NULL) // у списку був один елемент

}

Видаляти елемент має сенс, якщо список не порожній. Тому ми перевіряємо змінну count.

У функції використовується тимчасова змінна, так само як у деструкторі. Тільки у даному випадку нам потрібно видалити тільки один елемент. Потім ми зменшуємо кількість елементів у змінній count.

Якщо в списку був один елемент (head == tail == «коректна адреса», а поля head-> next == tail-> next == 0), нам потрібно змінити значення покажчика tail.

Метод видалення останнього вузла списку.

Ця функція складніше попередньої. Ми не можемо просто так видалити вузол, на який вказує tail. tail потрібно пересунути на один елемент назад. Для того щоб дізнатися адресу передостаннього елемента нам потрібно «пройти» по всіх вузлах від початку списку.

SLinkedList: PopBack() {(count == 1) {tail;= tail = 0;-;

}(count > 1) {* temp = new SListNode;= head;(temp->next!= tail) temp = temp->next;temp->next;-;

}

Коли в списку один елемент, ми просто видаляємо його, а вказівниками head і tail присвоюємо 0. Звичайно ж не забуваємо і про змінну count.

Якщо ж у списку більше одного елемента, то ми створюємо тимчасову змінну, яка буде «пробігати» всі елементи. Такі змінні називаються ітераторами. У деструкторі, до речі, теж був ітератор. Але про ітератор пізніше.

Тимчасовому вузлу ми присвоюємо адресу першого елемента списку. Далі у циклі відбувається перевірка поля next тимчасового вузла з адресою останнього вузла tail. Цикл припинить виконуватися, коли тимчасовий вузол буде містити адресу передостаннього елемента.

Після циклу ми пересуваємо вказівник tail назад. А потім видаляємо останній вузол. Зверніть увагу, що робиться це за допомогою поля next передостаннього вузла. Тепер, коли останній елемент видалений, поле next передостаннього вузла вказує у «порожнечу», тому ми присвоюємо цьому полю значення 0.

Щоб ще більше розширити функціональність списків для ітераторів необхідно створити свій клас.

Клас ітераторів для однозв'язного списку.

Після того, як ми написали класи вузла і безпосередньо списку, потрібно додати клас ітераторів. Ітератори використовуються для пересування по списку. Концепція ітераторів широко поширена і використовується з багатьма структурами даних.

SListIterator {:* node;* list;

};

У класі дві змінні: вказівник на поточний вузол списку і вказівник на сам список. Покажчик на список використовується, щоб визначити, до якого списку належить даний ітератор.

Клас Iterator містить конструктор з двома аргументами.

:SListIterator (SListNode* n, SLinkedList* l) {= n;= l;

}

У конструктор передаються вказівники на вузол і список. Заповнюються відповідні поля.

Коли ітератор добігає до кінця списку, що має відбуватися? Ітератор не може повернутися у попередній елемент. Потрібно знищувати ітератор і створювати новий? Замість цього ми створимо функцію у якій ітератор повернеться у початок списку.

SListIterator: Start() {= list->head;

}

Тут все просто, полю node ми присвоюємо поле head змінної list. Тут і list, і node є членами класу Iterator.

SListIterator: Forward() {(node!= NULL)= node->next;

}

Зверніть увагу на перевірку умови. Ми можемо просунути ітератор вперед на один вузол далі вузла tail списку. Цей вузол містить значення 0.

Наступна функція повертає значення поточного вузла.

& SListIterator: Item() {node->data;

}

Метод повертає значення по посиланню.

І остання функція ітератора перевіряє його значення. Якщо у ітератор міститься 0 (список закінчився або у ньому немає елементів), то функція поверне 0. Якщо в ітераторі міститься коректне значення, то функція поверне 1.

SListIterator: Valid() {(node!= NULL);

}

Хоча, за допомогою ітераторів і можна додавати вузли до списку (метод InsertAfter класу SListNode), робиться це не дуже добре. Якщо ітератор вказує на останній вузол, і ми викликаємо функцію InsertAfter, то список зіпсується, так як в InsertAfter ніяк не обробляється перевірка tail списку. Тому для ітераторів більш правильним рішенням буде написати власну функцію. Причому краще цю функцію зробити не для ітераторів а для списків, а ітератори можна передавати у функцію у вигляді аргументів:

Insert (SListIterator& itr, IceCream d) {(itr. Valid()) {.node->InsertAfter(d);(itr.node == tail) {= itr.node->next;

}++;

}

Ми робимо перевірку, на що вказує ітератор. Якщо він вказує на 0, то нічого не відбувається. Якщо ж в ітераторі міститься коректне значення, то ми додаємо вузол за допомогою функції InsertAfter. І тепер потрібно перевірити, якщо ми додали вузол після останнього, потрібно пересунути tail.

І остання функція яку ми розглянемо: функція видалення вузла зі зв'язного списку:

SLinkedList: Remove (SListIterator& itr) {* temp = head;(itr.node == head) {. Forward();();

}{(temp->next!= itr.node) temp = temp->next;. Forward();(temp->next == tail) tail = temp;temp->next;>next = itr.node;

}-;

}

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

5.      Інструкція користувача

Для роботи з додатком необхідно запустити виконуючий файл Var_022.exe. З’явиться вікно.

Рисунок 13 - Головне вікно програми

Унизу у рядку статусу відображаються поточні координати миші. Основне поле - для малювання фігури за допомогою миші. Також у вікні є головне меню, що має наступну структуру і відбиває практично всі функціє додатка:

ü  Файл

o   Загрузить список

o   Сохранить текущий список

o   Выход

ü  Объект

o   Создать

o   Переместить

o   Повернуть относительно

§  точки

§  вершины фигуры

o   Отобразить относительно

§  Начала координат

§  Оси х

§  Произвольной прямой

§  Середины фигуры

o   Периметр

o   Расстояние от середины фигуры до…

§  Начала координат

§  Произвольной точки

§  Произвольной прямой

ü  Список

o   Создать

o   Построить список объектов

§  < заданного периметра

§  > заданного периметра

§  < расстояния от середины фигуры до начала координат

§  > расстояния от середины фигуры до начала координат

§  < расстояния от середины фигуры до произвольной точки

§  > расстояния от середины фигуры до произвольной точки

§  < расстояния от середины фигуры до произвольной прямой

§  > расстояния от середины фигуры до произвольной прямой

Розглянемо їх по черзі.

При виборі пункту меню «Файл» -> «Загрузить список» з’являється вікно. У ньому необхідно вибрати необхідний файл і натиснути кнопку «Открыть». Після чого на основному полі будуть відображені фігури списку, що був збережений у обраному файлі.

Для збереження списку після його створення на основному полі необхідно обрати пункт меню «Файл» -> «Сохранить текущий список». У вікні, що з’явилося необхідно обрати каталог, ввести ім’я файлу у полі «Имя файла» і натиснути кнопку «Сохранить».

При виборі пункту меню «Выход» робота програми завершується і вікно закривається.

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

При виборі пункту «Объект» -> «Создать» додаток переходить у режим малювання однієї фігури. Для цього необхідно мишею намалювати «верхню стіну». Після відпускання клавіші миші фігура домальовується пропорційно. Якщо перемалювати фігуру, попередня стирається. Ці етапи відображені на рисунках 14 та 15.

Рисунок 14 - Перемальовування фігури

Рисунок 15 - Фігура промальовується пропорційно лінії

Після вибору пункту меню «Объект» -> «Переместить» необхідно за допомогою миші намалювати пряму, уздовж якої необхідно виконати переміщення. Потім за допомогою клавіш керування курсором «ліворуч» і «праворуч» можна переміщати фігуру.

При виборі пункту меню «Объект» -> «Повернуть относительно…», а далі будь-який підпункт, необхідно за допомогою миші встановити точку. Після цього за допомогою таких самих клавіш керувати повертаємо фігуру за годинниковою або проти годинникової стрілки.

При виборі пункту меню «Объект» -> «Отобразить относительно…» при клацанні мишею по основному полу виконується обране перетворення. Лише при виборі підпункту «произвольной прямой» спочатку цю пряму необхідно намалювати за допомогою миші, а потім натиснути клавішу «ліворуч».

При виборі пункту меню «Объект» -> «Периметр» на основному полі відображається площа намальованої фігури у пікселах (рис. 16).

Рисунок 16 - Обчислення площі фігури

При виборі пункту меню «Объект» -> «Расстояние от середеины фигуры до…» на основному полі буде відображено відстань у пік селах. Тільки при визначенні відстані до заданої точки необхідно її намалювати за допомогою миші (рис. 17), а при визначенні відстані до заданої прямої - намалювати пряму.

Рисунок 17 - Обчислення відстані від середини фігури до заданої точки

При виборі пункту «Список» -> «Создать» додаток переходить у режим малювання списку фігур. Для цього необхідно мишею намалювати стільки фігур, скільки треба. Всі вони будуть додані у список (рис. 18).

Рисунок 18 - Створення списку об’єктів

При виборі пункту «Список» -> «Построить список объектов» а далі будь-який пункт з’явиться поле у правому верхньому куті, у якому необхідно увести задане значення чи то відстані, чи то площі. Далі виконати подвійне клацання мишею на цьому полі і натиснути клавішу «ліворуч». Результатом буде створено псисько об’єктів, умова для яких виконується, і ці фігури будуть промальовані товстою лінією (рис. 19).

Рисунок 19 - Список фігур, що мають периметр більше заданого

При необхідності перед натисканням клавіші «ліворуч» (при виборі відповідних підпунктів) треба мишею намалювати точку або пряму, до яких визначається відстань.

Перелік літератури

1.   Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений. - М.: «Вильямс», 2008

2.      Дейтел Х., Дейтел П. Как программировать на C++

.        Лафоре Р. Объектно-ориентированное программирование в С++. СПб.: Питер, 2004

.        Пахомов Б.И. C/C++ и MS Visual C++ 2008 для начинающих. - Спб.: БХВ-Петербург, 2009.

.        Прата С. Язык программирования С++. Лекции и упражнения.