Динамічні структури данних. Курсова робота з Основи програмування та алгоритмічні мови. Робота № 519444

Динамічні структури данних

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

КН

Кафедра:

Кафедра ЕОМ

Інформація про роботу

Рік:

2013

Тип роботи:

Курсова робота

Предмет:

Основи програмування та алгоритмічні мови

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Національний університет “Львівська політехніка” Кафедра ЕОМ Курсова робота ( частина 2 ) На тему: “ Динамічні структури даних ” з дисципліни: " Програмування" Вибір варіантів індивідуального завдання: Вибір АТД: № = [(16) + (1994) + (117) ] % 4 + 1 = 4 Примітка: 1 – стек, 2 – черга, 3- список, 4 – дерево. Вибір номера завдання: № = [(4) + (1994) + (83) ] % 10 + 1 = 2 ЗАВДАННЯ НА КУРСОВУ РОБОТУ Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Реалізувати операції додавання та вилучення вузлів з бінарного дерева пошуку. Виконати обхід дерева у заданому порядку та показати: послідовність вершин дерева при проходженні його у прямому порядку; послідовність листків дерева при проходженні його у зворотньому порядку; послідовність вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку. Вилучити з дерева всi листки. 2) Глосарій або предметний покажчик підручника складається з впорядкованих по алфавіту основних термінів, кожен з яких супроводжується впорядкованою за зростанням послідовністю номерів сторінок, де він зустрічається, і множиною підтермінів. Підтерміни виводяться на наступних за основним терміном рядках, вони дещо зсунуті вправо відносно основного терміна і впорядковані по алфавіту всередині основного терміна. Кожен підтермін супроводжується впорядкованою за зростанням послідовністю номерів сторінок, де він зустрічається. Розробити структуру даних для представлення такого предметного покажчика і написати програму для зображення предметного покажчика по вхідних даних, що зберігаються у текстовому файлі. Кожний вхідний рядок починається або з символу М (основний термін), або з символу S (підтермін). Рядок з символом М містить основний термін, за котрим слідують номери сторінок, на котрих зустрічається основний термін. Рядок з символом S будується аналогічно, за винятком того, що він містить не основний термін, а підтермін. Вхідні рядки з’являються у будь-якому порядку. Єдина умова: кожен підтермін вважається підтерміном найближчого попереднього основного терміна. Для одного основного терміна або підтерміна може бути декілька вхідних рядків (всі номери сторінок, що з’являються для конкретного терміна у будь-якому рядку, повинні бути надруковані разом з цим терміном). Зміст 1. Теоретична частина 4 2.Завдання 3. Побудова АТД 6 2.1. Постановка задачі 6 2.2. Динаміка вмісту 7 2.3. Результати виконання програми 10 3. Завдання 4. Застосування АТД 11 3.1. Постановка задачі 11 3.2. Алгоритм розв’язання задачі 12 3.2.1. Словесний опис алгоритму 12 3.2.2. Граф-схема алгоритму 12 3.3. Результати виконання програми 15 Висновки 16 Список літератури 17 Додаток А. Текст програми до завдання 3 18 Додаток Б. Текст програми до завдання 4 22 1. Теоретична частина Переваги динамічних структур даних Динамічні структури даних, щодо визначення, характеризуються відсутністю фізичної суміжності елементів структури пам'яті, непостійністю і непередбачуваністю розміру структури в процесі її обробки. Оскільки елементи динамічної структури розташовуються по непередбачуваним адресами пам'яті, адреса елемента такої структури не може бути обчислений з адреси початкового або попереднього елемента. Для встановлення зв'язку між елементами динамічної структури використовуються покажчики, через які встановлюються явні зв'язки між елементами. Таке подання даних у пам'яті називається зв'язковим. Елемент динамічної структури складається з двох полів: інформаційного поля або поля даних, в якому містяться ті дані, заради яких і створюється структура; в загальному випадку інформаційне поле саме є інтегрованою структурою-вектором, масивом, записом і т.п.; полі зв'язок, в якому містяться один або кілька покажчиків, що зв'язує цей елемент з іншими елементами структури. Коли зв'язне подання даних використовується для розв'язання прикладної задачі, для кінцевого користувача дивись робиться тільки вміст інформаційного поля, а поле зв'язок використовується тільки програмістом-розробником. Переваги зв'язкового представлення даних: у можливості забезпечення значної мінливості структур; розмір структури обмежується тільки розміром пам'яті машини; при зміні логічної послідовності елементів структури потрібно не переміщення даних в пам'яті, а тільки корекція покажчиків. Однак існують і недоліки: робота з покажчиками вимагає, як правило, більш високої кваліфікації від програміста; на поля зв'язок витрачається додаткова пам'ять; доступ до елементів зв'язного структури може бути менш ефективним за часом. Застосування динамічних структур Останній недолік є найбільш серйозним і саме їм обмежується застосовність зв'язкового представлення даних. Якщо в суміжному поданні даних для обчислення адреси будь-якого елемента нам у всіх випадках достатньо було номера елемента або інформації, що міститься в дескрипторі структури, то для зв'язкового подання адресу елемента не може бути обчислений з вихідних даних. Дескриптор зв'язного структури містить один або кілька покажчиків, що дозволяють увійти в структуру, далі пошук і необхідного елемента виконується проходженням по ланцюжку покажчиків від елемента до елементу. Тому зв'язне уявлення практично ніколи не застосовується в задачах, де логічна структура даних має вигляд вектора або масиву - з доступом за номером елемента, але часто застосовується в задачах, де логічна структура вимагає іншої вихідної інформації доступу (таблиці, стеки, списки, дерева і т . д.). Дерево - в інформатиці та програмуванні одна з найпоширеніших структур даних. Формально дерево визначається як скінченна множина Т з одного або більше вузлів (nodes), яка задовольняє наступним вимогам: існує один відокремлений вузол - корень (root) дерева інші вузли (за виключенням кореня) розподілені серед m ≥ 0 непересічних множин T1, ..., Tm і кожна з цих множин в свою чергу є деревом. Дерева T1, ..., Tm мають назву піддерев (subtrees) даного кореня. З цього визначення випливає, що кожний вузлів є в свою чергу коренем деякого піддерева. Кількість піддерев вузла має назву степеня (degree) цього вузла. Вузол степеню нуль називається кінцевим (terminal) або листком (leaf). Не корінь і некінцевий вузол також має назву вершини розгалуження (branch node). Нехай x - довільний вузол дерева з коренем r. Тоді існує єдиний шлях з r до x. Усі вузли на цьому шляху називаються предками (ancestors) x; якщо деякий вузол y є предком x, то x називається нащадком (descendant) y. 2. Завдання 3. Побудова АТД 2.1. Постановка задачі Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Реалізувати операції додавання та вилучення вузлів з бінарного дерева пошуку. Виконати обхід дерева у заданому порядку та показати: послідовність вершин дерева при проходженні його у прямому порядку; послідовність листків дерева при проходженні його у зворотньому порядку; послідовність вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку. Вилучити з дерева всi листки. 2.2. Динаміка вмісту 2.2.1. Задаємо вхідну послідовність 10 цілих чисел: 24, 20, 16, 30, 36, -20, 14, 28, -30, 22. 2.2.2. Схематичне зображення дерева: 24 Add(24); Add(20); Add(16); Add(30); Add(36); Delete(20); Add(14); Add(28); Delete(30); Add(22); Реалізація БД пошуку на базі масиву розмірністю 17: Індекси 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 info 24 20 16 30 36 14 28 22 x x x x x x x x father 0 16 1 2 1 3 5 3 0 9 10 11 12 13 14 15 left-son 3 0 6 0 7 0 0 0 0 0 0 0 0 0 0 0 right-son 5 4 8 0 0 0 0 0 10 11 12 13 14 15 16 2 Head = 1; Free = 9; 3.4. Обхід БД пошуку: а) послідовність вершин дерева при проходженні його у прямому порядку: 24 16 14 22 36 28 б) послідовність листків дерева при проходженні його у зворотньому порядку: 14 22 28 в) послідовність вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку: 36 3.5 Вилучити з дерева всi листки. Зображення дерева після виконання операції вилучення всіх листків: 3.3. Результати виконання програми / 3. Завдання 4. Застосування АТД 3.1 Постановка задачі Глосарій або предметний покажчик підручника складається з впорядкованих по алфавіту основних термінів, кожен з яких супроводжується впорядкованою за зростанням послідовністю номерів сторінок, де він зустрічається, і множиною підтермінів. Підтерміни виводяться на наступних за основним терміном рядках, вони дещо зсунуті вправо відносно основного терміна і впорядковані по алфавіту всередині основного терміна. Кожен підтермін супроводжується впорядкованою за зростанням послідовністю номерів сторінок, де він зустрічається. Розробити структуру даних для представлення такого предметного покажчика і написати програму для зображення предметного покажчика по вхідних даних, що зберігаються у текстовому файлі. Кожний вхідний рядок починається або з символу М (основний термін), або з символу S (підтермін). Рядок з символом М містить основний термін, за котрим слідують номери сторінок, на котрих зустрічається основний термін. Рядок з символом S будується аналогічно, за винятком того, що він містить не основний термін, а підтермін. Вхідні рядки з’являються у будь-якому порядку. Єдина умова: кожен підтермін вважається підтерміном найближчого попереднього основного терміна. Для одного основного терміна або підтерміна може бути декілька вхідних рядків (всі номери сторінок, що з’являються для конкретного терміна у будь-якому рядку, повинні бути надруковані разом з цим терміном). 3.2. Алгоритм розв’язання задачі 3.2.1. Словесний опис алгоритму Створюю клас Glossary, основою якого є об’єкт класу Tree. Рівень 1, тобто підвітки кореня дерева, це терміни. Рівень 2 це підтерміни або сторінки де зустрічаються терміни. Рівень 3 це сторінки на яких зустрічаються підтерміни. В класі реалізовано методи для пошуку в глосарії за терміном, а також за терміном і підтерміном. Реалізовано додавання нових термінів. Також, можна додавати підтерміни до існуючих термінів. Реалізовано вилучення елементів з глосарію 3.2.2. Граф-схема алгоритму 3.3. Результати виконання програми / Вміст вихідного текстового файла: / Глосарій після додавання елементів з текстового файла: / Вміст вихідного текстового файла: / Висновки Створено програму, яка моделює глосарій книги за допомгою АТД «Дерево». Реалізовано всі необхідні методи та методи, які задані завданням. Список літератури Грегори К. Использование Visual С++. Специальное издание. - М.: «Диалектика», 1999. Мешков А.В., Тихомиров Ю.В. Visual С++ и MFC. Пер. с англ. – 2-е изд. перераб. и доп. – СПб.: БХВ - Петербург, 2002. – 1040 с. Страуструп Б. Язык программирования С++. Третье издание. - М.: «Издательство Бином», 1999. Трамбле Ж., Соренсон П. Введение в структуры данных. – М.:Машиностроение, 1982 Уильям Топп, Уильям Форд. Структуры данных в С++. – М.:Бином, 2000 - 700

Курсова робота Основи програмування та алгоритмічні мови

roman2013

05.02.2013 00:26

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись