Есть и другая причина для сортировки списка – желание распечатать данные в удобном порядке, например, по алфавиту. Честно говоря, список – это не лучшая структура для поиска и сортировки. Для этого лучше подходят другие динамические структуры – деревья, о которых можно узнать из литературы по алгоритмам. Но сейчас мы заняты списком и будем сортировать его.
Здесь не годятся алгоритмы для массивов. Ведь в списке нет индексов, к его элементам можно добраться лишь по цепочке ссылок. Зато у списка есть другое достоинство: для перестановки элементов не надо перемещать записи в памяти, – достаточно перенацелить указатели. Это легко сделать при вводе данных из файла, – так совмещается ввод списка с его сортировкой.
Вот пример с тремя записями (на рис. 125 и рис. 126 показаны лишь номера автомобилей). Предположим, что список содержит записи с номерами 20, 30 и 40, и мы вставляем запись с номером 35. После создания переменной p^ надо найти предыдущий элемент, чтобы подцепить к нему новый. Обозначим указатель на такой элемент буквой q. Найдя элемент q (об этом чуть позже), вставку делаем на «раз и два» (рис. 125).
p^.mNext:=q^.mNext; { связываем текущий со следующим }
q^.mNext:=p; { связываем предыдущий с текущим }
Рис.125 – Состояние списка перед вставкой записи с номером 35Состояние списка после вставки элемента показано на рис. 126.
Рис.126 Состояние списка после вставки записи с номером 35Теперь рассмотрим два особых случая. Первый – когда список ещё пуст, и вставляемая запись будет первой и последней, здесь вставка делается так:
List:= p; { если список пуст, голова указывает на новую запись }
Второй случай, – когда номер в первой записи окажется больше вставляемого. Тогда новую запись вставим в начало списка.
p^.mNext:=List; { первый становится вторым }
List:=p; { а текущий- первым }
Разобрав все три возможные ситуации при вставке в сортированный список, рассмотрим поиск указателя на предыдущий элемент q. Условие поиска таково: номер в элементе q должен быть меньше вставляемого, а следующий за ним элемент должен иметь номер, больше вставляемого, а иначе элемент q будет последним в списке. Поиск начнем, как всегда, с головы.
q:= List; { Поиск места вставки начинаем с головы, здесь List<>nil }
while Assigned(q^.mNext) and (q^.mNext^.mNumber < aNumber)
do q:=q^.mNext;
Здесь выражение q^.mNext^.mNumber соответствует номеру автомобиля в следующей за q записи.
Разобрав тонкости программы «P_54_3», предъявлю её во всей красе.
{ P_54_3 – Размещение данных в сортированном списке }
type PRec = ^TRec; { Тип указатель на запись }
TRec = record { Тип записи для базы данных }
mNumber : integer; { Номер авто }
mFam : string[31]; { Фамилия владельца }
mNext : PRec; { Указатель на следующую запись }
end;
var List : PRec; { Указатель на начало списка (голова) }
{ Размещение нового элемента в сортированном списке }
procedure AddToSortList(aNumber: integer; const aFam : string);
var p, q : PRec;
begin
New(p); { Создаем динамическую переменную-запись }
{ Размещаем данные в полях записи }
p^.mNumber:= aNumber; p^.mFam:= aFam;
p^.mNext:=nil;
{ Если список пуст… }
if not Assigned(List)
then List:= p { если список пуст, голова указывает на новую запись }
else begin { если список не пуст… }
q:= List; { Поиск места вставки начинаем с головы }
{ Двигаемся по списку, пока следующий элемент существует
и его номер меньше вставляемого }
while Assigned(q^.mNext) and (q^.mNext^.mNumber < aNumber)
do q:=q^.mNext;
if q^.mNumber > aNumber then begin
{ вставка на первое место }
p^.mNext:=List; { первый становится вторым }
List:=p; { а текущий – первым }
end else begin
{ вставка в середине или в конце списка }
p^.mNext:=q^.mNext; { связываем текущий со следующим }
q^.mNext:=p; { связываем предыдущий с текущим }
end
end
end;
{ Распечатка списка }
procedure PrintList;
{--- взять из P_54_1 ---}
end;
var i: integer;
begin {--- Главная программа ---}
List:= nil; { инициализация}
{ Заполнение списка }
for i:=1 to 20 do AddToSortList(100+Random(100), 'Деточкин');
{ Распечатка списка }
PrintList;
Readln;
end.
Разумеется, что проверку этой программы я возлагаю на вас.
Поиск в сортированном спискеСоздав функцию поиска номера в сортированном списке, поставим победную точку. Будем искать запись, для которой номер в следующей за ней записи больше искомого (если следующая запись существует). Это условие совпадает с условием поиска при вставке в сортированный список. Найдя такую запись и сравнив её номер с искомым, сформируем результат: если номер найден, возвращаем указатель на эту запись, а иначе – NIL. Все это относится к программе «P_54_4».
{ P_54_4 – Поиск данных в сортированном списке }
type PRec = ^TRec; { Тип указатель на запись }
TRec = record { Тип записи для базы данных }
mNumber : integer; { Номер авто }
mFam : string[31]; { Фамилия владельца }
mNext : PRec; { Указатель на следующую запись }
end;
var List : PRec; { Указатель на начало списка (голова) }
{ Размещение нового элемента в сортированном списке }
procedure AddToSortList(aNumber: integer; const aFam : string);
{--- взять из P_54_1 ---}
end;
{ Распечатка списка }
procedure PrintList;
{--- взять из P_54_1 ---}
end;
{ Поиск в сортированном списке }
function Find(aNumber: integer): PRec;
var p : PRec;
begin
p:= List; { Поиск начинаем с головы }
{ Двигаемся по списку, пока следующий элемент существует
и его номер не больше искомого }
while Assigned(p) and Assigned(p^.mNext) and (p^.mNext^.mNumber <= aNumber)
do p:=p^.mNext;
{ Если конец списка не достигнут и номер совпадает… }
if Assigned(p) and (p^.mNumber = aNumber)
then Find:= p { то успешно! }
else Find:= nil; { а иначе не нашли }
end;
var i, N : integer; P : PRec;
begin {--- Главная программа ---}
List:= nil;
for i:=1 to 20 do AddToSortList(100+Random(100), 'Фамилия, Имя');
PrintList; { Просмотр списка }
repeat { Цикл экспериментов по поиску в списке }