Олег Деревенец - Песни о Паскале

P:= List;

while Assigned(P) do begin

{ Здесь обрабатывается элемент списка }

P:= P^.mNext; { переход к следующему элементу }

end;

На входе в цикл указатель P загружается из головы списка. Внутри цикла, после обработки очередного элемента, переходим по указателю mNext к следующему. Напомню, что функция Assigned(P)равнозначна выражению P<>NIL. Таким образом, цикл завершится после обработки последнего элемента списка, поскольку его поле mNext содержит NIL. А если список пуст (голова содержит NIL), цикл не выполнится ни разу.

Программа «P_54_1» покажет на экране следующий результат.

30 Сидоров

20 Петров

10 Иванов

Как и следовало ожидать, порядок элементов в списке оказался обратным порядку вставки в него. Этим можно воспользоваться для построения стека, что мы и сделаем в свое время.

Углубившись в списки, мы чуть не забыли о нашем пользователе – полицейском. А ведь ему придется искать в базе данных информацию об угнанных автомобилях. Дополнив предыдущую программу функцией поиска, получим представленную ниже программу «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.

В главной программе список заполняется записями со случайными номерами автомобилей. Так же «случайно» все владельцы оказались однофамильцами (придумайте тут что-нибудь!). Далее организован цикл с запросом искомого номера, поиском и печатью результата.

Итак, мы построили список и организовали в нём поиск данных. Довольны ли мы результатом? Для начала – неплохо, но если копнуть глубже…

Войдите в положение полицейского, перед которым мелькают сотни машин. Сколько из них числятся в угоне? Мизер! Но обработка каждого автомобиля вынуждает программу пройти по всему списку, – ведь он не сортирован! А опыт показал, что там, где порядок, все ищется быстрее. Действительно, если расположить записи в порядке возрастания номеров, то просмотр списка можно прекращать при достижении номера больше искомого. При этом среднее число шагов поиска сократится вдвое.

Есть и другая причина для сортировки списка – желание распечатать данные в удобном порядке, например, по алфавиту. Честно говоря, список – это не лучшая структура для поиска и сортировки. Для этого лучше подходят другие динамические структуры – деревья, о которых можно узнать из литературы по алгоритмам. Но сейчас мы заняты списком и будем сортировать его.

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