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

Рис.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.

Разумеется, что проверку этой программы я возлагаю на вас.

Поиск в сортированном списке