Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Динамічні структури данних
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
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
05.02.2013 00:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора