Песни о Паскале

      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;       { а текущий- первым }