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

Аннотация

Данный курсовой проект посвящен рассмотрению и изучению алгоритмов нечисленной обработки данных – линейный и двоичный поиск, а также упорядочение массива методом сортировки деревом. Алгоритмы реализованы на языке 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 , то все происходит аналогично, но с дугой, направленной вправо. Таким образом, из каждой вершины может исходить самое большее две дуги, как и полагается для двоичного дерева.

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

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать