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

Разобрав все три возможные ситуации при вставке в сортированный список, рассмотрим поиск указателя на предыдущий элемент 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;
{ Распечатка списка }