Курсова робота Динамічні структури даних груд
Міністерство освіти та науки РФ
Федеральне агентство з освіти
Державний освітній заклад вищої професійної освіти
"Омський державний технічний університет"
Кафедра прикладної математики та інформаційних систем
Курсова робота з дисципліни: «Високорівневі методи»
Динамічні структури даних: грудень
Додаток 1. Текст програми
Додаток 2. Форма
Об'єктно-орієнтоване програмування – це природне продовження структурного програмування. Об'єктно-орієнтоване програмування потребує складних програмних процесів, але робить створення програми досить легким. В результаті створюються досконалі коди, які легко поширювати та просто підтримувати. Одного разу створений для програми об'єкт можна використовувати в інших програмах. Повторне використання об'єктів набагато скорочує час розробки та збільшує продуктивність праці. Об'єктно-орієнтоване програмування ґрунтується на використанні класів. Використання класів – це основна відмінність мови С++ від мови С, на якій вона заснована.
Клас поряд із поняттям «Об'єкт» є важливим поняттям об'єктно-орієнтованого підходу в програмуванні. Під класом мається на увазі якась сутність, яка задає деяку загальну поведінку для об'єктів. Таким чином, будь-який об'єкт може належати або не належати певному класу, тобто володіти або не володіти поведінкою, яку цей клас має на увазі. Клас визначає для об'єкта правила, з яких з об'єктом можуть працювати інші об'єкти, зазвичай це робиться за допомогою визначення методів класу.
Крім того, класи можутьзнаходитися один з одним у різних відносинах, таких як успадкування чи агрегація.
Клас - це збори зв'язкової інформації, яка включає і дані, і функції. Клас – це розвиток структур: у яких теж поєднується дані різних типів. Це такий самий шаблон, під який, як і під структуру, пам'ять виділяється лише тоді, коли ми створюємо змінну типу цього шаблону.
Клас визначається як список своїх членів. До членів класу належать його поля (властивості) та функції (методи).
Кожному члену класу можна встановити його область доступу (access control level). Область доступу члена класу визначає ділянки коду, з яких до цього члена можна буде звертатися. У більшості об'єктно-орієнтованих мов програмування підтримуються такі області доступу:
- private (закритий, внутрішній член класу) - звернення до члена допускаються лише з коду методів класу, у якому цей член визначено. Будь-які спадкоємці класу вже не зможуть отримати доступ до цього члена;
- protected (захищений, внутрішній член ієрархії класів) - звернення до члена допускаються з коду методів класу, в якому цей член визначено, або з будь-яких класів-спадкоємців;
- public (відкритий член класу) – звернення до члена допускаються з будь-якого коду.
У кожному класі визначено характеристики об'єктів, які використовує даний клас. У класі також задаються програми, які називають методами, які обробляють характеристики об'єктів, що належать даному класу. Поведінка об'єкта у світі визначається його характеристиками. Змінюючи значення показників, ми отримаємо різну поведінку об'єктів. Коли ми створюємо екземпляр класу та визначаємо значення його конкретних характеристик, ми отримуємо конкретнийоб'єкт. У складі класу існує спеціальний метод, який формує екземпляр класу. Цей метод називається конструктора. На противагу конструктору існує програма-деструктор, яка знищує екземпляр класу в пам'яті.
Створити клас "Дек".
1. Додавання елемента початку дека.
2. Видалення елемента початку дека.
3. Додавання елемента до кінця дека.
4. Видалення елемента кінця дека.
5. Перевірка дека на наявність у ньому елементів.
Динамічні структури даних: грудень
У мовах програмування існує спосіб виділення пам'яті під дані, який називається динамічним. І тут пам'ять під величини відводиться під час виконання програми. Такі величини називають динамічними. Розділ оперативної пам'яті, що розподіляється статично, називається статичною пам'яттю; Розділ пам'яті, що динамічно розподіляється, називається динамічною пам'яттю (динамічно розподіляється пам'яттю).
Використання динамічних величин надає програмісту низку додаткових можливостей. По-перше, підключення динамічної пам'яті дозволяє збільшити обсяг даних, що оброблюються. По-друге, якщо потреба в якихось даних відпала до закінчення програми, то зайняту ними пам'ять можна звільнити для іншої інформації. По-третє, використання динамічної пам'яті дозволяє створювати структури даних змінного розміру.
p align="justify"> Робота з динамічними величинами пов'язана з використанням ще одного типу даних - посилального типу. Величини, що мають тип посилання, називаються покажчиками.
Структуровані типи даних, такі, як масиви, множини, записи, є статичні структури, оскільки їх розміри незмінні протягом усього часу виконання програми.
Частопотрібно, щоб структури даних змінювали свої розміри під час вирішення задачі. До таких структур відносяться списки (односпрямовані, двоспрямовані, кільцеві односпрямовані та кільцеві двоспрямовані), стеки, деки, черги, дерева та інші. Опис динамічних структур за допомогою масивів, записів та файлів призводить до неекономного використання пам'яті ЕОМ та збільшує час вирішення завдань.
Адреса величини - це номер першого байта поля пам'яті, в якому знаходиться величина. Розмір поля однозначно визначається типом.
Динамічна структура називається деком (англ. deque - абревіатура від double-ended queue, двостороння черга) або двонаправленим списком, якщо кожен вузол її містить два покажчики: один вказує на попередній вузол, інший - на наступний. Такі списки можуть бути лінійними та циклічними, а члени в них додаються та видаляються з 2 сторін.
 |
Ми розрізнятимемо деки з обмеженим виходом або обмеженим входом; у таких деках відповідно виняток чи включення допускається лише одному кінці.
Мал. 2. Гру з обмеженим входом
Мал. 3. Гру з обмеженим виходом
Дек з обмеженим входом може бути використаний як проста черга або як стек.
У деці всі винятки та додавання відбуваються на обох його кінцях.
Дек досить легко можна організувати як двозв'язаного ациклічного списку. При цьому перший та останній елементи списку відповідають входам (виходам) дека.
Створюваний клас у цій програмі називається Deq.
Цей клас повинен реалізовувати функції вставки та видалення елементів на початок і в кінці дека.
Для створення класу"Дек" необхідно спочатку створити структуру елемента з вказівником на наступний елемент. У цій програмі такою структурою є Node.
Під час створення класу треба створити покажчики перший і останній елементи дека. Дані покажчики прописуються в private, тобто звертатися до цих покажчиків можна лише з методів класу Deq.
У загальнодоступній області доступу прописуються методи класу, прописані у постановці завдання.
Покажчикам спочатку надаються порожні значення (NULL).
Додавання елемента на початок грудня
Для додавання елемента початку дека використовується метод класуadd. Його параметрами є елемент, що додаєтьсяb.
Необхідно створити новий елемент структури Node(el). Елементу el надається значення введеного з клавіатури числа. Для додавання елемента на початок дека, необхідно, щоб комірка була порожня. Тому, перевіряється умова наявності в осередку елемента. Якщо комірка не порожня, то покажчик на перший елемент переходить на наступну комірку, в яку буде записаний елемент. Кількість осередків збільшується на 1.
Видалення елемента з початку грудня
Для видалення елемента початку дека використовується метод класуdelete.
Видалення елемента відбувається за тим самим алгоритмом, але осередок не перевіряється на наявність елемента в ньому. Елементу el надається покажчик first і покажчик перетворюється на наступну комірку. Потім елемент el видаляється і кількість осередків знижується на одиницю.
Додавання елемента в кінець грудня
Для додавання елемента до початку дека використовується метод класу add_end. Його параметрами є елемент, що додаєтьсяb.
Необхідно створити новий елемент структури Node(el). Елементу el надається значення введеного зклавіатури числа. Для додавання елемента в кінець дека необхідно, щоб комірка була порожня. Покажчик на останній елемент переходить на наступну комірку, в яку і буде записаний елемент. Далі покажчику на останній елемент переходить на наступну комірку, якій надається значення NULL. Кількість осередків збільшується на 1.
Видалення елемента з кінця грудня
Для видалення елемента початку дека використовується метод класу delete_end.
Для видалення елемента кінця дека треба створити новий елемент структури Node (el). Елементу el надається покажчик на перший елемент. Поки el не прийме значення NULL, елемент прийматиме значення наступного елемента. Потім el видаляється і посилання на останній елемент присвоюється значення el. Кількість осередків зменшується.
Перевірка дека на наявність у ньому елемента
Для перевірки дека використовується метод класуprov.Цей метод має тип Boolean.
Для перевірки на наявність елементів у деці створюється новий елемент структури Node і йому присвоюється покажчик на перший елемент дека. Якщо комірка не порожня, то повертається значення true, інакше false.
Функція виведення дека в StringGrid
Ця функція потрібна для відображення вставки та видалення елементів у таблицю StringGrid. Функція збільшує кількість осередків таблиці, якщо виявляє, що осередок не порожній.