сейчас ссылка r указывает на элемент 12 , то есть r^.Inf = 12, q^.Inf = 5, и q указывает на элемент, после которого нужно вставить новый:
3. в ссылочное поле нового элемента помещается адрес, стоящий в ссылочном поле найденного элемента q (т.е. адрес следующего за ним элемента, в данном случае элемента 12):
v^.Next := q^.Next;
сейчас оба элемента (7 и 5) будут соединены с элементом 12,
4. в ссылочное поле найденного элемента 5 помещается адрес нового элемента 7:
q^.Next := v;
Пример: сформировать сортированный список из элементов 5, 3, 12, 7 и вывести его на экран (конец ввода – число 0).
Интерфейс:
Первое число: 5
Следующее число: 3
Следующее число: 12
Следующее число: 7
Следующее число: 0
Введено чисел: 4
Список:
Программа:
Type TPoint = ^TElement;
TElement = Record
Inf: Integer;
Next: TPoint;
Var head, q, r, v : TPoint;
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);
Procedure Vyvod_spisok; процедура вывода списка
q := head^.Next;текущую ссылку – на первый элемент
While (q <> Nil) Doпока не конец списка
Write(q^.Inf:5); выводим очередной элемент
q := q^.Next; ссылку – на следующий элемент
Begin головная программа
WriteLn(‘Создание сортированного списка’);
Formir_sort_spisok; обращение к процедуре создания списка
WriteLn(‘Введено чисел: ’, head^.Inf);
WriteLn(‘Список:’);
Vyvod_spisok; обращение к процедуре вывода списка
Самым наглядным способом представления информации является ее представление рисунками или графиками. Поэтому при решении многих математических задач используются специальные рисунки (схемы), называемые графами.
Граф представляет собой множество точек – вершин графа, соединенных между собой отрезками – ребрами графа.
Термин граф впервые появился в работах венгерского математика Д.Кенига в 1936 году, хотя ряд задач по теории графов был решен еще Л.Эйлер в XVIII веке.
Примером графа может служить схема линии метрополитена, карта автомобильных или железных дорог. Эти дороги можно рассматривать как ребра, соединяющие города или станции – вершины такого графа.
Вершины графа обычно нумеруются или обозначаются прописными латинскими буквами: A. B, C, … Любой граф можно описать или задать перечислением вершин и ребер. Наиболее удобный способ такого задания – с помощью матрицы смежности, в которой строки и столбцы соответствуют вершинам графа, а значения элементов – длине ребер, соединяющих эти вершины. Если длина ребер не задается, то наличие ребра обозначается единицей, а его отсутствие – нулем.
Например, граф:
задается матрицей смежности:
A B C D
A
B
C
D
Как видно, это симметричная матрица.
Граф называется ориентированным (орграф), если на каждом его ребре указано направление, то есть о каждой его вершине можно сказать, какие ребра из нее выходят, а какие входят:
Для этого ориентированного графа матрица смежности имеет вид:
