Навигация
Описание построения дерева
32292
знака
12
таблиц
3
изображения
2.1.3 Описание построения дерева
Пусть каждый элемент исходного массива a состоит из двух полей: признака a[i,1] и собственно значения элемента a[i,2], где i – номер элемента в исходном массиве. Чтобы описать массив, упорядоченный в виде дерева, каждый элемент надо снабдить ещё, по меньшей мере двумя полями, содержащими номера элементов, расположенных в конце левой и правой дуг, исходящих из вершины, в которую помещён данный элемент. Этих двух дополнительных полей достаточно для построения дерева и для поиска в нем. Однако для других операций с деревом желательно иметь ещё одно поле, содержащее номер того элемента, к которому подвешен (безразлично, слева или справа) данный элемент. Пусть исходный массив уже содержит все необходимые поля, то есть, описан как
mas=array [1..n, 1..5] of integer,
но значения дополнительных полей a[i,3], a[i, 4] и a[i,5] перед началом работы алгоритма не определены. Называются эти поля соответственно левым, правым и обратным указателем. Если после окончания работы алгоритма левый (правый) указатель какого-либо элемента содержит нуль, это означает, что из вершины, в которую помещён данный элемент, не исходит левая (правая) дуга. Обратный указатель содержит нуль только для первого элемента, который помещён в корне дерева. Остальные детали процедуры ясны из приведённого в начале этого раздела словесного описания алгоритма.
2.1.4 Описание сортировки деревом
Имеются два массива: a – исходный и b – отсортированный. В массиве b элементы массива a расположены в порядке возрастания значения признака. Если у элемента есть левая ветвь, то элемент с наименьшим значением признака разыскивается на этой ветви. Если у элемента левой ветви нет, то он переносится в массив b, так как в массиве нет элемента с меньшим значением признака. После этого очередной элемент разыскивается в правой ветви, если она есть, или возвращается по обратному указателю. После возвращения к какому-либо элементу по левой или правой ветви дальнейшие действия идут так, как будто у этого элемента соответствующей ветви нет.
2.2 Линейный поиск
Для неупорядоченного исходного массива единственным способом нахождения заданного элемента в этом массиве является линейный поиск. Этот метод состоит в последовательном сравнении каждого элемента массива с заданным для поиска элементом. При линейном поиске иногда просматривается половина, а то и больше элементов исходного массива. Этот метод удобен и прост для массивов с меньшей длиной. Для массивов большей длины это метод вызывает затруднения, так как время поиска будет очень медленным.
Применим метод линейного поиска на примере поиска в неупорядоченном массиве A элемента X=11. Дан массив A, который состоит из 10 элементов.
Таблица 1 – Линейный поиск
| № Элемента | Сравнение | № Проверки |
| 1 | 5 | 1 |
| 2 | 12≠11 | 2 |
| 3 | 68≠11 | 3 |
| 4 | 0≠11 | 4 |
| 5 | 92≠11 | 5 |
| 6 | 87≠11 | 6 |
| 7 | 7≠11 | 7 |
| 8 | 32≠11 | 8 |
| 9 | 11=11 | 9 |
| 10 | 24 |
11Из таблицы 1 видно, что для нахождения элемента X=11 пришлось выполнить 9 сравнений. Если бы элемента 11 не оказалось под номером 9, то поиск выполнялся бы до его нахождения, либо до окончания массива.
2.3 Двоичный поиск
Одним из эффективных методов поиска в больших отсортированных массивах является двоичный, другое название бинарный, поиск. Так называемый, поиск методом деления пополам. Вместо просмотра подряд всех элементов массива делим его пополам. Так как массив отсортирован, то, сравнивая искомый элемент со значением среднего элемента массива, можно сделать вывод, о том, что может ли быть элемент с таким значением в массиве и в какой половине он находиться, то есть, определить область дальнейшего поиска. Затем делится пополам та часть массива, в которой находится элемент, и так до тех пор, пока рассматриваемая часть массива получится состоящей из одного элемента.
Допустим, есть упорядоченный по возрастанию массив из целых чисел. Необходимо определить, содержит ли этот массив некоторое число (образец).
Алгоритм двоичного поиска:
1. Сначала образец сравнивается со средним (по номеру) элементом массива
- если образец равен среднему элементу, то задача решена;
- если образец больше среднего элемента, то это значит, что искомый элемент расположен, ниже среднего элемента (между элементами с номерами sre+1), и за новое значение verhe принимается sre+i, а значение nize не меняется;
- если образец меньше среднего элемента, то это значит, что искомый элемент расположен выше среднего элемента (между элементами с номерами verhe и sre-1), и за новое значение nize принимается sre-1, а значение verhe не меняется.
2. После того как определена часть массива, в которой может находиться искомый элемент, вычисляется новое значение sredе и поиск продолжается.
Применим метод двоичного поиска на примере поиска в упорядоченном массиве. X – искомый элемент, равный 11, а A – массив, состоящий из 10 элементов:
1) 0 - verhe
5
7
11
12 - srede
24
32
68
87
92 – nize
srede равный 12>11 = X, следовательно искомый элемент находится выше среднего элемента.
2) 0 - verhe
5
7 - srede
11– nize
Srede равный 7< 11=X, значит нужный элемент находится ниже среднего элемента. Выполняем дальнейшее сравнение. Так как ниже остался всего один элемент, то сравниваем его с искомым.
3) 11=11
В итоге нужный элемент найден на третьем сравнении. Данный пример наглядно показывает всё удобство и легкость двоичного метода поиска. Результаты работы программы приведены в приложении Г.
Похожие работы
... процессов и явлений, использовать графику машины для повышения наглядности изучаемого материала. Использование пакетов прикладных учебных программ, готового программного обеспечения является одной из самых важных компонентов формирования компьютерной грамотности. При этом значительно расширяются межпредметные связи между многими учебными дисциплинами, особенно между математикой и информатикой. ...
... практичных алгоритмов оптимизированного перебора, позволяющих за разумное время осуществлять распараллеливание достаточно больших участков. Анализ работ, посвященных оптимизации кода для процессоров с параллелизмом на уровне команд показывает, что для достижения наилучших результатов необходимо применение комплекса оптимизаций, среди которых можно выделить следующие классы. Преобразования циклов ...
... і слова в орфографічному словнику контроль орфографічної правильності його написання слід здійснювати за правилами орфографії. Зараз готують до затвердження наступний п’ятий правопис. Тому в процесі редагування треба враховувати динамічність правопису і слідкувати за правописними змінами. Відхилення від правильного написання допустиме лише тоді, коли в повідомленні йдеться про юридичну справу і ...
... дисциплин. Горн рассматривает эти вопросы, отталкиваясь в своих рассуждениях от профессиональных интересов ученых в этой области еще на, стадии получения ими образования: «Информационно-компьютерная наука рассматривает прагматические аспекты использования символов их пользователями и интерпретаторами в качестве еще одного центрального вопроса таким же образом, как эти аспекты должны исследоваться ...
0 комментариев