Курсова робота на тему: «ДЕРЕВОПОДІБНІ ЕЛЕМЕНТИ В АЛГОРИТМІЧНИХ СТРУКТУРАХ»

Зміст

Розділ 1.    Основні поняття та алгоритмізація дерев    4

1.1.Графічне зображення деревовидних структур    7

1.2.Значення і структура списку    12

1.4.Використання методів обходу дерев    18

1.5.Складання алгоритму диференціювання    21

1.6.Інші представлення дерев    25

1.7.Відношення еквівалентності    29

Розділ 2.    Практична реалізація деревоподібних елементів в алгоритмічних структурах    38

Висновки    47

Список літератури    48

Вступ

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

Формально дерево (tree) визначається як кінцева множина Т одного або більш вузлів з наступними властивостями:

  1. існує один виділений вузол, а саме — коріння (root) даного дерева Т;
  2. решта вузлів (за винятком коріння) розподілена серед т ≥ 0 не пересічних множин Т1,…,Тm і кожна з цих множин, у свою чергу, є деревом: дерева Т,…,1Tт називаються піддеревами (sub trees) даного коріння. Крім того, нище буде описано, як правильно графічно зображати дерева, їх підпорядковані елементи, і як це буде відображатися при подальшому розв’язанні. Стандартна термінологія деревовидних структур походить від генеалогічних дерев другого типу, а саме від родової схеми.

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

  3. Основні поняття та алгоритмізація дерев

    Дерева — найбільш важливі нелінійні структури, які зустрічаються при роботі з комп’ютерними алгоритмами. Взагалі кажучи, деревовидна структура задає для вузлів відношення “розгалуження”, яке багато в чому нагадує будову звичайного дерева.

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

    З цього визначення виходить, що кожен вузол дерева є корінням деякого піддерева даного дерева. Кількість піддерев вузла називається степенем (degree) цього вузла. Вузол із степенем нуль називається кінцевим вузлом (terminal node) або листом (leaf). Не кінцевий вузол називається вузлом розгалуження (branch node). Рівень (level) вузла по відношенню до дерева Т визначається рекурсивно таким чином. Рівень коріння дерева Г рівний нулю, а рівень будь-якого іншого вузла на одиницю вищий, ніж рівень коріння найближчого піддерева дерева Г, що містить даний вузол.

    Ці поняття ілюструються на мал. 1.1 на прикладі дерева з сімома вузлами. Вузол А є корінням, яке має два піддерева: {В} і{C,D,E,F,G}. Корінням дерева {C,D,E,F.G} є вузол С. Рівень вузла 3 рівний 1 по відношенню до всього дерева. Він має три піддерева, {D}, {Е} і {F,
    G}, тому З мас степінь 3. Кінцевими на мал. 1.1 є вузли В, D, Е і G. Вузол F єдиний вузол із степенем 1. а вузол G — єдиний вузол із степенем 3. Якщо має значення відносний порядок піддерев Т,…,Тmте дерево є впорядкованим (ordered tree). Якщо у впорядкованому дереві m ≥ 2, то має
    сенс назвати піддерево 72 другим піддеревом даного коріння і т.д. Впорядковані дерева іноді також називаються плоскими деревами (plane trees), оскільки при їх впорядкуванні має значення

    (мал. 1.1) (мал.1. 2)

    Мал. 16.

    Мал. 16.

    спосіб розміщення дерева на площині. Якщо не вважати різними два дерева, які відрізняються тільки відносним порядком піддерев

    вузлів, то дерево називається орієнтованим (oriented), оскільки при цьому має значення тільки відносна орієнтація вузлів, а не їх порядок. Сама природа представлення даних в комп’ютері визначає неявний порядок будь-якого дерева, тому в більшості випадків впорядковані дерева представляють найбільший інтерес. Далі неявно припускатимемо, що всі дані дерева є впорядкованими, якщо явно не вказане зворотне. Відповідно дерева на мал. 1.1 і 1.2 в загальному випадку розглядаються як різні, хоча як орієнтовані дерева вони абсолютно однакові.

    Мал. 16.

    Ліс (forest) це множина (звичайно впорядкована), що не містить жодного непересічного дерева або містить декілька непересічних дерев. Тоді ще одне формулювання п. (b) в даному вище визначенні дерева могло б виглядати так: вузли дерева за умови виключення коріння утворюють ліс. Між абстрактними поняттями лісу і дерев існує не дуже помітна різниця. При вилученні коріння дерева отримаємо ліс, і навпаки: при додаванні одного вузла в ліс, всі дерева якого розглядаються як піддерева нового вузла, одержимо дерево. Тому поняття “ліс” і “дерево” часто використовуються як рівнозначні при роботі із структурами даних.

    ЗАВАНТАЖИТИ

    Для скачування файлів необхідно або Зареєструватись

    Derevopodibni El V Alg Struk (650.5 KiB, Завантажень: 2)

Сторінка: 1 2 3 4 5 6 7 8 9 10
завантаження...
WordPress: 23.26MB | MySQL:26 | 0,351sec