ТОР 5 статей: Методические подходы к анализу финансового состояния предприятия Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века Характеристика шлифовальных кругов и ее маркировка Служебные части речи. Предлог. Союз. Частицы КАТЕГОРИИ:
|
Занятие 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;
Задание. Создайте программу, формирующую упорядоченный список, вставив в нее рассмотренную выше процедуру и процедуру просмотра и вывода на экран элементов списка. Отладьте программу, добавьте комментарий, покажите учителю результат для оценки.
Не нашли, что искали? Воспользуйтесь поиском:
|