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

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.

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

Создав функцию поиска номера в сортированном списке, поставим победную точку. Будем искать запись, для которой номер в следующей за ней записи больше искомого (если следующая запись существует). Это условие совпадает с условием поиска при вставке в сортированный список. Найдя такую запись и сравнив её номер с искомым, сформируем результат: если номер найден, возвращаем указатель на эту запись, а иначе – NIL. Все это относится к программе «P_54_4».

{ P_54_4 – Поиск данных в сортированном списке }

type PRec = ^TRec; { Тип указатель на запись }

TRec = record { Тип записи для базы данных }

mNumber : integer; { Номер авто }

mFam : string[31]; { Фамилия владельца }

mNext : PRec; { Указатель на следующую запись }

end;

var List : PRec; { Указатель на начало списка (голова) }

{ Размещение нового элемента в сортированном списке }

procedure AddToSortList(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 Assigned(p^.mNext) and (p^.mNext^.mNumber <= aNumber)

do p:=p^.mNext;

{ Если конец списка не достигнут и номер совпадает… }

if Assigned(p) and (p^.mNumber = aNumber)

then Find:= p { то успешно! }

else Find:= nil; { а иначе не нашли }

end;

var i, N : integer; P : PRec;

begin {--- Главная программа ---}

List:= nil;

for i:=1 to 20 do AddToSortList(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.

• Указатель на любой тип данных можно объявлять раньше типа, на который он ссылается.

• Односвязный список – это простейшая динамическая структура, отводящая под данные столько памяти, сколько им требуется.

• Элементы списка – это записи, содержащие в числе прочих данных указатель на следующую запись в списке.

• Элементы списка помещают в кучу и связывают между собой внедренными в них указателями.

• Первый элемент доступен через голову списка (указатель в статической памяти программы). Остальные элементы доступны по цепочке указателей, встроенных в записи.

• Сортировку списка можно совместить с его вводом.

А) Напишите функцию для подсчета элементов списка; она должна принимать указатель на голову списка, а возвращать целое число.

Б) Начертите блок-схему вставки записи в сортированный список.

В) Напишите процедуру для удаления первого элемента списка. Или слабо?

Г) Напишите процедуру сортировки уже готового списка. Подсказка: последовательно извлекайте элементы из несортированного списка и вставляйте в сортированный (потребуется две головы для двух списков).

Задачи на темы предыдущих глав

Д) В задаче 53-Г была представлена модель «глупого» винчестера. «Умный» винчестер отличается организацией внутренней очереди и челночным движением головки, которая следует попеременно то от внутренней дорожки к внешней, то обратно, попутно выполняя все накопившиеся в очереди запросы. Направление движения переключается, когда в текущем направлении не остается запросов, поэтому головка редко достигает крайних дорожек.