Занятие 3. Упорядочивание списка. Вставление элемента в середину списка.
Сформируем список целых чисел упорядоченный по неубыванию, т.е. каждый следующий элемент списка должен быть больше или равен предыдущему.
Для решения этой задачи рассмотрим основные части алгоритма, который мы будем воплощать в программе.
После ввода очередного числа с клавиатуры определяем его место в списке. Заметим, что при этом элемент может быть вставлен либо в начало списка, либо в конец его, либо во внутрь. Первый и второй случаи мы уже рассмотрели выше. Остановимся на третьем случае.
Для того чтобы вставить в список элемент со значением 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;
Задание. Создайте программу, формирующую упорядоченный список, вставив в нее рассмотренную выше процедуру и процедуру просмотра и вывода на экран элементов списка. Отладьте программу, добавьте комментарий, покажите учителю результат для оценки.
Дата добавления: 2015-05-16; просмотров: 931;