Создание сортированного списка

Первое число: 5

Следующее число: 3

Следующее число: 12

Следующее число: 7

Следующее число: 0

Введено чисел: 4

Список:

3 5 7 12

Программа:

Program Sort_spisok;

Uses CRT;

Type TPoint = ^TElement;

TElement = Record

Inf: Integer;

Next: TPoint;

End;

Var head, q, r, v : TPoint;

Procedure Formir_sort_spisok;

Begin

New(head); head -указатель на голову списка

head^.Inf := 0;количество элементов в списке

head^.Next := Nil; списка еще нет

New(v); формируем первый элемент

Write(‘Первое число: ’);

ReadLn(v^.Inf);вводим его информационную часть

If (v^.Inf=0)если ввели 0,

Then Exit; то выходим из процедуры

head^.Inf := 1;в списке один элемент

v^.Next := head^.Next;вставляем его в голову списка

head^.Next := v; в head^.Next адрес первого элемента списка

New(r); r - поисковая ссылка

Repeat

New(v);формируем очередной элемент

Write(‘Очередное число: ’);

ReadLn(v^.Inf);вводим его информационную часть

If (v^.Inf=0) если ввели 0,

Then Break;то выходим из цикла ввода

head^.Inf := head^.Inf + 1;увеличиваем счетчик элементов на 1

r := head^.Next; поисковик r - на первый элементсписка

q := head; q – отстает на шаг

While (r <> Nil) Do пока не дошли до конца списка

If (r^.Inf <= v^.Inf) Then если текущий еще меньше

Begin вставляемого,

q := r; то подтягиваем q к r

r := r^.Next; и делаем шаг по списку

End

Else Break;иначе выходим из цикла поиска-место найдено

v^.Next := q^.Next; ставим новый элемент на место

q^.Next := v;

Until (v^.Inf = 0);

End;

Procedure Vyvod_spisok; процедура вывода списка

Begin

q := head^.Next;текущую ссылку – на первый элемент

While (q <> Nil) Doпока не конец списка

Begin

Write(q^.Inf:5); выводим очередной элемент

q := q^.Next; ссылку – на следующий элемент

End;

WriteLn;

End;

Begin головная программа

ClrScr;

WriteLn(‘Создание сортированного списка’);

WriteLn;

Formir_sort_spisok; обращение к процедуре создания списка

WriteLn(‘Введено чисел: ’, head^.Inf);

WriteLn(‘Список:’);

Vyvod_spisok; обращение к процедуре вывода списка

ReadLn;

End.

Бинарные деревья

Самым наглядным способом представления информации является ее представление рисунками или графиками. Поэтому при решении многих математических задач используются специальные рисунки (схемы), называемые графами.

Граф представляет собой множество точек – вершин графа, соединенных между собой отрезками – ребрами графа.

Термин граф впервые появился в работах венгерского математика Д.Кенига в 1936 году, хотя ряд задач по теории графов был решен еще Л.Эйлер в XVIII веке.

Примером графа может служить схема линии метрополитена, карта автомобильных или железных дорог. Эти дороги можно рассматривать как ребра, соединяющие города или станции – вершины такого графа.

Вершины графа обычно нумеруются или обозначаются прописными латинскими буквами: A. B, C, … Любой граф можно описать или задать перечислением вершин и ребер. Наиболее удобный способ такого задания – с помощью матрицы смежности, в которой строки и столбцы соответствуют вершинам графа, а значения элементов – длине ребер, соединяющих эти вершины. Если длина ребер не задается, то наличие ребра обозначается единицей, а его отсутствие – нулем.

Например, граф:

задается матрицей смежности:

A B C D

A

B

C

D

Как видно, это симметричная матрица.

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

Для этого ориентированного графа матрица смежности имеет вид:

A B C D

A

B

C

D

Говорят, что две вершины соединены путем, если из первой вершины можно пройти по ребрам во вторую вершину. Путей между вершинами может быть несколько, поэтому они обозначаются перечислением вершин, которые встречаются на данном пути. Например, вершины A и C графа:

соединены путями ABC, AC, ADC, AEDC, ABDC, AEDBC.

Граф называется связным, если любые две его вершины соединены некоторым путем. Если в графе можно найти замкнутый путь, то граф называется циклическим, а сам замкнутый путь – циклом.

Связный граф, в котором нет циклов, называется деревом:

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

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

Из вершины A выходят три ребра – AB, AC и AЕ, в вершину D входит одно ребро – ED. Этот же граф можно описать следующей матрицей смежности:

A B C D E

A

B

C

D

E

В незаполненных ячейках должны стоять нули – связи между соответствующими вершинами нет.

Наименование строки – это имя вершины-источника, из которой ребро выходит, а столбца – вершины-приемника, в которую входит. Таким образом, количество ненулевых элементов в матрице смежности ориентированного графа равно количеству ребер в нем.

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

Бинарное дерево – это такое ориентированное дерево, в котором:

· из каждой вершины исходит не более двух ребер,

· имеется только одна вершина – корень дерева, в которую не входит ни одного ребра,

· в каждую вершину, кроме корня, входит только одно ребро.

Бинарные деревья обычно изображаются корнем вверх:

В этом бинарном дереве вершина A является корнем.

Для ребер бинарного дерева, выходящих из одной вершины, имеются две возможности – быть направленными влево-вниз или вправо-вниз: ребро BD направлено влево-вниз, а ребро DH – вправо-вниз.

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

Узел, не являющийся корнем ни одного поддерева, называется листом. В вышеприведенном дереве листьями являются узлы G, H, K. Характеристикой каждого узла является его уровень, определяемый следующим образом: корень дерева имеет нулевой уровень, уровень любого другого узла на единицу больше уровня узла-предшественника: узлы B,C имеют уровень 1, узлы D, E, F – уровень 2, узлы G,H,K (узлы) – уровень 3.

Глубина бинарного дерева – это максимальный уровень листа дерева, что равно длине самого длинного пути от корня к листу дерева.

Среди узлов различают предков и потомков: узел A является предком для узлов B и C, узлы G и H – потомками узла D. Поэтому корень дерева – это узел, не имеющий предков, а листья – это узлы, не имеющие потомков.

Бинарные деревья – это полезная структура данных в тех случаях, когда в каждой точке вычислительного процесса должно быть принято одно решение из двух возможных (альтернатива), например, в алгоритмах сортировки, когда требуется сравнение каждого очередного элемента (числа, слова) со всеми предшествующими. Использование бинарных деревьев позволяет уменьшить количество таких сравнений: берется первый элемент и помещается в исходный узел бинарного дерева, который становится его корнем с пока пустыми левым и правым поддеревьями. Каждый последующий элемент сравнивается с элементом, стоящим в корне дерева: если новый элемент меньше его, то он образует левый узел следующего уровня, а если больше или равен – то правый. Так продолжается до тех пор, пока сортируемая последовательность элементов не закончится. При этом получается, что самый левый лист будет содержать минимальный элемент из введенной последовательности, а самый правый – максимальный. Любой левый узел будет содержать элемент, меньший, чем элемент в предшествующем узле, а правый – больший или равный элементу в предшествующем узле.

Например, следующая последовательность чисел:

14 15 4 9 7 18 3 5 16 4 20 17 9 14 5

образует бинарное дерево:

В этом дереве самый левый лист содержит наименьшее число 4, а самый правый – наибольшее 20.

Если сейчас просмотреть это дерево в так называемом симметричном порядке – слева направо: левое поддерево - его корень – правое поддерево, то получим отсортированную последовательность:

3 4 4 5 5 7 9 9 14 14 15 16 17 18 20

Бинарное дерево можно представить связным списком, в котором каждое ссылочное поле каждого элемента (узла) должно содержать значения двух ссылок – на элемент (узел) слева внизу и элемент (узел) справа внизу. Если один из узлов отсутствует, то ссылка на него равна Nil. Самые нижние элементы списка (листья) имеют ссылки со значениями Nil:

Если информационные поля элементов дерева являются данными целого типа, то дерево можно описать, например, следующим образом:

Type TRebro = ^TUzel;

TUzel = Record

Data: Integer; информационное поле

Left, Right: TRebro; ссылочные поля

End;

Var root, q, v: TRebro;

Здесь объектами типа TUzel являются записи, в которых каждое ссылочное поле Left или Right равно либо Nil, либо ссылке на конкретную ячейку памяти компьютера, отведенную для объекта типа TUzel.

Дерево можно представить в виде множества объектов типа TUzel, связанных ссылками. Сами эти объекты соответствуют узлам дерева, а ссылки – его ребрам. Если при этом поле Left (Right) некоторого узла равно Nil, то это значит, что в дереве из этого узла не исходит ребро, направленное влево-вниз (вправо-вниз). Переход от вышестоящего к нижестоящему узлу совершается, как и в связных списках, присваиванием ссылочной переменной значения ее ссылочного поля, левого или правого. Этим способом можно просмотреть все узлы дерева сверху вниз. Включение нового узла в дерево осуществляется, как и включение нового элемента в связный список, изменением значений ссылочных полей соответствующих узлов. Вместе с каждым деревом рассматривается переменная, значением которой является ссылка на корень дерева (в нашем примере это root). Если в дереве нет ни одного узла, то значение этой переменной равно Nil.

Корень дерева можно создать, например, так:

New(root);

Write(‘Первое число: ’);

ReadLn(root^.Data);

root^.Left := Nil;

root^.Right := Nil;

После этого можно вводить сортируемую последовательность: очередное введенное число сравнивается с числом, стоящим в корне, и образует левый или правый узел следующего уровня. Ссылку v будем использовать для ввода нового элемента, ссылку q (поисковик) – для поиска места в дереве для нового элемента.

Пример: создать бинарное дерево для сортировки последовательности целых чисел. Ввести несколько чисел (см. выше) – конец ввода – число 0. Вывести введенную последовательность на экран.

Интерфейс:

Первое число: 14

Очередное число: 15

Очередное число: 4

Очередное число: 9

……..

Очередное число: 0

Отсортированная последовательность:

3 4 4 5 5 7 9 9 14 14 15 16 17 18 20

Программа:

Program Bi_Tree;

Uses WinCRT;

Type TRebro = ^TUzel;

TUzel = Record

Data : Integer;

Left, Right : Rebro;

End;

Var root, q, v : TRebro;

Procedure Order(base: TRebro); процедура просмотра дерева

Begin

If (base <> Nil) Then

Begin

Order(base^.Left);

Write(base^.Data:5);

Order(base^.Right);

End;

End;

Begin

ClrScr;

New(root);

Write('Первое число: ');

ReadLn(root^.Data); первое число - в корень дерева

root^.Left:=Nil;

root^.Right:=Nil;

Repeat

Write('Очередное число: ');

New(v);

ReadLn(v^.Data);

If (v^.Data = 0) если очередное число - ноль,

Then Break; то выходим из цикла ввода

v^.Left:=Nil;

v^.Right:=Nil;

q:=Root; поисковик - в корень дерева

While (q <> Nil) Do пока не добрались до листа:

Begin

If (v^.Data < q^.Data) если введенное число меньшечисла в очередном узле

Then If (q^.Left <> Nil) и левая ссылка узла не пуста,

Then q:=q^.Left то делаем шаг влево,

Else иначе

Begin если левая ссылка узла пуста,

q^.Left:=v; то подвешиваем туда очередноечисло

Break; и выходим из цикла поиска

End;

If (v^.Data >= q^.Data) если введенное число больше илиравночислу в очередном узле

Then If (q^.Right <> Nil) и правая ссылка узла непуста,

Then q:=q^.Right то делаем шаг вправо,

Else иначе

Begin если правая ссылка узла пуста,

q^.Right:=v; то подвешиваем туда очередное число

Break; и выходим из цикла поиска

End;

End; {While}

Until (False);

WriteLn;

Writeln('Отсортированная последовательность: ');

Order(root);

WriteLn;

ReadLn;

End.