Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
фундаментальні структури
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних технологій, автоматики та метрології
Факультет:
КН
Кафедра:
Кафедра електронні обчислювальні машини
Інформація про роботу
Рік:
2011
Тип роботи:
Курсова робота
Предмет:
Алгоритми та методи обчислень
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "Львівська політехніка"
Інститут комп’ютерних технологій, автоматики та метрології
Кафедра "Електронні обчислювальні машини"
ЗВІТ
до курсової роботи на тему:
«ПРОГРАМУВАННЯ»
з курсу «ПРОГРАМУВАННЯ»
Завдання на курсову роботу
Побудувати базову структуру даних і набір операцій для роботи з нею. Застосувати їх для
розв’язання однієї з наступних задач згідно з варіантом. Під час виконання програми
обов’язково відображати на екрані монітора всі зміни, що будуть відбуватись у вибраній
структурі даних.
Завдання 1:
Написати програму синтаксичного аналізу відповідностей відкриваючих і закриваючих дужок в арифметичному виразі, що має три набори дужок "(" i ")", "<" i ">", "[" i "]". Роздрукувати таблицю відповідностей дужок, причому в таблиці повинно бути зазначено, для яких дужок відсутні парні їм дужки. Для ідентифікації дужок використати їх порядкові номери у виразі.
Завдання 2:
Дано послідовність натуральних чисел ( значення кожного числа від 1 до 1000 ).
Послідовність може бути не відсортована. Треба знайти варіант найбільшої (по кількості
елементів) неспадаючої послідовності, складеної з чисел цього ряду. Порядок включення чисел у неспадаючу послідовність повинен відповідати порядку слідування чисел у початковій послідовності.
Анотація
В курсовій роботі розглядаються фундаментальні структури, які складаються з простих даних. Курсова робота складається з двох завдань:
1-е завдання-використання таких структур даних як:стек, дек, черга, списки.
2-е завдання-використання складніших структур даних таких як:дерева, графи.
Зміст
Вступ ……………………………………………………………………………………………….5
1.Завдання 1:
1.1.Теоретична частина ……………………………………………………………………….10
1.2.Опис алгоритму ……………………………………………………………………………12
1.3.Система тестів ……………………………………………………………………………..13
1.4.Специфікація програми …………………………………………………………………...14
1.5.Результати виконання програми …………………………………………………………15
2.Завдання 2:
2.1.Теоретична частина ……………………………………………………………………….16
2.2.Опис алгоритму ……………………………………………………………………………22
2.3.Система тестів ……………………………………………………………………………..23
2.4.Специфікація програми …………………………………………………………………...24
2.5.Результати виконання програми …………………………………………………………25
Висновки …………………………………………………………………………………………26
Список літератури ……………………………………………………………………………….27
Додатки …………………………………………………………………………………………...28
Вступ
В програмуванні та комп'ютерних науках структу́ри да́них — це способи організації даних в комп'ютерах. Часто разом зі структурою даних пов'язується і специфічний перелік операцій, що можуть бути виконаними над даними, організованими в таку структуру.
Правильний підбір структур даних є надзвичайно важливим для ефективного функціонування відповідних алгоритмів їх обробки. Добре побудовані структури даних дозволяють оптимізувати використання машинного часу та пам'яті комп'ютера для виконання найбільш критичних операцій.
Відома формула «Програма = Алгоритми + Структури даних» дуже точно виражає необхідність відповідального ставлення до такого підбору. Тому іноді навіть не обраний алгоритм для обробки масиву даних визначає вибір тої чи іншої структури даних для їх збереження, а навпаки.
Підтримка базових структури даних, які використовуються в програмуванні, включена в комплекти стандартних бібліотек найбільш розповсюджених мов програмування, таких як Standart Template Library для C++, Java API, Microsoft.NET, тощо.
Щоб ефективно працювати з даними треба знати їх структуру. Наприклад, ви бачите рядок цифр, 26 12 11/26. Він вам нічого не говорить, поки ви не дізнаєтесь, що перші три цифри означають "вжити до", а остання - номер партії. Та й перші три розібрати важко, якщо не здогадатись що 11 - це 2011 рік, 26 - напевне число, а 12 - місяць грудень. Тобто структура даних - це щось що дозволяє правильно інтерпретувати їх.
Списком називається впорядкована послідовність елементів a1, a2, ...,an. Розмір або довжина цього списку дорівнює n. Список розміру 0 називається порожнім. Список можна реалізувати або за допомогою массиву або за допомогою зв’язування його елементів вказівниками (зв’язаний список). У зв’язаному списку елементи лінійно впорядковані, їх порядок визначається вказівниками, що входять у склад елементів списка. Елемент двостороннього зв’язаного списка містить три поля: ключ та два вказівника – наступний та попередній. В односторонньому зв’язаному списку відсутнє поле ‘попередній’. У впорядкованому списку елементи розташовані в порядку зростання ключів на відміну від невпорядкованого списка.
Орієнтованим графом називається структура G = (V, E), де V – скінченна множина вершин, E – множина ребер, що задається як бінарне відношення на V, тобто E ??V ??V. Орієнтований граф називається орграфом. Граф може містити ребра - цикли, які сполучають вершину саму з собою. Про ребро (u, v) говорять, що воно виходить із вершини u та входить у вершину v.
В неорієнтованому графі множина ребер E складається із невпорядкованих пар вершин. Про ребро (u, v) неорієнтованого графу говорять, що воно інцидентно вершинам u та v. Якщо в графі G є ребро (u, v), то говорять, що вершина u суміжна з вершиною v. Для неорієнтованого графу відношення суміжності є симетричним. Степенем вершини в неорієнтованому графі називається кількість інцидентних їй ребер. Для орієнтовних графів розрізняють вхідну та вихідну вершини; сума вхідних та вихідних степеней називається степенем вершини.
Деревом називається зв’язаний граф без циклів. Дерево являє собою скінченну множину елементів Т, які називаються вершинами. Якщо множина вершин Т порожня, то дерево називається порожнім; інакше в дереві повинна бути виділена одна вершина, яка називається коренем (якщо виділеної вершини не існує, то така структура називається деревом без виділеного кореня). Якщо (y, x) є останнім ребром на шляху з кореня до х, то y називається батьком, а x – сином. Корінь є єдиною вершиною, яка не має батька. Вершини, які мають одного спільного батька, називаються братами. Якщо кожна вершина T (батько) сполучається не більше ніж з k іншими вершинами T1, T2, ..., Tk (синами), то таке дерево називається k - арним. Якщо вершина не має синів, то вона називається листом; інакше вершина називається внутрішньою. Кількість синів у вершини дерева називається її степенем. Глибиною вершини називається довжина шляху від кореня до цієї вершини. Висотою дерева називається найбільша довжина від кореня до листа. Повним k - арним деревом називається k - арне дерево, в якому усі листи мають однакову глибину та усі внутрішні вершини мають однаковий степінь.
Властивість дерев. Нехай G = (V, E) – неорієнтований граф. Тоді наступні твердження еквівалентні:
G є деревом без виділеного кореня;
для довільних двох вершин G існує єдиний простий шлях, що їх сполучає;
граф G є зв’язним, але не залишається таким при вилученні хоча б одного ребра;
граф G є зв’язним і |E| = |V| - 1;
граф G є ациклічним і |E| = |V| - 1;
граф G є ациклічним, але додання довільного ребра породжує цикл.
У двійковому дереві кожна вершина може мати не більше двох синів (лівий та правий сини). Кожна вершина окрім кореня, має батька. Припредставленні двійкового дерева за допомогою вказівників кожна вершина містить ключ Val, вказівники на лівого Left та правого Right синів, а також на батька Up. Якщо сина або батька (для кореня) не існує, то відповідний вказівник містить NIL. Ключі у двійковому дереві містяться у відповідності до властивості впорядкованості:
Нехай x – довільна вершина двійкового дерева. Якщо вершина y знаходиться в лівому піддереві вершини x, то x.Val > y.Val. Якщо вершина y знаходиться в правому піддереві вершини x, то x.Val < y.Val.
Об’єкт дерево має наступні методи:
INSERT – вставка елемента до дерева;
DELETE – вилучення елемента з дерева;
FIND – пошук елемента в дереві;
FindMin – пошук вузла дерева з мінімальним елементом;
FindMax – пошук вузла дерева з максимальним елементом;
PrintLR – обхід дерева зліва направо.
Властивість впорядкованості дозволяє надрукувати всі ключі у неспадному порядку за допомогою обходу дерева зліва направо, який відбувається наступним чином:
побувати в лівому піддереві
побувати в корені
побувати в правому піддереві
Мінімальний (максимальний) ключ в дереві можна знайти, якщо пройти по вказівникам Left (Right) від кореня поки не досягнемо вершини, лівий (правий) син якої дорівнює NIL. Процедура FindMin (FindMax) повертає вказівник на вершину, яка містить мінімальний (максимальний) ключ. Час виконання вказаних процедур дорівнює O(h), де h – висота дерева.
У процедурі вставки Insert елемента Value в бінарне дерево Tree відбувається рух вниз по дереву від корня до листа. В кожній вершині x, яка не є листом, процедура обирає напрямок руху (вліво чи вправо) у відповідності до властивості впорядкованості: якщо Value < x.Val, то відбувається рух вліво, інакше – вправо. Дійшовши до листа z, процедура
вставляє нову вершину w, ключ якої дорівнює Value знову ж таки за властивістю впорядкованості: якщо Value < z.Val, то z.Left := w, інакше z.Right := w. Час виконання процедури дорівнює O(h), де h – висота дерева.
Дерева з довільним розгалудженням можна перетворити у двійкове дерево за принципом “ліва дитина – правий сусід”. Кожна вершина містить три вказівники:
вказівник p на батька;
вказівник left-child[x] на саму ліву дитину вершини х;
вказівник right-child[x] на найближчого сусіда вершини х;
Вершина х не має дітей тоді і тільки тоді коли left-child[x] = NIL.
Вершина х є крайньою правою дитиною свого батька якщо right-child[x] = NIL.
AVL - деревом (Adelson-Velskii and Landis) називається бінарне дерево, яке має наступні властивості:
висоти піддерев кожного батька відрізняються не більше ніж на 1:
кожне піддерево батька є AVL - деревом.
AVL - дерева належать до класу збалансованих бінарних дерев.
Ліве дерево є AVL - деревом, оскільки у нього висота кожного лівого сина на 1 більша за висоту відповідного правого сина. Дерево, яке зображене справа, не є AVL - деревом, оскільки лівий син вершини 12 (дерево з коренем 8) має висоту 4, а правий син вершини 12 (дерево з коренем 18) має висоту 2.
Дерево відрізків – це структура даних, яка створена для роботи з такими інтервалами на числовій осі, кінці яких належать фіксованій множині з N абсцис (далі цими абсцисами будемо вважати цілі числа в інтервалі [1, N]). Оскільки множина абсцис фіксована, то дерево відрізків являє собою статичну структуру по відношенню до цих абсцис.
Дерево відрізків – це двійкове дерево з коренем. Для заданих цілих чисел l та r (l < r) дерево відрізків T(l, r) будується рекурсивно наступним чином: воно складається з кореня v з параметрами B[v] = l, E[v] = r (B – Begin, E - End). Якщо r - l > 1, то воно складається з лівого піддерева T(l, [(B[v] + E[v])/2]) та правого піддерева T([(B[v] + E[v])/2], r).
Інтервали, що належать множині {[B[v], E[v]]: v - вузел T(l, r)}, називаються стандартними інтервалами дерева T(l, r). Стандартні інтервали, які належать листам T(l, r), називаються елементарними інтервалами. T(l, r) збалансоване та має глибину ?log2(r - l)?.
Дерево відрізків призначено для динамічного запам’ятання інтервалів, кінці яких належать множині {l, l + 1, ..., r}. Якщо r - l > 3, то інтервал [b, e] з цілими b < e буде розбито в набір не більш ніж ?log2 (r - l)? + ?log2 (r - l)? - 2 стандартних інтервалів дерева T(l, r).
Функція BuildTree ( l, r ) будує та повертає дерево відрізків T(l, r). Складний тип даних tree має структуру дерева, в якій left та right – вказівники на лівого та правого сина, begin та end – параметри вершини. Фрагментація інтервала [b, e] повністю визначається операцією занесення [b, e] в дерево відрізків Т. До структури даних tree додамо булевий параметр flag, який буде відповідати за включення стандартного інтервалу до інтервалу [b, e]. Тобто якщо для деякої вершини v має місце flag[v] = TRUE, то [ begin[v], end[v] ] ? [b, e].
Лінійний список в інформатиці та програмуванні визначається як екземпляр абстрактного типу даних, що формалізує концепцію впорядкованої множини елементів. Наприклад, абстрактний тип даних для безтипових, змінних списків можна визначити із допомогою конструктора та чотирьох операцій:
конструктор для створення порожнього списка;
операція визначення порожності списка;
операція для додавання елемента в початок списка (cons в Лісп);
операція отримання першого елемента списка (або «голови») списка (car в Лісп);
операція для визначення списка, що складається із всіх елементів списка окрім першого (або його «хвоста») (cdr в Лісп).
За визначенням, список — це послідовність з n≥0 елементів X[1],X[2], … X[n], для якої виконується наступна умова: якщо n>0 та X[1] — перший елемент у списку, а X[n] — останній, то k-й елемент розташований між X[k-1] та X[k+1] елементами для усіх 1<k<n.
З такими структурами даних виконуються наступні операції:
отримання k-го елемента списку для читання чи запису в нього нового значення;
додавання нового елемента в будь-яку позицію в списку;
видалення елемента списку;
об'єднання в одному списку двох або більше лінійних списків;
розбиття списку на два або більше фрагментів;
створення копії списку;
визначення кількості елементів в списку;
сортування елементів списку;
пошук елемента, що задовільняє певним критеріям.
1.Завдання 1:
1.1.Теоретична частина
СТЕК в інформатиці та програмуванні -- різновид лінійного списку, структура даних, яка працює за принципом (дисципліною) "останнім прийшов -- першим пішов" (LIFO, last in, first out). Всі операції (наприклад, видалення елементу) в стеку можна проводити тільки з одним елементом, який знаходиться на верхівці стеку та був введений в стек останнім.
Стек можна розглядати як певну аналогію до стопки тарілок, з якої можна взяти верхню, і на яку можна покласти верхню тарілку (інша назва стеку -- "магазин", за аналогією з принципом роботи магазину в автоматичній зброї)
Операції зі стеком
push ("заштовхнути елемент"): елемент додається в стек та розміщується в його верхівці. Розмір стеку збільшується на одиницю. При перевищенні розміру стека граничної величини, відбувається переповнення стека (stack overflow)
pop ("виштовхнути елемент"): отримує елемент з верхівки стеку. При цьому він видаляється зі стеку і його місце в верхівці стеку займає наступний за ним відповідно до правила LIFO, а розмір стеку зменшується на одиницю. При намаганні "виштовхнути" елемент з вже пустого стеку, відбувається ситуація "незаповнення" стеку (stack underflow)
Кожна з цих операцій зі стеком виконується за фіксований час O(1) і не залежить від розміру стеку.
Додаткові операції (присутні не у всіх реалізаціях стеку):
isEmpty: перевірка наявності елементів в стеку; результат: істина (true), коли в стеку немає елементів.
isFull: перевірка заповненості стека. Результат: істина, коли додавання нового елементу неможливе
clear: звільнити стек (видалити усі елементи).
top: отримати верхній елемент (без виштовхування).
size: отримати розмір (кількість елементів) стека.
swap: поміняти два верхніх елементи місцями.
Організація в пам'яті комп'ютера
Стек може бути організований як масив або множина комірок в певній області комп'ютера з додатковим зберіганням ще й вказівника на верхівку стека. Заштовхування першого елемента в стек збільшує адресу вказівника, виштовхування елементу зменшує її. Таким чином, адреса вказівника завжди відповідає комірці масиву, в якій зараз знаходиться верхівка стеку.
Багато процесорів ЕОМ мають спеціалізовані регістри, які використовуються як вказівники на верхівку стеку, або використовують деякі з регістрів загального вжитку для цієї спеціальної функції в певних режимах адресації пам'яті.
Приклади застосування
Калькулятори, які використовують зворотню польську нотацію, використовують стек для збереження даних обчислень.
Існує велика кількість "стеко-орієнтованих" мов програмування (Forth, PostScript), які використовують стек як базову структуру даних при виконанні багатьох операцій (арифметичних, логічних, вводу-виводу тощо).
Стеко-орієнтованими є багато з віртуальних машин, наприклад віртуальна машина Java.
Компілятори мов програмування використовують стек для передавання параметрів в процесі виклику підпрограм, процедур та функцій. Спеціалізований стек використовується також для збереження адрес повернення з підпрограм.
Реалізація базових алгоритмів
На високорівневих мовах програмування, стек може бути реалізований за допомогою масиву та додаткової змінної:
Для зберігання елементів стеку резервується масив S[1 n] певного розміру та додаткова змінна top[S], яка буде зберігати індекс верхівки стеку.
Операції push та pop тоді можуть бути записані так (без перевірки на переповнення та "незаповнення"):
PUSH (S, x)
1 top[S]:= top[S]+1 //збільшення індексу на 1
2 S[top[S]]:=x //запис нового елемента у верхівку стека
POP (S)
1 top[S]:=top[S]-1 // зменшення індексу на 1
2 return S[top[S]+1] //повернення колишньої верхівки стеку
1.2.Опис алгоритму:
Вхідний текст для обробки будем вважати як масив символів.При проході всього тексту, знайшовши:
-будь-яку форму відкритої дужки(‘(’,’[’,’<’) – заносим цю дужку у стек і також заносим порядкове значення цієї дужки.
- будь-яку форму закритої дужки(‘)’,’]’,’>’) – заносим цю дужку у стек і також заносим
порядкове значення цієї дужки. Видаляєм цю дужку зі стеку.Перевіряєм, чи ця закриваюча дужка відповідає свої формі дужки, яка є у вершині стеку, якщо так то виводим, що ці дужки відповідають один одному і видаляєм відкриваючу дужку зі стеку, якщо ні то показуєм, що нема відповідності дужок.
1.3.Система тестів:
1 2 3 4 5
Нехай заданий текст: (5+3)/2-[3-2))
1-крок:
Вміст стеку: (
Дужка, яка обробляється: (5+3)/2-[3-2))
2-крок:
Вміст стеку:
Виводим, що є відповідність дужок(1 дужка відповідає 2 дужці)
Дужка, яка обробляється: (5+3)/2-[3-2))
3-крок:
Вміст стеку: [
Дужка, яка обробляється: (5+3)/2-[3-2))
4-крок:
Вміст стеку:
Бачимо, що закриваюча дужка ‘)’ не відповідає формі дужки, яка знаходиться у
вершині стеку. Тому виводим, що закриваючій дужці ‘)’ нема відповідної закриваючої дужки(вивід - 4)і виводим, що відкриваючі дужці ‘[’ нема відповідної закриваючої дужки(вивід 3 -).
Дужка, яка обробляється: (5+3)/2-[3-2))
5-крок:
Вміст стеку:
Бачимо, що стек пустий, нема з чим порівнювати закриваючу дужку ‘)’. Тому виводим, що закриваючій дужці ‘)’ нема відповідної відкриваючої дужки(вивід - 5).
Результат: 1 2
-
4
5
1.4.Специфікація програми:
У програмі є оголошений клас Stack. В ньому є такі методи:
-Stack(int nSize)
Конструктор, аргументом якого є змінна nSize, яка відповідає за розмір стеку
-void Add(char elem)
Метод, який додає символ дужки будь-якої форми.
-char front()
Метод, який повертає елемент, який знаходиться у вершині стеку.
-void pop()
Метод, який вилучає елемент зі стеку.
-int size()
Метод, який повертає кількість елементів у стеку.
-void AddPor(int a)
Метод, який додає порядковий номер певної дужки.
-char Por()
Метод, який повертає порядковий номер певної дужки
-bool empty()
Метод, який повертає чи стек повний, чи не повний.
У коді присутня функція void CKyrsovaDlg::OnGetResult()
Яка є обробником події для кнопки, яка виводить результат.
Оголощена змінна stack1. Змінна за допомогою якої відбувається додавання елементів у стек, вилучення і т. д.
Оголошена змінна str типу CString, за допомогою якої відбувається вивід таблиці порядкових значень дужок.
Оголошена змінна m_list за допомогою якої відбувається додавання у список порядкових значень дужок.(List Control).
Оголошена змінна m_String за допомогою якої відбувається ввід вхідного текту.(Edit Control).
1.5.Результати виконання програми:
2.Завдання 2:
2.1.Теоретична частина:
В програмуванні бінарне дерево -- дерево структура даних, в якому кожна вершина має не більше двох дітей. Зазвичай такі діти називаються правим та лівим. На базі бінарних дерев будуються такі структури, як бінарні дерева пошуку та бінарні купи.
Бінарне дерево
Різновиди бінарних дерев
Бінарне дерево -- таке кореневе дерево, в якому кожна вершина має не більше двох дітей.
Повне (закінчене) бінарне дерево -- таке бінарне дерево, в якому кожна вершина має нуль або двох дітей.
Ідеальне бінарне дерево -- це таке повне бінарне дерево, в якому листя (вершини без дітей) лежать на однаковій глибині (відстані від кореня).
Бінарне дерево на кожному n-му рівні має від 1 до 2n вершин.
Обхід бінарного дерева Часто виникає необхідність обійти усі вершини дерева для аналізу інформації, що в них знаходиться. Існують декілька порядків такого обходу, кожний з яких має певні властивості, важливі в тих чи інших алгоритмах: прямий (preorder), центрований (inorder) та зворотній (postorder).
Реалізація бінарних дерев
Реалізація бінарного дерева. Кожна вершина містить вказівники на праву та ліву дитину (left та right)
Існують декілька варіантів конструювання бінарних дерев в залежності від задач, які вирішуються цими структурами та можливостей тої чи іншої мови програмування. Реалізація з використанням вказівників передбачає зберігання в кожній вершині дерева x разом з даними двох полів з вказівниками (правим та лівим) right[x] та left[x] на відповідних дітей цієї вершини.
Модифікована реалізація бінарного дерева. Кожна вершина містить також вказівник на батьківську вершину
Також іноді додається вказівник p[x] на батьківську вершину. Це виявляється корисним, коли необхідний швидкий доступ до батьківської вершини та спрощує деякі алгоритми. Іноді достатньо тільки вказівника на батьківську вершину. Взагалі будь-яке орієнтоване дерево можна описати, знаючи тільки зв'язки від дітей до батьківської вершини. Деякі різновиди бінарних дерев (наприклад, червоно-чорні дерева або AVL-дерева), вимагають збереження в вершинах і деякої додаткової інформації. Якщо у вершини відсутня одна чи обидві дитини, відповідні вказівники ініціалізуються спеціальними "пустими" значеннями.
Бінарне дерево на базі масиву
Бінарні дерева також можуть бути побудовані на базі масивів. Такий метод набагато ефективніший щодо економії пам'яті. В такому представленні, якщо вершина має порядковий номер i, то її діти знаходяться за індексами 2i+1 та 2i+2, а батьківська вершина за індексом ((i-1)/2) (за умов, що коренева вершина має індекс 0). Інший варіант зберігання дерева в масиві — зберігати індекси дітей.
Представлення n-арних дерев як бінарних
Існує єдине та взаємооднозначне відображення довільного впорядкованого дерева в бінарне.
Для цього слід послідовно зв'язати усіх дітей кожної сім'ї з першою дитиною та та видалити усі вертикальні з'єднання за виключенням з'єднання батька з першою дитиною в сім'ї. Тобто кожна вершина N впорядкованого n-арного дерева відповідає вершині M деякого бінарного дерева. Ліва дитина вершини M відповідає першій дитині вершини N, а права дитина M відповідає першому з наступних братів N (тобто першому з наступних дітей батька вершини N).
Така відповідність має назву природної відповідності між n-арним та бінарним деревом.
Б) Бінарне дерево пошуку:
Бінáрне дéрево пóшуку (англ. binary search tree, BST) в інформатиці - бінарне дерево, в якому кожній вершині x співставлене певне значення val[x]. При цьому такі значення повинні задовольняти умові впорядкованості:
нехай x -- довільна вершина бінарного дерева пошуку. Якщо вершина y знаходиться в лівомі піддереві вершини x, то val[y] ≤ val[x]. Якщо у знаходиться у правому піддереві x, то val[y] ≥ val[x].
Таке структурування дозволяє надрукувати усі значення у зростаючому порядку за допомогою простого алгоритма центрованого обходу дерева. Бінарні дерева пошуку набагато ефективніші в операціях пошуку, аніж лінійні структури, в яких витрати часу на пошук пропорційні O(n), де n -- розмір масиву даних, тоді як в повному бінарному дереві цей час пропорційний в середньому O(log2n) або O(h), де h - висота дерева (хоча гарантувати, що h не перевищує log2n можна лише для збалансованих дерев, які є ефективнішими на пошукових алгоритмах, аніж прості бінарні дерева пошуку).
Пошук в бінарному дереві
Процедура пошуку в бінарному дереві отримує на вході значення k, яке необхідно знайти, та вказівник x на корень того піддерева, в якому слід шукати.
SEARCH (x, k)
1 if x = NULL or k = val[x]
2 then return x
3 if k < val[x]
4 then return SEARCH (left[x], k)
5 else return SEARCH (right[x], k)
В процесі пошуку ми рухаємось від кореня, порівнюючи значення k зі значенням в поточній вершині х. Якщо k < val[x], пошук рекурсивно продовжується в лівому піддереві (k може бути тільки там згідно умови впорядкованості), інакше -- у правому піддереві. Очевидно, що довжина шляху не перевищує висоти дерева, тому час пошуку є O(h), де h - висота дерева.
Мінімум, максимум, наступник та попередник
Мінімальний елемент в дереві можна знайти, розглянувши послідовно ліве піддерево left[x]:
MINIMUM (x)
1 while left[x]<>NULL
2 do x:=left[x]
3 return x
Процедура знаходження максимуму симетрична. Обидві процедури знову ж таки знаходять елемент за час, пропорційний O(h)
Елемент, що є наступним за даним (в сенсі відношення впорядкованості) можна знайти за допомогою такої процедури:
SUCCESSOR (x)
1 if right[x] <> NULL
2 then return MINIMUM (right[x])
3 y:=p[x]
4 while y<>NULL and x = right[y]
5 do x:=y
6 y:=p[y]
7 return y
Процедура знаходження попереднього даному елемента є симетричною. Обидві процедури знову ж таки знаходять елемент за час, пропорційний O(h)
Додавання елементу
Процедура додавання елементу в бінарне дерево T додає елемент, зберігаючи умову впорядкованості. Параметром тут є вказівник z на нову вершину, в яку поміщене значення val[z], left[z]=right[z]=NULL.
INSERT (T, z)
1 y:=NIL
2 x:=root[T]
3 while x <> NULL
4 do y:=x
5 if val[z] < val[x]
6 then x:=left[x]
7 else x:=right[x]
8 p[z]:=NULL
9 if y = NULL
10 then root[T] :=z
11 else if val[z]<val[y]
12 then left[y]:=z
13 else right[y]:=z
Процедура рухається вниз по дереву, при цьому зберігаючи в y вказівник на батька вершини x. Порівнюючи значення в x та z, процедура вирішує, в яке з піддерев рухатись далі. Процес завершується тоді, коли x=NULL. Саме сюди й слід помістити вершину z (рядки 8-13). Ця операція також потребує часу для виконання, пропорційного O(h)
Видалення елементу
Параметром для процедури є вказівник на вершину, що видаляється. Тут можливі три варіанти дій:
якщо у вершини немає дітей, достатньо помістити NULL у відповідне поле його батька (замість вказівника на вершину, що видаляється)
якщо у вершини є одна дитина, можна з'єднати батька цієї вершини безпосередньо з її дитиною
якщо вершина має двох дітей, слід спочатку знайти слідуючий (в сенсі порядку) елемент y, в якого немає лівої дитини, а потім скопіювати значення та додаткові дані з вершини y на місце вершини, що видаляється, а саму вершину y видалити.
DELETE (T, z)
1 if left[z] = NULL or right[z]=NULL
2 then y:=z
3 else y:=SUCCESSOR(z)
4 if left[y] <> NULL
5 then x:=left[y]
6 else x:= right[y]
7 if x <> NULL
8 then p[x]:=p[y]
9 if p[y]:=NULL
10 then root[T]:=x
11 else if y=left[p[y]]
12 then left[p[y]] :=x
13 else right[p[y]]:=x
14 if y <> z
15 then val[z]:=val[y]
16 //копіювання додаткових даних з y
17 return y
2.2.Опис алгоритму:
Задану послідовність сортуєм за допомогою симетричного обходу бінарного дерева.
Функція, яка повертає результуючу послідовність(найбільша неспадаюча послідовність) отримує на вхід задану послідовність чисел(А) і відсортовану послідовність чисел(В).Будується двовимірна матриця max_len розміром(залежно від к-ості елементів послідовності) в нашому випадку max_len[12][12]. Невідсортовану послідовність запишем перед рядками матриці а відсортовану послідовність запишем над стовпцями матриці.Детальніше у розділі 2.3 Система тестів. В елементі матриці max_len[i][j] буде зберігатися довжина найбільшої спільної підпослідовності для префіксів A[1…i] i B[1…j].
В елементі max_len[12][12] , буде знаходитись дожина найбільшої спільної підпослідовності.
2.3.Система тестів:
Нехай задана послідовність чисел: 62 30 32 72 69 5 42 78 40 41 45 57
Відсортована послідовність: 5 30 32 40 41 42 45 57 62 69 72 78
Вигляд побудованої матриці:
62 30 32 72 69 5 42 78 40 41 45 57
5 6 6 5 4 3 3 3 3 3 2 2 1
30 6 6 5 4 3 3 2 2 2 2 2 1
32 5 5 5 4 3 3 2 2 2 2 2 1
40 5 4 4 4 3 3 2 2 2 2 2 1
41 5 4 4 4 3 3 2 2 2 2 1 1
42 5 4 4 4 3 3 2 1 1 1 1 1
45 4 4 4 4 3 3 2 1 1 1 1 1
57 4 4 4 4 3 2 2 1 1 1 1 1
62 4 4 4 4 3 2 2 1 0 0 0 0
69 3 3 3 3 3 2 2 1 0 0 0 0
72 2 2 2 2 2 2 2 1 0 0 0 0
78 1 1 1 1 1 1 1 1 0 0 0 0
Наприклад, якщо взяти елемент max_len[6][4].Значення елементу max_len[6][4] буде дорівнюватиме довжині найбільшій спільній зростаючій підпослідовності послідовності 62 30 32 72 69 5(6 елементів) і послідовності 5 30 32 40(4 елемента). Результат 2.
Бачимо, що max_len[12][12]=6. Це означає, що довжина найдовшої спільної підпослідовності =6.
За допомогою цього циклу у вектор result записуєм результуючу послідовність:
vector<int> res;
for(int i = 0, j = 0; max_len[i][j] != 0 && i < a.size() && j < b.size(); )
{
if(a[i] == b[j])
{
res.push_back(a[i]);
14.04.2013 01:04-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора