ign="justify"> Для кореня дерева рекурсивно викликається наступна процедура:
Відвідати вузол
Обійти ліве піддерево
Обійти праве піддерево
Приклади використання обходу:
· рішення задачі шляхом розподілу на частини
· разузлование зверху
· стратегія розділяй і володарюй (Сортування Фон Hеймана, швидке сортування, одночасне знаходження максимуму і мінімуму послідовності чисел, множення довгих чисел).
1.4 Сортування бульбашкою
Розташуємо масив зверху вниз, від нульового елемента - до останнього.
Ідея методу: крок сортування полягає в проході знизу вгору по масиву. По дорозі проглядаються пари сусідніх елементів. Якщо елементи деякої пари знаходяться в неправильному порядку, то міняємо їх місцями.
Після нульового проходу по масиву вгорі виявляється самий легкий елемент - звідси аналогія з бульбашкою. Наступний прохід робиться до другого зверху елемента, таким чином другий за величиною елемент піднімається на правильну позицію.
Робимо проходи по все зменшується нижній частині масиву до тих пір, поки в ній не залишиться тільки один елемент. На цьому сортування закінчується, так як послідовність впорядкована за зростанням.
lt; class T gt;
void bubbleSort (T a [], long size) {i, j; x; (i=0; i lt; size; i ++) {// i - номер проходу
for (j=size - 1; j gt; i; j--) {// внутрішній цикл проходу
if (a [j - 1] gt; a [j]) {= a [j - 1]; a [j - 1]=a [j]; a [j]=x;
}
}
}
}
Середнє число порівнянь і обмінів мають квадратичний порядок росту: Theta (n2), звідси можна зробити висновок, що алгоритм бульбашки дуже повільний і малоефективний.
Тим не менш, у нього є величезний плюс: він простий і його можна по-всякому покращувати.
1.5 Алгоритм Боуер і Мура (БМ)
Алгоритм Бойера-Мура, розроблений двома вченими - Бойером (Robert S. Boyer) і Муром (J. Strother Moore), вважається найбільш швидким серед алгоритмів загального призначення, призначених для пошуку підрядка в рядку. Перш ніж розглянути роботу цього алгоритму, уточнимо деякі терміни. Під рядком ми будемо розуміти всю послідовність символів тексту. Власне кажучи, мова не обов'язково повинна йти саме про тексті. У загальному випадку рядок - це будь-яка послідовність байтів. Пошук підрядка в рядку здійснюється за заданим зразком , тобто деякої послідовності байтів, довжина якої не перевищує довжину рядка. Наше завдання полягає в тому, щоб визначити, чи містить рядок заданий зразок.
Найпростіший варіант алгоритму Бойєр-Мура складається з наступних кроків. На першому кроці ми будуємо таблицю зміщень для шуканого зразка. Процес побудови таблиці буде описано нижче. Далі ми поєднуємо початок рядка і зразка і починаємо перевірку з останнього символу зразка. Якщо останній символ зразка та відповідний йому при накладенні символ рядка не збігаються, зразок зрушується щодо рядка на величину, отриману з таблиці зміщень, і знову проводиться порівняння, починаючи з останнього символу зразка. Якщо ж символи збігаються, проводиться порівняння передостаннього символу зразка і т.д. Якщо всі символи зразка співпали з накладеними символами рядки, значить ми знайшли підрядок і пошук закінчено. Якщо ж якийсь (не останній) символ зразка не збігається з відповідним символом рядка, ми зрушуємо зразок на один символ вправо і знову починаємо перевірку з останнього символу. Весь алгоритм виконується до тих пір, поки або не буде знайдено входження шуканого зразка, або не буде досягнутий кінець рядка.
Величина зрушення у разі неспівпадання останнього символу обчислюється виходячи з таких міркувань: зрушення зразка повинен бути мінімальним, таким, щоб не пропустити входження зразка в рядку. Якщо даний символ рядка зустрічається у зразку, ми зміщуємо зразок таким чином, щоб символ рядка збігся з самим правим входженням цього символу у зразку. Якщо ж зразок взагалі не містить цього символу, ми зрушуємо зразок на величину, рівну його довжині, так що перший символ зразка накладається на наступний за перевіряються символ рядка.
Величина зсуву для кожного символу зразка залежить тільки від порядку символів у зразку, тому зміщення зручно вирахувати заздалегідь і зберігати у вигляді одновимірного масиву, де кожному символу алфавіту відповідає зсув щодо останнього символу зразка. Пояснимо все вищесказане на простому прикладі. Нехай у нас є набір символів з п'яти символів: a, b, c, d, e і ми хочемо знайти входження зразка abbad в рядку" abecc...
