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
511
2
12?11
3
68?11
4
0?11
5
92?11
6
87?11
7
7?11
8
32?11
9
11=11
10
24
Из таблицы 1 видно, что для нахождения элемента X=11 пришлось выполнить 9 сравнений. Если бы элемента 11 не оказалось под номером 9, то поиск выполнялся бы до его нахождения, либо до окончания массива.
Страницы: 1, 2, 3, 4, 5