Аннотация

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

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

Первый элемент массива поместим в корень дерева. ............