Контрольные вопросы
В чем суть метода сортировки обменом и почему его зовут метод «пузырька»?
Какие группы алгоритмов сортировки можно выделить?
Как работают методы быстрой сортировки?
Как оценить скорость алгоритмов сортировки?
Что представляет из себя двоичный поиск.
Задание 5. «полиз»
Цель работы: познакомиться с алгоритмами работы с нелинейными структурами данных
Краткие теоретические сведения
1. Деревья (нелинейные структуры данных)
Дерево состоит из элементов, называемых узлами. Каждый узел имеет оригинальный ключ (как правило, это целое число), данные и поля ссылки. Т.е. каждый узел может ссылаться на другие узлы и если XY узел X называется предком (родителем), а Y - потомком (сыном) или дочерним узлом. Одинаковые ключи здесь не допускаются.
Дерево имеет единственный узел, у которого нет предков. Такой узел называют корнем дерева. Любой другой узел имеет ровно одного предка. Узел, не имеющий потомков, называется листом.
Внутренний узел – это узел, не являющийся ни листом ни корнем.
Бинарное дерево - это дерево, состоящее из узлов, каждый из которых содержит не более двух ссылок на различные бинарные поддеревья, т.е. у каждого его узла (предка) может быть не более двух потомков - левый и правый. Таким образом, на каждый узел бинарного дерева имеется ровно одна ссылка.
На рисунке приведен пример бинарного дерева (корень обычно изображается сверху, хотя изображение можно и перевернуть).
Если дерево организовано так, что для каждого узла все ключи его левого поддерева меньше ключа этого узла, а все ключи его правого поддерева - больше, оно называется деревом поиска.
Обычно бинарное дерево строитсясразу упорядоченным, т.е. ключ узла левого сына имеет значение меньшее, чем значение ключа у родителя, а узел правого сына - большее.
Например, если приходят числа 17, 18, 6, 5, 9, 23, 12, 7, 8, то построенное по ним дерево будет выглядеть следующим образом (для упрощения приводим только ключи):
Существуют три алгоритма обхода деревьев, которые естественно следуют из самой структуры дерева.
Обход слева направо: Left-Root-Right: сначала посещаем левое поддерево, затем - корень и, наконец, правое поддерево.
(Или наоборот, справа налево: Right -Root- Left)
2) Обход сверху вниз: Root-Left-Right : посещаем корень до поддеревьев.
3) Обход снизу вверх: Left-Right-Root: посещаем корень после поддеревьев
Иллюстрация алгоритмов обхода деревьев приведена в теме «Построение обратной польской записи»
2. Построение обратной польской записи
Одной из главных причин, лежащих в основе появления языков программирования высокого уровня, явились вычислительные задачи, требующие больших объемов вычислений. Поэтому к языкам программирования предъявлялись требования максимального приближения формы записи арифметических выражений к естественному языку математики с последующим их вычислением путем их трансляции. Здесь наибольшее распространение получил метод трансляции с помощью обратной польской записи («ПОЛИЗ»), которую предложил польский математик Я.Лукашевич: – представление перед вычислениями арифметического выражения в постфиксной форме.
И прежде чем рассмотреть конкретные примеры, познакомимся с различными способами записи арифметических выражений. Пусть для операндов a и b выполняется операция сложения. Мы привыкли записывать это в виде a+b. Такая форма записи называется инфиксной. Наряду с этой формой записи существуют еще префиксная (+ab) и постфиксная (ab+) формы записи арифметических выражений. Отличаются они друг от друга положением знака операции по отношению к операндам: - в инфиксной записи знак операции располагается между операндами, над которыми эта операция выполняется; - в префиксной записи знак операции предшествует соответствующим операндам, а в постфиксной - знак операции располагается за операндами.
Пример. Использование бинарного дерева.
Пусть задано простое арифметическое выражение вида:
(a+b)*(c+d)-e (5.1)
Представим это выражение в виде дерева, в котором узлам соответствуют операции, а листьям - операнды.
Алгоритм построения такого дерева следующий.
Построение начинают с корня, в качестве которого выбирается операция, выполняющаяся последней. Левой ветви соответствует левый операнд операции, а правой ветви - правый.
Если выражение сложное, то далее в узлах очередного уровня размещают операции по восходящей очередности их выполнения.
В узлы последнего уровня помещают операции, которые будут выполнены в первую очередь.
И наконец операнды – листья дерева.
Дерево выражения (5.1) имеет вид:
Совершим обход дерева, под которым будем понимать формирование строки символов из символов узлов и ветвей дерева. Обход будем совершать от самой левой ветви вправо и узел переписывать в выходную строку только после рассмотрения всех его ветвей (обход по алгоритму «Левое поддерево – Правое поддерево – Корень», строго по уровням, т.е. последовательно снизу вверх). Результат обхода дерева имеет вид:
ab+cd+*e- (5.2)
Характерные особенности выражения (2) состоят в следовании символов операций за символами операндов и в отсутствии скобок. Такая запись называется обратной польской записью.
Обратная польская запись - идеальный промежуточный язык при трансляции:
вычисление выражения, записанного в обратной польской записи, проводится путем его однократного просмотра слева направо, что является весьма удобным при генерации объектного кода программ.
Алгоритм вычислений «ПОЛИЗ» следующий:
Если текущий элемент записи – операнд. То переходим к следующему элементу.
Если же текущий элемент записи – символ операции, то эта операция выполняется над ближайшими двумя операндами, расположенными слева от этой операции. Полученный результат размещают на месте самого левого операнда а сами операнды и символ операции из «ПОЛИЗа» вычеркивают.
В результате последовательно будут выполнены все операции а сама запись сократится до одного элемента: конечного результата.
Например, вычисление выражения (2) может быть проведено следующим образом:
-
№
Анализируемая строка
Действие
1
аb+сd+*e-
r1=a+b
2
r1cd+*e-
r2=c+d
3
r1r2*e-
r1=r1*r2
4
r1e-
r1=r1-e
5
r1
Здесь r1и r2 - вспомогательные переменные.
r1 на пятом уровне – конечный результат
“Польская запись”
Получить выражение в постфиксной форме и вычислить по полученному ПОЛИЗу значение выражения.
Пример: R=(a+b)*(c-d)/e –вводимое выражение;
а=3 b=5 c=6 d=9 е=7 –значения операндов.
Результат выполнения программы:
R=ab+cd-*e/
R=-3.42857