Углубившись в списки, мы чуть не забыли о нашем пользователе – полицейском. А ведь ему придется искать в базе данных информацию об угнанных автомобилях. Дополнив предыдущую программу функцией поиска, получим представленную ниже программу «P_54_2». Для экономии бумаги я не показал здесь процедуры вставки и распечатки списка.
{ P_54_2 – Размещение и поиск данных в несортированном списке }
type PRec = ^TRec; { Тип указатель на запись }
TRec = record { Тип записи для базы данных }
mNumber : integer; { Номер авто }
mFam : string[31]; { Фамилия владельца }
mNext : PRec; { Указатель на следующую запись }
end;
var List : PRec; { Указатель на начало списка (голова) }
procedure AddToList(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 (P^.mNumber <> aNumber) do p:= p^.mNext;
Find:= p; { результат поиска }
end;
var i, N : integer; P : PRec;
begin {--- Главная программа ---}
List:= nil;
{ Заполним список случайными значениями номеров }
for i:=1 to 20 do AddToList(100+Random(100), 'Деточкин');
PrintList; { Распечатка списка }
repeat { Цикл попыток поиска в списке }
Write('Укажите номер авто = '); Readln(N);
if N>0 then begin
P:= Find(N);
if Assigned(P)
then Writeln(P^.mNumber, '':3, P^.mFam)
else Writeln ('Не найдено!');
end;
until N=0
end.
Простенькая функция Find ищет в списке элемент с нужным номером автомобиля, и возвращает указатель на этот элемент списка. При неудачном исходе функция возвращает NIL.
В главной программе список заполняется записями со случайными номерами автомобилей. Так же «случайно» все владельцы оказались однофамильцами (придумайте тут что-нибудь!). Далее организован цикл с запросом искомого номера, поиском и печатью результата.
Сортированные списки
Итак, мы построили список и организовали в нём поиск данных. Довольны ли мы результатом? Для начала – неплохо, но если копнуть глубже…
Войдите в положение полицейского, перед которым мелькают сотни машин. Сколько из них числятся в угоне? Мизер! Но обработка каждого автомобиля вынуждает программу пройти по всему списку, – ведь он не сортирован! А опыт показал, что там, где порядок, все ищется быстрее. Действительно, если расположить записи в порядке возрастания номеров, то просмотр списка можно прекращать при достижении номера больше искомого. При этом среднее число шагов поиска сократится вдвое.
Есть и другая причина для сортировки списка – желание распечатать данные в удобном порядке, например, по алфавиту. Честно говоря, список – это не лучшая структура для поиска и сортировки. Для этого лучше подходят другие динамические структуры – деревья, о которых можно узнать из литературы по алгоритмам. Но сейчас мы заняты списком и будем сортировать его.
Здесь не годятся алгоритмы для массивов. Ведь в списке нет индексов, к его элементам можно добраться лишь по цепочке ссылок. Зато у списка есть другое достоинство: для перестановки элементов не надо перемещать записи в памяти, – достаточно перенацелить указатели. Это легко сделать при вводе данных из файла, – так совмещается ввод списка с его сортировкой.
Вот пример с тремя записями (на рис. 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; { первый становится вторым }
