Сформируем список целых чисел упорядоченный по неубыванию, т.е. каждый следующий элемент списка должен быть больше или равен предыдущему.
Для решения этой задачи рассмотрим основные части алгоритма, который мы будем воплощать в программе.
После ввода очередного числа с клавиатуры определяем его место в списке. Заметим, что при этом элемент может быть вставлен либо в начало списка, либо в конец его, либо во внутрь. Первый и второй случаи мы уже рассмотрели выше. Остановимся на третьем случае.
Для того чтобы вставить в список элемент со значением Digit между двумя элементами, нужно найти эти элементы и запомнить их адреса (первый адрес – в переменной dx, второй – в рх), после чего установить новые связи с переменной, в которой хранится значение Digit.
Графически это можно представить так:
Операторы, выполняющие данную задачу будут следующими:
New(x);
x^.Data:= Digit;
px^.Next:= x;
x^.Next:= dx;
Приведем процедуру InsInto, которая ищет место в списке и вставляет элемент, переданный ей как параметр. В результате сразу получается упорядоченный список. Адрес первого элемента списка хранится в глобальной переменной Head.
|
|
Procedure InsInto(Digit: integer; Var Head: Ukazatel);
Var
dx, px, x: Ukazatel;
Begin
New(x);
x^.Data:= Digit;
x^.Next:= Nil;
if Head = Nil
then {Если список пуст, то вставляем первый элемент}
Head:= x
else
{Если список не пуст, то просматриваем его до тех пор, пока не отыщется подходящее место для x^ или не закончится список}
Begin
dx:= Head;
px:= Head;
while (px<>Nil) and (px^.Data<=Digit) do
Begin
dx:= px;
px:=px^.Next;
End;
if px=Nil
then {Пройден весь список}
dx^.Next:= x {Элемент добавляется в конец списка}
else {Пройден не весь список}
Begin
x^.Next:= px;
if px=Head
then
Head:= x {Вставляем в начало списка}
else
dx^.Next:= x; {Вставляем внутрь списка}
End;
End;
End;
Задание. Создайте программу, формирующую упорядоченный список, вставив в нее рассмотренную выше процедуру и процедуру просмотра и вывода на экран элементов списка. Отладьте программу, добавьте комментарий, покажите учителю результат для оценки.