Чтение онлайн

{ Размещаем данные в полях записи }

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

Ваша программа должна подсчитать общее время обработки запросов «умным» контроллером для набора данных из входного файла, составленного по правилам для задачи 53-Г. Создайте несколько наборов таких данных и сравните время их обработки двумя типами контроллеров: «умным» и «глупым».