Понедельник, Июль 5th, 2010

Структуры и алгоритмы обработки данных

Цель работы: исследовать и изучить методы сортировки с помощью дерева.

Задача работы: овладеть навыками написания программ для сортировки с помощью бинарного дерева на языке программирования ПАСКАЛЬ .

Порядок работы :
изучить описание лабораторной работы;
по заданию, данному преподавателем, разработать алгоритм программы решения задачи;
написать программу на языке ПАСКАЛЬ;
отладить программу;
решить задачу;
оформить отчет.

Краткая теория

При обработке данных в ЭВМ важно знать и информационное поле элемента, и его размещение в памяти машины. Для этих целей используется сортировка. Итак, сортировка — это расположение данных в памяти в регулярном виде по их ключам. Регулярность рассматривают как возрастание значения ключа от начала к концу в массиве.
Различают следующие типы сортировок:
внутренняя сортировка — это сортировка, происходящая в оперативной памяти машины
внешняя сортировка — сортировка во внешней памяти.
Схематичное представление двоичного дерева :                       имеется набор вершин, соединенных стрелками. Из каждой вершины выходит не более двух стрелок (ветвей ), направленных влево — вниз или вправо — вниз. Должна существовать единственная вершина, в которую не входит ни одна стрелка — эта вершина называется корнем дерева. В каждую из оставшихся вершин входит одна стрелка.

Существует множество способов упорядочивания дерева. Рассмотрим один из них :
» Левый » сын имеет ключ меньше, чем ключ » Отца »
» Правый » сын имеет ключ больше, чем ключ » Отца »
Получили бинарное упорядоченное дерево с минимальным числом уровней.
Строго сбалансированное дерево : дерево, в котором левое и правое поддерево имеют  уровни , отличающиеся  не более, чем на единицу.
Рассмотрим принцип построения дерева при занесении элементов в массив :
Пусть в первоначально пустой массив заносятся последовательно поступающие элементы :  70, 60, 85, 87, 90, 45, 30, 88, 35, 20, 86 ; Т.к. это еще пустое дерево, то ссылки left и right равны  nil( left — указатель на левого сына (элемент), right — указатель на правого сына (элемент)).
Четвертый из поступающих элементов 87. Т.к. этот ключ больше ключа 70 ( корень ), то новая вершина должна размещаться на правой ветви дерева. Чтобы определить ее место, спускаемся по правой стрелке к очередной вершине ( с ключом 85 ), и если поступивший ключ больше 85, то новую вершину делаем правым сыном вершины с ключом 85 .

В рассмотренном примере ПРИНЦИП ПОСТРОЕНИЯ ДЕРЕВА имеет следующий вид : если поступает очередной элемент массива, то начиная с корня дерева (в зависимости от сравнения текущего элемента с очередной вершиной) идем влево или вправо от нее до тех пор, пока не найдем подходящую вершину, к которой можно подключить новую вершину с текущим ключом. В зависимости от результата сравнения ключей, новую вершину делаем левой или правой для найденной вершины.

Алгоритм

Для создания дерева необходимо создать в памяти элемент следующего типа :

Тип на ПАСКАЛе :
type

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Категория: Учебники