Бинарные деревья
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
Как видно, это симметричная матрица.
Граф называется ориентированным (орграф), если на каждом его ребре указано направление, то есть о каждой его вершине можно сказать, какие ребра из нее выходят, а какие входят:
Для этого ориентированного графа матрица смежности имеет вид: