Курсовая работа: Анализ алгоритмов нечисленной обработки данных
Шаг 3. Запись каждого элемента в текстовый файл F_1 после считывания.
Шаг 4. Массив формируется с помощью датчика случайных чисел также в цикле с параметром i : for i:=1 to n do
A[i]:=random(1000);
Шаг 5. Запись сформированного массива в текстовый файл F_1, элементы которого располагаются в четырёх позициях.
Процедура Vivod выводит на экран сформированный неупорядоченный массив.
3.2 Линейный поиск
Схема алгоритма линейного поиска приведена в приложении В. Алгоритм реализован в виде процедуры Lin_Poisk (приложение Б).
Шаг 1. Установить счетчик количества сравнений в 0: k:=0.
Шаг 2. Последовательное сравнение элементов исходного массива с заданным элементом x в цикле с параметром i.
Шаг 3. Элемент массива равен искомому элементу: a[i]=x, то счетчику присваивается индекс искомого элемента: k:=i, а также осуществляется выход из цикла с помощью процедуры break;
Шаг 4. Если k≠0, тогда шаг 5, иначе шаг 6.
Шаг 5. Вывод на экран сообщения Writeln (‘Element naiden. Sravnenii-‘,k).
Шаг 6.Вывод на экран сообщения Writeln (‘Element ne naiden’).
3.3 Построение двоичного дерева
Процедура Tree представляет исходный массив A в виде дерева B. Формирование двоичного дерева выполняется следующим образом:
Шаг 1. Обнуляются поля первого элемента, содержащего левый, правый и обратный указатели b[1,3]:=0; b[1,4]:=0; b[1,5]:=0.
Шаг 2. Записываются элементы массива в получаемое дерево. В дереве b заполняются первые 2 поля – поле значения и признака. Первый элемент является корнем дерева
Шаг 3. Цикл организации двоичного дерева. Для каждого элемента массива (дерева), начиная со второго, необходимо выполнять следующие действия:
Шаг 3.1. Просмотр начинается со сравнения i-го элемента с корнем дерева, т.е. индекс k устанавливается в единицу k:=1.
Шаг 3.2. Сравнение: если i-й элемент массива меньше корня дерева, тогда его необходимо записать в левую ветвь j:=3, иначе – в правую ветвь j:=4.
Шаг 3.3. Проверка: если у k-го элемента есть левый или правый потомок, то переход на Шаг 3.4, иначе – переход на Шаг 3.5.
Шаг 3.4. За индекс k необходимо взять значение переменной s, которое содержит указатель правого или левого потомка k-го элемента и переход на Шаг 3.2.
Шаг 3.5. В поле указателя левого или правого потомка k-го элемента записывается значение индекса i. Поля i-го элемента, содержащие указатели левого, правого потомков и предка, обнуляются.
Данный алгоритм реализован в виде процедуры Tree (Приложение Б). Схема алгоритма процедуры Tree представлена в Приложении В.
3.4 Сортировка двоичным деревом
Идея сортировки деревом заключается в следующем. Если у элемента есть левая ветвь, то элемент с наименьшим значением признака надо искать на этой ветви. Если у элемента левой ветви нет, то он должен быть перенесён в результирующий массив b1. После этого очередной элемент разыскивается в правой ветви, если она есть, или возвращается по обратному указателю. После возвращения к какому-либо элементу по левой или правой ветви дальнейшие действия идут так, как будто у этого элемента соответствующей ветви нет. И так до тех пор, пока все элементы исходного массива, образующие двоичное дерево, не будут упорядочены по возрастанию.
Алгоритм сортировки деревом приведен ниже:
Шаг 1. Записываются элементы исходного массива (дерева) в результирующий массив (сортируемое дерево). Просмотр дерева начинается с первого элемента i:=1. Устанавливается счетчик, индекс для просмотра сортируемого дерева k:=0.
Шаг 2. Проверяется i-й элемент массива (дерева) на наличие левого потомка. Если он имеется, то за i-й элемент берется левый потомок и повторяется Шаг 2. Увеличивается счетчик количества перестановок m:=m+1.