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

 

Мiнiстерство освiти і науки, молоді та спорту України

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

Кафедра ЕОМ

 

 

 

 

 

 

 

 

 

 

 

 

Курсова робота 
з дисципліни «Програмування. Частина ІІІ. 
Структури даних та алгоритми»

Завдання 2:  Динамічні структури даних

 

 

 

 

 

 

 

 

 

Вибір  індивідуального  варіанту:

 

Вибір АТД: № =  (12 + 1994 + 97)%4+1= 4 – АТД «Дерево»

Вибір номера завдання: № = (7 + 1993 + 66)%10+1 = 6 – варіант завдання

 

 

 

 

 

Виконав:

 студент групи КІ-23

 Барнінець Юрій

Прийняла:

 Матвейчук Т.А

 

 

Львів – 2013

Зміст

Завдання 2: Динамічні структури даних

ЗМІСТ

1. ТЕОРЕТИЧНА ЧАСТИНА _______________________________________3

2. ЗАВДАННЯ 3.  ПОБУДОВА   АТД _______________________________ 6

2.1. Постановка задачі_________________________________________   6

2.2. Динаміка вмісту___________________________________________ 6

2.3. Результати виконання програми______________________________9

3. ЗАВДАННЯ 4.  ЗАСТОСУВАННЯ   АТД__________________________10

3.1. Постановка задачі_________________________________________10

3.2. Алгоритм розв’язання задачі________________________________10

3.2.1. Словесний  опис алгоритму_____________________________11

3.2.2. Граф-схема  алгоритму_________________________________12

3.3. Результати виконання програми_____________________________13

ВИСНОВКИ

СПИСОК  ЛІТЕРАТУРИ

ДОДАТОК А. ТЕКСТ ПРОГРАМИ ДО ЗАВДАННЯ 3

 ДОДАТОК Б. ТЕКСТ ПРОГРАМИ ДО ЗАВДАННЯ 4 

Завдання 2: Динамічні структури даних

1. ТЕОРЕТИЧНА ЧАСТИНА

 

Дерево – одна з найбільш широко поширених структур даних в інформатиці, рафіч деревоподібну структуру у вигляді набору пов’язаних вузлів. Є пов’язаною графом, що не містить цикли. Більшість джерел також додають умова на те, що ребра графа не повинні бути орієнтованими. На додаток до цих трьох обмежень, в деяких джерелах вказуються, що ребра графа не повинні бути зваженими.

 
Визначення

- Кореневий вузол – самий верхній вузол дерева.  
- Корінь – одна з вершин, за бажанням спостерігача.  
- Листовий вузол або лист – вузол самого нижнього рівня дерева.  
- Листя дерева – коріння, з яких не виходить жодної дуги.   
- Внутрішній вузол – будь-який вузол дерева, що має нащадків, і таким чином не є листовим вузлом. 
- Дерево вважається орієнтованим, якщо в корінь не заходить ні одне ребро.  
- Дерево визначення – рафічна діаграма схеми бази даних.  
- Повний зчеплений ключ – ідентифікатор запису, який утворюється шляхом конкатенації всіх ключів примірників батьківських записів (груп).  

 Вузли

Вузол є екземпляром одного з двох типів елементів графа, відповідним об’єкту деякої фіксованої природи. Вузол може містити значення, стан або подання окремої інформаційної структури або самого дерева. Кожен вузол дерева має нуль або більше вузлів-нащадків, які розташовуються нижче по дереву (за угодою, дерева ‘ростуть’ вниз, а не вгору, як це відбувається з справжніми деревами). Вузол, що має нащадка, називається вузлом-батьком щодо свого нащадка (або вузлом-попередником, або старшим). Кожен вузол має не більше одного предка. Висота вузла – це максимальна довжина спадного шляху від цього вузла до самого нижнього вузла (крайовій вузла), званому листом. Висота кореневого вузла дорівнює висоті всього дерева. Глибина вкладеності вузла дорівнює довжині шляху до кореневого вузла

 

Кореневі вузли

Самий верхній вузол дерева називається кореневим вузлом. Бути самим верхнім вузлом на увазі відсутність у кореневого вузла предків. Це вузол, на якому починається виконання більшості операцій над деревом (хоча деякі алгоритми починають виконання з «листків» і виконуються, поки не досягнуть кореня). Всі інші вузли можуть бути досягнуті шляхом переходу від кореневого вузла по ребрах (або посилання). (Згідно формального визначення, кожен подібний шлях повинен бути унікальним). У діаграмах він зазвичай зображується на самій вершині. У деяких деревах, наприклад, купах, кореневий вузол має особливі властивості. Кожен вузол дерева можна розглядати як кореневий вузол піддерева, «зростаючого» з цього вузла.

Листові вузли

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

 

Внутрішні вузли 
Внутрішній вузол – будь-який вузол дерева, що має нащадків, і таким чином не є листовим вузлом.

Піддерева

Піддерево – частина деревообразной структури даних, яка може бути представлено у вигляді окремого дерева. Будь-який вузол дерева T разом з усіма його вузлами-нащадками є піддерево дерева T. Для будь-якого вузла піддереві або має бути шлях у кореневий вузол цього піддерева, або сам вузол повинен бути кореневим. Тобто піддерево пов’язано з кореневим вузлом цілим деревом, а відносини піддерева з усіма іншими вузлами визначаються через поняття відповідне піддерево (за аналогією з терміном «відповідне підмножина»).

 

Упорядкування дерев

Існує два основних типи дерев. У рекурсивному дереві чи неврегульованих дереві має значення лише структура самого дерева без урахування порядку нащадків для кожного вузла. Дерево, в якому заданий порядок (наприклад, кожному ребру, ведучому до нащадка, надані різні натуральні числа) називається деревом з іменованими ребрами або впорядкованим деревом із структурою даних, визначеної перед ім’ям і званої структурою даних упорядкованого дерева.

Впорядковані дерева є найбільш поширеними серед деревоподібних структур. Бінарне дерево пошуку – одна з різновидів упорядкованого дерева.

Представлення дерев

Існує безліч різних способів подання дерев. Найбільш загальний спосіб представлення зображує вузли як записи, розташовані в динамічно виділюваної пам’яті з дороговказами на своїх нащадків, предків (або і тих і інших), або як елементи масиву, пов’язані між собою відносинами, певними їх позицій в масиві (наприклад, двійкова купа) .

Дерева як графи

У теорії графів дерево – пов’язаний ациклічний граф. Кореневе дерево – це граф з вершиною, виділеної в якості кореневої. У цьому випадку будь-які дві вершини, пов’язані ребром, успадковують відносини «батько-нащадок». Ациклічний граф з безліччю пов’язаних компонентів або набір кореневих дерев іноді називається лісом.

Методи обходу

Покроковий перебір елементів дерева у зв’язках між предками-вузлами і нащадками-вузлами називається обходом дерева, а сам процес називається обходом по дереву. Найчастіше, операція може бути виконана переходом покажчика по окремих вузлах. Обхід, при якому кожен вузол-предок проглядається насамперед його нащадків називається предупорядоченним обходом або обходом в прямому порядку (pre-order walk), а коли проглядаються спочатку нащадки, а потім предки, то обхід називається поступорядоченним обходом або обходом у зворотному порядку (post- order walk). Існує також симетричний обхід, при якому відвідується спочатку ліве піддерево, потім вузол, потім – праве піддерево, і обхід в ширину, при якому вузли відвідуються рівень за рівнем (N-й рівень дерева – безліч вузлів з висотою N). Кожен рівень обходиться зліва направо.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.ЗАВДАННЯ 3.  ПОБУДОВА   АТД

2.1. Постановка задачі

Побудувати  бінарне дерево пошуку для послідовності  чисел, що вводяться з клавіатури. Реалізувати операції додавання  та вилучення вузлів з бінарного  дерева пошуку. Виконати обхід дерева у заданому порядку та показати:

1. Послідовність вершин дерева при проходженні його у прямому порядку;

2. Послідовність листків дерева при проходженні його у зворотньому порядку;

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

Виконати індивідуальне завдання згідно з варіантом.

Вилучити з дерева всi вузли, що мають тільки одного безпосереднього  нащадка.

 

2.2. Динаміка вмісту дерева

 

Послідовність 10 чисел:

15, 2, 8, 17, 3, 9, 19, 1, 16, 22

Схематичне зображення БД пошуку після  обробки кожного числа з вхідної  послідовності:

Add(15);

 

Add(2);

 

 

 

Add(8);

 

 

 

 

 

 

                                           Add(17);

 

 

 

 

 

Add(3);

 

 

 

 

 

 

Add(9);

Add(19);

Add(1);

 

Add(16);

Add(22);

 

 

Реалізація  БД пошуку на базі масиву розмірністю 17:

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

 

 

індекс	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
data	15	2	17	1	8	16	19	x	x	3	9	x	x	x	22	x	x

 

Головним недоліком розглянутого способу представлення бінарного  дерева є те, що структура даних  є статичною. Розмір масиву вибирається  виходячи з максимально можливої кількості рівнів бінарного дерева. Причому ніж менш повним є дерево, тим менш раціонально використовується пам’ять.

Обхід БД пошуку:

а) послідовність вершин дерева при проходженні його у  прямому порядку:

15 – 2 – 1 – 8 – 3 – 9 –  17 – 16 – 19 – 22

 

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

1 – 3 – 9 – 16 – 22

 

в) послідовність вузлів, що мають  тільки одного нащадка при проходженні  дерева у   симетричному порядку: 
19

г) Вилучити з дерева всi вузли, що мають тільки одного безпосереднього нащадка:

 

 

 

2.3. Результати виконання програми

Результат виконання програми показано на рис. 1

Рис.1

3. ЗАВДАННЯ 4.  ЗАСТОСУВАННЯ   АТД

3.1. Постановка задачі

Задано  рядок символів S і набір  слів А[1],  …, A[k]. Написати програму розбиття рядка S на слова з набору всіма можливими способами.

 

Приклад:             Вхідні дані             Результат розбиття

S=ABBC   S = A – B – BC

A[1]=A,    S  = A – BBC

A[2]=AB,    S  = AB – BC

A[3]=BC,

A[4]=BBC,

A[5]=H,

A[6]=B

 

 

3.2. Алгоритм розв’язання задачі

3.2.1. Словесний опис алгоритму

Грубо кажучи алгоритм реалізації даної задачі зводиться  до двох етапів:

1. Реалізувати алгоритм, який би на базі БД пошуку представив всі можливі комбінації розбиття рядка S на підрядки:
1. В корені дерева зберігається рядок, який необхідно розділити на всі можливі комбінації
2. Я умовно виділив 2 правила, послідовно застосовуючи які,ми отримуємо необхідне дерево:

1 правило розподілу:

Беремо першу літеру з вузла  та розміщуємо її як лівого сина даного вузла, а правим сина робимо копію  батька. Дальше, для другого вузла  беремо дві літери і розміщуємо як лівого сина для даного вузал, а правим сином знову робимо копію батька, цей процес виконуємо доти, доки довжина лівого сина не буде менша  за батька на 1.

Проілюструю графічно цей процес:

 

 

 

 

 

 

 

 

 

Після виконання правила 1 нам необхідно виконати над листками  правило 2, які утворились після виконання правила 1

2 правило розподілу:

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

Проілюструю графічно цей процес:

 

 

 

 

 

 

 

 

 

 

Отож, правило 1 та правило 2 необхідно послідовно виконувати над даним деревом доти, доки не утворяться листки, для яких це правило не є актуальним: