Занятие 5. Упорядочивание списка. Вставление элемента в середину списка.

Сформируем список целых чисел упорядоченный по неубыванию, т.е. каждый следующий элемент списка должен быть больше или равен предыдущему.

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

После ввода очередного числа с клавиатуры определяем его место в списке. Заметим, что при этом элемент может быть вставлен либо в начало списка, либо в конец его, либо во внутрь. Первый и второй случаи мы уже рассмотрели выше. Остановимся на третьем случае.

Для того чтобы вставить в список элемент со значением 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;

Задание. Создайте программу, формирующую упорядоченный список, вставив в нее рассмотренную выше процедуру и процедуру просмотра и вывода на экран элементов списка. Отладьте программу, добавьте комментарий, покажите учителю результат для оценки.