Учебно-методическии комплекс дисциплины «Структуры и алгоритм обработки данных» (стр. 14 )

Для обхода дерева  с использованием указанной функции и выдачи на  печать поля данных каждой вершины можно использовать следующую функцию:

procedure InOrder (root:TreePointer);

begin

  if root>nil then

  begin 

  InOrder(root. lett) ;

  write { root^ .data) ;

  InOrder(root^.right);

  end;

end.

Эта  функция делает  обход  дерева во  внутреннем  порядке  и  завершается  при обнаружении терминального листа (указателя о нулевом завершении). Ниже показаны функции для прохождения дерева в прямом и обратном порядке:

procedure PreOrder(root:TreePointer};

begin

  if root<>nil then

  begin

  write(root^.data);

  preorder(root^.left);

  preorder (root^. right) ;

  end;

end.

procedure PostOrder(root:TreePointer);

begin

  if root<>nil then

  begin

  postorder (root. left) ;

  postorder (root. right) ;

Write (root^.data);

end;

end;

Задания для самостоятельного выполнения

1.  Составьте программу, которая строит упорядоченное двоичное дерево и выводит его на экран

Лабораторная работа №3. Решение задачи поиска

Цель: уметь использовать различные методы поиска в массивах

Массивы наиболее часто используются при подготовке статистических сводок, справочных изданий, словарей и т. д. Самый простой способ поиска информации в данном случае - последовательный просмотр-перебор всех элементов массива. Для облегчения поиска необходимых данных содержимое массива упорядочивается, как правило уже известными вам способами.

Рассмотрим наиболее часто встречающуюся задачу поиска необходимого элемента в отсортированном массиве, и алгоритм её решения.

Дан отсортированный по возрастанию массив  вещественных  чисел  A состоящий из n элементов.  Определить, содержит ли данный массив число B, и если содержит,  то определить номер (индекс) данного  элемента  в массиве.

Предположим, что в массиве A имеется элемент,  равный B, т. е. существует такой индекс p,  что A[p]=B.  По результату любого  сравнения A[s]<B (1<s<n) мы сразу определяем,  лежит ли p в диапазоне от 1 до s, или же в диапазоне от s+1 до n:  второе будет иметь место,  если неравенство A[s]<B справедливо, а первое - если не справедливо. Это свойство данного сравнения используется в алгоритме деления пополам.

  Алгоритм деления пополам.

Первоначально номера крайних элементов массива 1 и n берут в  качестве границ поиска элемента; далее, до тех пор, пока границы не совпадут, шаг за шагом сдвигают эти границы следующим образом: сравнить B с  A[s],  где  s  - целая часть среднего арифметического границ;  если A[s]<B,  то заменить прежнюю нижнюю границу на  s+1,  оставив  верхнюю границу без изменения,  иначе оставить без изменения нижнюю границу,  а верхнюю границу заменить на s. Поиск закончится когда границы совпадут.

Сказанное можно  записать в виде последовательности операторов TP. В этом фрагменте p и q обозначают упомянутые верхнюю и нижнюю границы.

  p:=1; q:=n;

  while p<q do

  begin

  s:=(p+q) div 2;

  if a[s]<b then p:=s+1

  else q:=s;

  end;

  Схематически процесс поиска можно изобразить в виде схемы:

  +-------------------------0-------------------------------+

  ¦  +---------------1---------------¦

  ¦  +-------2--------+  ¦

  ¦  ¦  +----3---¦  ¦

  ¦  ¦  +--4-+  ¦  ¦

  ¦  ¦  +-5+ ¦  ¦  ¦

  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20

Заметим сразу следующее.  Мы исходим из предположения,  что среди элементов массива имеется такой,  который равен B.  Если заранее неизвестно, имеется или нет такой элемент,  то,  получив p,  надо дополнительно проверить, действительно ли A[p]=B.

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

Задания для самостоятельного выполнения.

1. Напишите  программу,  которая организует хранение в массиве 15 различных введённых с клавиатуры целых чисел.  Содержимое массива сортируется по  возрастанию.  После этого,  с клавиатуры запрашивается  контрольное число, наличие которого в массиве необходимо проверить. Номер элемента массива,  в положительном случае, выводится на экран монитора.

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

3. Напишите  программу,  которая организует хранение в массиве 15 различных введённых с клавиатуры целых чисел.  Содержимое массива сортируется по убыванию. После этого, с клавиатуры запрашивается контрольное число,  наличие которого в массиве необходимо проверить. На экран монитора выводится содержимое массива до "контрольного числа"  включительно.

4. Дан  массив  из  10  целых чисел.  Отсортируйте его и найдите в нём контрольное число.  Все элементы до контрольного числа замените  на противоположные.

5. Дан массив из 20 символов.  Отсортируйте его и найдите в нём  контрольный символ.  Выведите  на  экран  содержимое  массива начиная с символа равного контрольному символу.

6. Дан массив, состоящий из 15 символов. Содержимое массива сортируется по убыванию. После этого вводится контрольное целое число в диапазоне от 0-255.  Необходимо определить наличие в массиве  символа, имеющего номер "контрольное число". В положительном случае сам символ и его индекс в массиве выводятся на экран.

7. Дан массив,  состоящий из 15 целых чисел,  в диапазоне от 0 до 255. Содержимое массива сортируется по возрастанию. После этого вводится контрольный символ.  Необходимо определить наличие в массиве числа, равного номеру контрольного символа. В положительном случае число и его индекс в массиве выводятся на экран.

8. Дан массив А состоящий из 10 символов.  Отсортируйте его по возрастанию. Организуйте массив целых чисел Б, заполнив его номерами символов из массива А.  Введите контрольное число в диапазоне от 0  до 255  и  определите его наличие в массиве Б.  В положительном случае выведите на экран найденное число и его индекс в массиве.

9. Дан массив Б состоящий из 10 чисел в диапазоне от 0 до 255.  Отсортируйте его по возрастанию. Организуйте символьный массив А, заполнив его символами с номерами элементов массива Б. Введите контрольный  символ  и  определите его наличие в массиве А.  В положительном случае выведите на экран сам символ и его индекс в массиве.

10. Дан массив А состоящий из 20 целых чисел. Отсортируйте его по убыванию.  Введите с клавиатуры 2 контрольных числа a и b.  Определите наличие в массиве чисел,  лежащих в диапазоне от a до b.  В положительном  случае  выведите найденные числа и их индексы в массиве на  экран.

11. Дан массив Б состоящий из 20 символов. Отсортируйте его по возрастанию. Введите с клавиатуры 2 контрольных символа a и b. Определите наличие в массиве символов лежащих в диапазоне от a до b. В положительном случае выведите найденные символы и их индексы на экран.

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

Лабораторная работа №4. Решение задачи сортировки

Цель: знать алгоритмы сортировок и уметь применять их при решении задач,

В большинстве случаев,  массивы применяются для хранения большого количества однотипной информации,  создания и организации баз и банков данных и т. д.  Во многих случаях номер (индекс) элемента в массиве  не играет большой роли.  Важно именно его значение, т. е. сама информация. Базы и банки данных,  в свою очередь,  необходимы не только для  того, чтобы "складывать" в них информацию,  но и для того, чтобы в любой момент была возможность удобного и быстрого доступа  к  ней.  В  обычном "неотсортированном" массиве информацию найти можно,  но только уже известным Вам способом  последовательного  перебора-просмотра  всех  его элементов,  до тех пор,  пока нужный элемент не будет обнаружен.  Этот самый простой метод обладает только одним но очень существенным недостатком - на поиск одного элемента уходит много времени.  Все остальные методы поиска информации намного эффективнее,  быстрее, но применяются только в упорядоченных, отсортированных массивах. Поэтому часто возникает задача об упорядочивании массива.

Рассмотрим простой случай такой задачи:  дан числовой массив  x1, x2,  ... xn, элементы которого попарно различны; требуется переставить элементы массива так, чтобы после перестановки они были упорядочены в порядке возрастания: x1 < x2 < ... < xn.

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

  Алгоритм сортировки выбором

Очевидно, что первое место в массиве  должен  занять  минимальный элемент массива,  второе - наименьший из всех остальных, третий - наименьший из оставшихся и т. д.