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

End.

Begin

Begin

End

Repeat

Begin

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;

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 - поисковая ссылка

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; и делаем шаг по списку

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

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

q^.Next := v;

Until (v^.Inf = 0);

End;

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

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

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

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

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

End;

WriteLn;

End;

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

ClrScr;

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

WriteLn;

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

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

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

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

ReadLn;

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

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

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

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

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

 

 

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

 

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

A B C D

 

A

B

C

D

 

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

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

 

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