Анализ алгоритмов нечисленной обработки данных

35

Аннотация

Данный курсовой проект посвящен рассмотрению и изучению алгоритмов нечисленной обработки данных - линейный и двоичный поиск, а также упорядочение массива методом сортировки деревом. Алгоритмы реализованы на языке Turbo Pascal 7.0.

Содержание

1 Постановка задачи 3

2 Метод решения 4

2.1 Сортировка двоичным деревом 4

2.1.1 Организация массива в виде двоичного дерева 4

2.1.2 Простейший способ 4

2.1.3 Описание построения дерева 5

2.1.4 Описание сортировки деревом 6

2.2 Линейный поиск 7

2.3 Двоичный поиск 8

2.4 Метод оценки времени поиска 10

3 Алгоритмизация задачи 11

3.1 Ввод и вывод массива 11

3.2 Линейный поиск 12

3.3 Построение двоичного дерева 12

3.4 Сортировка двоичным деревом 13

3.5 Двоичный поиск 14

3.6 Запись в файл 15

4 Инструкции по пользованию программой 16

4.1 Руководство пользователя 16

4.2 Руководство программиста 16

4.2.2 Процедура Vivod 17

4.2.3 Процедура Save_To_File 17

4.2.4 Процедура Lin_Poisk 17

4.2.5 Процедура Dv_Poisk 17

4.2.6 Процедура Tree 18

4.2.7 Процедура Tree_Sort 18

4.3 Область и условия применения программы 18

5 Анализ результата 19

5.1 Линейный поиск 19

5.2 Двоичный поиск 20

5.3 Анализ сортировки деревом 22

Заключение 24

Список литературы 25

Приложение А 26

Приложение Б 29

1 Постановка задачи

Необходимо:

1) Создать набор входных данных длиной 16, 128, 512, 1024 элементов для программ поиска и сортировки. Для массива длиной, не превышающей 16 элементов, предусмотреть ввод элементов с клавиатуры, в остальных случаях - генератором случайных чисел.

2) Разработать алгоритм и программу упорядочения методом минимальной по памяти турнирной сортировки.

3) Разработать алгоритм и программу поиска заданного элемента в неупорядоченных массивах. Метод линейного и двоичного поиска.

4) Осуществить отладку программы на тестовых примерах.

5) Оценить время сортировки и поиска информации для массивов заданной длины.

Требования к программе:

1) основные алгоритмы оформить в виде подпрограмм;

2) программа должна быть самодокументированной;

Обеспечить формирование массива:

1) путем ввода элементов с клавиатуры при n?16;

2) с помощью генератора случайных чисел при n>16;

2 Метод решения

2.1 Сортировка двоичным деревом

2.1.1 Организация массива в виде двоичного дерева

Чтобы облегчить поиск в массиве элемента с нужным значением признака, не обязательно упорядочивать его по этому признаку в линейную последовательность. Двоичным называется ориентированное дерево, у которого в каждую вершину, кроме одной, корня дерева, заходит одна дуга и из каждой вершины исходит не более двух дуг. Ветвью дерева называют поддерево, состоящее из некоторой дуги данного дерева, ее начальной и конечной вершин, а также всех вершин и дуг, лежащих на всех путях, выходящих из конечной вершины этой дуги.

2.1.2 Простейший способ

Сначала рассматривается весьма простой метод построения дерева, организующего массив. При этом методе, в известном смысле, отдаются на волю случая. Как будет видно, можно все же получить хорошие результаты, если в исходном состоянии массива значения признака, взятые в порядке возрастания номеров элементов, образуют хорошо перемешанную последовательность.

Первый элемент массива поместим в корень дерева. Со вторым элементом поступают так. Сравнивают значение p2 признака этого элемента со значением p1 признака элемента, помещенного в корень дерева (т.е первого элемента).

Если p2<p1, то к корню пририсовывают дугу, направленную влево, и помещают второй элемент в конце этой дуги. Если же p2?p1, то делают то же самое, но дугу направляют вправо. В общем случае, когда требуется выбрать место на дереве для i-го элемента массива (к этому моменту дерево уже содержит i- 1 вершину и i-2 дуги), поступают следующим образом. В процессе выбора просматривается некоторый путь по дереву (цепочка смежных неповторяющихся вершин и дуг), выходящий всегда из корня. Чтобы, находясь в некоторой вершине пути, определить, обрывается ли путь в этой вершине, а если нет, то какая вершина следующая, применяется один и тот же прием для каждой вершины, в том числе и для корня. Сравнивается значение pi признака размещаемого элемента со значением pk признака элемента, помещенного в данной вершине. Если pi <pk , то смотрят, исходит ли из этой вершины дуга влево. Если исходит, то вершина в конце этой дуги будет следующей вершиной пути, если нет, то достраивают эту дугу и помещают i-й элемент в ее конце. Если же pi ? pk , то все происходит аналогично, но с дугой, направленной вправо. Таким образом, из каждой вершины может исходить самое большее две дуги, как и полагается для двоичного дерева.

Метод организации массива в виде двоичного дерева требует несколько больших затрат как на организацию массива, так и на поиск в нем нужного элемента, чем это минимально необходимо. Впрочем, это увеличение не столь существенно. Этот метод оптимален по порядку роста трудоемкости поиска в зависимости от размера массива. Это означает, что для данного метода, так же как и для оптимального, эта зависимость имеет вид c•log n (с точностью до величин меньшего порядка роста) и разница заключается лишь в значении коэффициента пропорциональности c.

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 видно, что для нахождения элемента X=11 пришлось выполнить 9 сравнений. Если бы элемента 11 не оказалось под номером 9, то поиск выполнялся бы до его нахождения, либо до окончания массива.

Страницы: 1, 2, 3, 4, 5