Песни о Паскале (СИ)

Текст добавлен: 6 ноября 2017, 03:30

Текст книги "Песни о Паскале (СИ)"

Автор книги: Олег Деревенец

Жанр:

Драматургия

сообщить о нарушении

Текущая страница: 21 (всего у книги 29 страниц)

Назад к карточке книги

begin

New(York); { выделено два байта из кучи, адрес в переменной York }

York^:=123;

Writeln(York^); { 123 }

end.

Здесь объявлен указатель на целое число по имени York. При выполнении процедуры New(York) из кучи выделяется 2 байта (для целого числа), и адрес этого кусочка попадает в указатель York. Чтобы воспользоваться выделенным участком как обычной переменной, указатель разыменовывают.

Спрашивается: откуда операционная система узнает объём запрашиваемой памяти (в данном случае 2 байта)? Об этом ей тихонько сообщит компилятор, которому известны размеры всех типов данных.

Освобождение памяти

Поработав с выделенным участком памяти, со временем вы можете отказаться от него – за ненадобностью. Тогда следует освободить его и вернуть в кучу, – как ни велика память, она не беспредельна, а брать взаймы ещё придется.

Освобождение кусочка памяти выполняется процедурой Dispose – «освободить». Ей, как и процедуре выделения памяти, нужен лишь один параметр – указатель на ранее выделенный участок памяти. Обратимся снова к примеру.

var ps : ^string; { указатель на строку }

begin

New(ps); { выделено 256 байтов из кучи }

ps^:=’Hello !’;

Writeln(ps^); { Hello ! }

Dispose(ps); { возвращено в кучу 256 байтов }

end.

Здесь мы получили из кучи 256 байтов под строковую переменную, – вполне приличный кусок. А после – за ненадобностью – освободили эту память.

Переменные, порождаемые и исчезающие по мановению волшебника-программиста, называют динамическими. Но исполняет повеления программиста операционная система, – только она вправе хозяйничать в куче. Получив запрос на выделение памяти через процедуру New, система сообщит программе адрес выделенного участка и отметит его у себя как занятый. Теперь никто не посягнет на него, пока программа не освободит участок процедурой Dispose, или не завершится. По завершении программы все занятые ею участки памяти освобождаются системой автоматически.

Доступ к динамическим переменным возможен лишь через указатели, а они размещаются в секции данных или в стеке. Такие переменные (в обычном понимании, то есть с именами) называют статическими, поскольку их положение в памяти не изменяется, то есть, статично. В приведенных выше примерах статические указатели ссылались на динамические переменные.

Предупреждён – значит, вооружен

Работа с динамическими переменными таит ряд тонкостей, к ним надо привыкнуть, впитать в себя. Рассмотрим типичные ошибки.

Не инициализированный указатель

var ps : ^string;

begin

ps^:=’Hello !’; { В указателе мусор – нельзя обращаться через него }

end.

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

Обращение через пустой указатель

var ps : ^string;

begin

ps := nil;

ps^:=’Hello !’; { Указатель пуст – нельзя обращаться через него }

end.

Урок предыдущего примера справедлив и здесь: обращение к памяти через пустой указатель тоже вызовет крах программы.

Обращение к уничтоженной переменной (висячие ссылки)

var ps : ^string;

begin

New(ps); ps^:=’Hello !’; { Это нормально }

Dispose(ps);

ps^:=’Bye !’; { Здесь ошибка, – переменной уже нет! }

end.

После освобождения памяти, занимаемой динамической переменной, обращаться к ней уже нельзя. Вот другой пример такой ошибки:

var p1, p2 : ^string;

begin

New(p1);

p2 := p1; { адрес динамической переменной копируется в другой указатель }

Dispose(p2); { Переменная освобождается через указатель p2 }

p1^:=’Hello !’; { Это ошибка, – переменной уже нет! }

Dispose(p1); { Это тоже ошибка ! }

end.

Здесь все тоньше. Динамическая переменная создана через один указатель, и её адрес скопирован в другой. Теперь можно обращаться к переменной и освобождать её через любой из них. Но после освобождения все ссылки на переменную теряют силу! Обратиться к ней, или повторно освободить уже нельзя!

Утечка памяти

Эта ошибка преследует даже опытных программистов. Её трудно заметить, поскольку расплата наступает после исчерпания всей памяти, а этого можно и не дождаться. В действительности никакой утечки памяти не происходит, правильней назвать это захламлением памяти или потерей ссылки на переменную. Итак, смотрим:

var p1, p2 : ^string;

begin

New(p1); New(p2); { создаем две динамические переменные }

p2 := p1; { адрес первой переменной копируется во второй указатель }

Dispose(p1); { Первую переменную освободить можно… }

Dispose(p2); { … а вторую – уже нельзя! }

end.

Здесь вторая переменная существует и после того, как указатель p2 переключился на первую. Но связь с нею потеряна навсегда, эту переменную нельзя даже освободить! Так объём свободной памяти в куче уменьшается, что и породило выражение «утечка памяти».

К счастью, после завершения программы операционная система сама освободит всю занятую программой память, включая потерянные участки. Не тревожьтесь – память вашего компьютера не пострадает!

В последующих главах мы построим несколько «боевых» программ с применением динамических переменных.

Итоги

• В задачах, где нельзя предсказать объём обрабатываемых данных, используют динамические переменные.

• Память для динамических переменных выделяется из кучи – области свободной памяти, которой «заведует» операционная система.

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

• Для выделения памяти вызывают процедуру New, она помещает в указатель адрес созданной переменной.

• Когда надобность в динамической переменной отпадает, занятую ею память освобождают процедурой Dispose.

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

А слабо?

А) Сравните размеры переменных и указателей на них, воспользуйтесь для этого следующей программкой. Напишите нечто подобное для переменных других типов.

type pb = ^byte; pw = ^word; pe = ^extended;

var b : byte; w : word; e : extended;

begin

Writeln(SizeOf(b):5, SizeOf(pb):5);

Writeln(SizeOf(w):5, SizeOf(pw):5);

Writeln(SizeOf(e):5, SizeOf(pe):5);

Readln;

end.

Б) Найдите ошибки в следующей программе и объясните их.

var p1, p2 : ^integer;

begin

p1 := 10;

p2^:= 20;

New(p1);

p2:= p1;

p1^:= 'Привет!';

Dispose(p1);

Dispose(p2);

end.

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

В) Ник обожал музыку. Но компьютерный музыкальный проигрыватель раздражал программиста, поскольку при случайном выборе мелодий повторял одни песни, напрочь забывая о других. Предположим, в списке 10 песен, но звучали только три из них: 3, 6, 5, 6, 3, 6, 5 и т.д.

Ник создал «справедливый» проигрыватель, выбирающий мелодии иначе. Все песни состояли в одном из двух списков: «белом» или «черном». Изначально все они были в «белом» списке, и очередная мелодия выбиралась из него случайно, а после проигрывания ставилась в конец «черного». Если в этот момент в «черном» списке состояла половина мелодий, то первая мелодия из «черного» списка возвращалась в «белый». Затем снова случайно выбиралась мелодия из «белого» списка. Так гарантировалось отсутствие повторов ранее проигранных песен в течение достаточно длительного времени. Создайте программу, генерирующую случайные числа (мелодии) в диапазоне от 1 до N представленным выше методом. Значение N не превышает 255.

Г) Распечатывая числовое множество, мы выводили все его элементы по одному, не заботясь об экономии бумаги или места на экране. Напишите экономную процедуру печати множества, учитывающую подряд идущие диапазоны чисел. Вот примеры желаемой распечатки:

1,5..255

0..200,210..255

0..255

2,5,7,10..20,30..40

Глава 53

Массив указателей

Мы научились создавать переменные по мере надобности – динамически. Эти переменные поселяются в куче, но доступны через указатели, что расположены в секции данных или в стеке – статической памяти программы. Взглянете на рис. 118, где каждая клеточка соответствует байту.

Рис.118 – Указатели на динамические переменные

Очевидно, что размещая в куче мелкие переменные, никакой экономии статической памяти не получишь. Но чем крупнее переменная, тем выгоднее выселять её в кучу. Эта идея лежит в основе следующей переделки полицейской базы данных.

Базу данных – в кучу

Последние улучшения полицейской базы данных связаны с её сортировкой и быстрым двоичным поиском. Вдобавок мы выяснили, что номер автомобиля – не единственное, что нужно полицейским. Хорошо бы держать в базе данных фамилию владельца, его адрес, телефон и прочее. Все это можно связать с номером автомобиля в структурном типе данных – записи.

type TRec = record { структура записи о владельце автомобиля }

mNum : integer; { номер авто – 2 байта }

mFam : string[31]; { фамилия владельца – 32 байта }

mAddr: string[63]; { адрес – 64 байта }

mTel : integer; { телефон – 2 байта }

end;

Для экономии памяти отведем под фамилию и адрес укороченные строки: 31 байт – для фамилии и 63 – для адреса. Легко посчитать, что для размещения такой записи потребуется: 2+32+64+2 = 100 байтов (размер строки на единицу больше объявленной длины, вы помните об этом?).

Объявим массив из тысячи таких записей (на первое время хватит).

type TBase = array [1..1000] of TRec;

И посчитаем размер массива, он составит 100 x 1000 = 100000 байтов. Ого! Сто тысяч, – это больше, чем могут позволить вам иные компиляторы (Borland Pascal, например). Но если такой массив и поместится в памяти, немалая его часть по понятным причинам будет пустовать.

А если разместить эти увесистые записи в куче? Тогда в статической памяти останется лишь массив указателей на эти переменные, который займет в памяти 4 x 1000 = 4000 байтов, что вполне приемлемо. А куча? Её вместимость сопоставима с объёмом памяти компьютера и исчисляется мегабайтами. Так мы убьем двух зайцев: сэкономим статическую память программы и выйдем за ограничения, налагаемые компилятором. Рис. 119 поясняет нашу задумку.

Рис.119 – Массив указателей на переменные в куче

Кстати, вы заметили какой-либо порядок записей в куче? Переменные разбросаны там и сям без всякой системы. Кучей, как вы помните, заведует операционная система, и требовать какого-то порядка от неё неуместно.

Итак, исполняя задуманное, учредим ещё один тип данных – указатель на запись.

type PRec = ^TRec;

Тогда база данных в статической памяти представится массивом.

type TBase = array [1..1000] of PRec;

Уловив идею будущей программы, приступим к деталям. План дальнейших действий таков. Сначала создадим вспомогательную программу с двумя процедурами: одна из них – для ввода базы данных из текста в кучу, а другая – для распечатки этой базы. Эта программа будет фундаментом для следующей, где добавим процедуру сортировки записей.

Как обычно, данные будем вводить из текстового файла. Каждая его строка содержит номер автомобиля и фамилию владельца (прочие данные вы добавите позднее). Вот пример входного файла, где номер автомобиля и фамилия разделяются несколькими пробелами.

6723 Иванов

2199 Петров

Первый вариант программы «P_53_1» перед вами, рассмотрим его.

{ P_53_1 – Ввод и вывод полицейской базы данных }

const CSize = 1000; { Емкость базы данных }

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

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

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

end;

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

TBase = array[1..CSize] of PRec; { Тип массив указателей }

var DataBase : TBase; { База данных – это массив указателей }

Count: integer; { Фактическое количество записей в базе }

{ Чтение данных из текстового файла в базу данных }

function ReadData(var F : text): integer;

var N : integer; { номер авто }

S : string; { фамилия }

P : PRec; { временный указатель на запись }

i : integer; { счетчик записей }

begin

Reset(F); i:=0;

while not Eof(F) and (i

Inc(i); { i+1 }

{ Читаем строку с номером и фамилией }

Read(F, N); Readln(F, S);

{ Удаляем пробелы в начале строки с фамилией }

while (S[1]=' ') do Delete(S,1,1);

New(P); { Создаем новую запись в куче }

{ Заполняем поля записи }

P^.mNumber := N; P^.mFam := S;

{ Указатель на запись помещаем в массив }

DataBase[i]:= P;

end;

Close(F); ReadData:= i;

end;

procedure ExpoDataBase; { Распечатка базы данных }

var i : integer;

begin

i:=1;

{ Пока индекс в пределах массива и указатель не пуст }

while (i<=CSize) and Assigned(DataBase[i]) do begin

{ Печатаем номер, четыре пробела и фамилию }

Writeln(DataBase[i]^.mNumber :6, '':4, DataBase[i]^.mFam);

Inc(i); { i+1 }

end;

var F : text; i : integer;

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

for i:= 1 to CSize do DataBase[i]:= nil;

Assign(F,'P_50_1.in');

Count:= ReadData(F);

Writeln ('Всего записей: ',Count);

ExpoDataBase; Readln;

end.

Типы данных объявлены так, как уговорено выше. Предельный размер базы данных задан константой CSize=1000.

Функция ReadData читает строки текстового файла и помещает данные в кучу. После ввода номера автомобиля оператором Read(F,N) указатель чтения в файле остановится на первом пробеле за числом. Следующий оператор Readln(F,S) дочитает остаток строки. Так в переменной S окажется фамилия с пробелами в начале строки, – они потом удаляются.

Последующие операторы внутри функции ReadData создают динамическую переменную (запись), адрес которой содержится в указателе P. Затем поля записи заполняем номером автомобиля и фамилией владельца, после чего указатель P копируем в очередной элемент массива указателей. Эти действия можно записать короче – без вспомогательного указателя P, вот так:

New(DataBase[i]); { создаем переменную-запись, указатель в массиве }

DataBase[i]^.mNumber := N; { копируем номер }

DataBase[i]^.mFam := S; { и фамилию }

Но при пошаговой отладке удобнее пользоваться промежуточными переменными, что мы и сделали.

Теперь обратимся к процедуре ExpoDataBase – она распечатывает данные, размещенные в куче. Выражение Assigned(DataBase[i]) в условии цикла WHILE равнозначно выражению DataBase[i]<>NIL и проверяет, ссылается ли указатель на динамическую переменную. Такая проверка исключает ошибку обращения через пустой указатель.

В главной программе заслуживает внимание строка, заполняющая пустым значением NIL все указатели массива. Ведь пока динамические переменные не созданы, указатели на них следует «заглушить» константой NIL.

for i:= 1 to CSize do DataBase[i]:= nil;

То же самое делается проще и быстрее процедурой FillChar.

FillChar(DataBase, SizeOf(DataBase), 0);

Но указатели – не обычные числа, возможно ли заполнять их нулями? Здесь проявляется универсальность процедуры FillChar, которая способна работать с данными любого типа. А ноль как раз и соответствует внутреннему представлению константы NIL.

Прежде, чем двинуться дальше, подготовьте файл с исходными данными и хорошенько проверьте работу программы «P_53_1».

Сортировка массива указателей

Переходим ко второму этапу, где мы добавим процедуру сортировки массива указателей. Напомню, что в сортированном массиве работает быстрый двоичный поиск, – этим и привлекает нас сортировка. Вот программа «P_53_2», где процедуры чтения и распечатки базы данных пропущены, – их следует взять из программы «P_53_1».

{ P_53_2 – Сортировка полицейской базы данных }

const CSize = 1000; { Максимальное количество записей в базе данных }

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

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

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

end;

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

TBase = array[1..CSize] of PRec; { Тип массив указателей }

var DataBase : TBase; { База данных – это массив указателей }

Count: integer; { Количество записей в базе }

{ Чтение данных из файла БД }

function ReadData(var F : text): integer;

{ Взять из P_53_1 }

end;

{ Распечатка БД }

procedure ExpoDataBase;

{ Взять из P_53_1 }

end;

{ FarmSort – "Фермерская" сортировка }

procedure FarmSort(var arg: TBase; Right : integer);

var L, R : Integer; T : PRec;

begin

for L := 1 to Right-1 do

{ Сдвигаем правый индекс влево }

for R := Right downto L+1 do begin

{ Если левый элемент оказался больше правого,

то меняем элементы местами }

if arg[L]^.mNumber > arg[R]^.mNumber then begin

{ Перестановка элементов массива }

T:= arg[L]; arg[L]:= arg[R]; arg[R]:= T;

end;

var F : text;

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

FillChar(DataBase, SizeOf(DataBase), 0);

Assign(F,'P_53_1.in');

Count:= ReadData(F); { Ввод данных и подсчет числа записей }

Writeln('До сортировки: ');

ExpoDataBase; Readln;

FarmSort(DataBase, Count); { Сортировка }

Writeln('После сортировки: ');

ExpoDataBase; Readln;

end.

Теперь направим внимание на процедуру сортировки. Для простоты я взял «фермерскую» сортировку – не самый быстрый алгоритм (смотрите главу 43). Отличия нынешнего варианта сортировки от первого невелики, их всего два.

Во-первых, сортируются не записи, а указатели на них. В 49-й главе нам довелось сортировать массив записей (помните футбольный чемпионат?), теперь сравним то решение с этим. Сортировка массива перемещает его элементы. Чем крупнее элемент, тем больше байтов передвигается. Очевидно, что четыре байта указателя двигаются быстрее, чем сотня байтов записи.

Здесь приходит на ум почтальон с пачкой открыток. Если открытки в пачке сложены случайно, почтальон станет бестолково бегать от дома к дому. Для ускорения дела надо что-то отсортировать: то ли дома в порядке сложенных открыток, то ли открытки по номерам домов. Как поступит почтальон? – догадайтесь сами. В нашем случае дома – это записи, а открытки – указатели на них.

Вторая особенность сортировки указателей в том, что обрабатывается не весь массив, а лишь непустые указатели. Обращаться к данным через пустые указатели недопустимо, – это верный способ «уронить» программу. Поэтому в процедуру передается граница сортируемой части через параметр Right – это правый индекс массива, равный фактическому количеству элементов в базе данных.

Итоги

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

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

• Сортировка массива указателей похожа на сортировку других типов данных, но выполняется, как правило, быстрее. При этом сортируют лишь непустые указатели.

А слабо?

А) Дополните запись TRec полями с адресом владельца и его телефоном. Организуйте ввод и вывод этих данных (наряду с другими). Подготовьте надлежащий текстовый файл с исходными данными и проверьте работу этой версии программы.

Б) Напишите процедуру линейного поиска номера автомобиля в несортированном массиве указателей.

В) Напишите процедуру быстрого двоичного поиска в сортированном массиве указателей. Дополните вывод найденных данных, включая фамилию владельца и прочее.

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

Г) «Глупый» винчестер (об «умном» вы узнаете в задаче 54-Д). Рассмотрим очень упрощенную модель винчестера, «шустрость» которого в значительной степени определяется частотой вращения диска и скоростью перемещения головки чтения-записи. Время одного оборота диска примем за единицу – квант. За это время головка полностью читает или записывает одну дорожку. Количество дорожек на диске – 256, а нумерация идет с нуля (0…255). Время, необходимое для перемещения головки на соседнюю дорожку, тоже примем равным одному кванту.

Винчестером управляет контроллер, работающий куда быстрее механических узлов – диска и головки, поэтому издержками времени на его работу пренебрежем. Через некоторый интервал времени (таймаут) контроллер просматривает входную очередь, содержащую запросы на чтение или запись дорожек. Эта очередь формируется всеми запущенными программами. У нас это будет текстовый файл, каждая строка которого содержит по несколько чисел в диапазоне от 0 до 255 – это номера запрашиваемых дорожек. Пустая строка говорит об отсутствии запросов в текущий момент времени. Для первой строки файла сделаем исключение, поместив там лишь одно число – период (таймаут) просмотра этой очереди контроллером в квантах.

Контроллер «рулит» так. Прочитав список запросов (очередную строку файла), он перемещает их в свою внутреннюю очередь и далее обрабатывает её в порядке прихода запросов: смещает головку в нужную позицию и выполняет чтение-запись. Одновременно он следит за таймаутом, и, по истечении оного, читает следующую порцию входной очереди (то есть, строку файла). Ваша программа должна подсчитать общее время обработки запросов, заданных во входном файле (время измеряется в квантах).

Глава 54

Односвязные списки

Создав массив указателей на динамические переменные, мы сбросили в кучу уйму данных. Результат неплох, но где пределы совершенству? Как ни крути, размер массива ограничен, сколько указателей нам запасти? Побольше? Но тогда значительная часть массива будет пустовать. Одним словом, постоянный размер массива вяжет нас. Идеальное решение в том, чтобы отвести под данные столько памяти, сколько им требуется, – не больше и не меньше. Мы стремимся к этому решению и сейчас в шаге от цели.

Чудесное сочетание

Ключ к безупречному решению – в сочетании записи с указателем. Запись может содержать в своей обёртке разнородные элементы: числа, символы, строки, массивы и так далее. А если внедрить в неё указатель на другую запись этого же типа? Тогда мы сможем погрузить в кучу цепочку элементов так, как показано на рис. 120.

Рис.120 – Связывание записей указателями

Здесь в кучу погружены три элемента данных (три записи), а в статической памяти программы торчит лишь «поплавок» – указатель на первый элемент этой цепочки. Все последующие записи сцеплены друг с другом указателями, встроенными в них же. Последняя запись содержит NIL, – как говорится, сколько веревочке не виться… Наряду с указателями, записи содержат, разумеется, и данные, необходимые для решаемой задачи. Такую структуру называют односвязным списком. Односвязным, – потому что элементы сцеплены лишь одной связью (при желании таких связей можно сделать больше). Мы будем называть эту динамическую структуру просто списком, по-английски – List.

В отличие от массива, где любой элемент доступен по индексу, в списке все иначе. Поскольку указатели ведут в одном направлении, то возможен лишь последовательный доступ к элементам. Начав движение с головы списка, мы достигнем первого элемента. Затем по указателю, хранящемуся в нём, перескочим на второй элемент, со второго – на третий и так далее, пока не найдем нужный элемент или не уткнемся в конец списка.

Проблема курицы и яйца

Построим элемент односвязного списка для полицейской базы данных. Вот объявления нужных нам типов данных: записи и указателя на неё.

type

PRec = ^TRec; { Указатель на запись, – здесь TRec ещё не объявлен! }

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

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

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

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

end;

Тип TRec содержит, наряду с полезными полями mNumber и mFam, ещё одно служебное поле – указатель на следующую запись mNext (Next – «следующий»).

Друзья мои, обратите внимание на выделенную строку, где нарушено важнейшее правило Паскаля! Вы знаете, что любой объект программы объявляют до его применения. Внутри записи объявлен указатель на неё же – поле mNext. Поэтому тип этого указателя PRec надо объявить раньше типа записи TRec, что и сделано в первой строке. Однако в этой первой строке применён тип записи TRec, который объявлен ниже! Круг замкнулся, как в задаче о курице и яйце, – что появилось раньше?

К счастью, в Паскале эта задача решена: указатель на любой тип данных можно объявлять раньше того типа, на который он ссылается. Это единственное исключение из правила. Значит, представленное выше объявление типов вполне законно.

Вяжем список

Возьмемся за постройку списка для полицейской БД. Начнем с простого: вставим в список несколько элементов данных с номерами автомобилей и фамилиями владельцев, а затем распечатаем список. Это делает программа «P_54_1», рассмотрим её.

{ P_54_1 – Размещение данных в несортированном списке }

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

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

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

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

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

end;

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

{ Добавление в список записи об автомобиле }

procedure AddToList(aNumber: integer; const aFam : string);

var P : PRec;

begin

New(P); { Создаем динамическую переменную-запись }

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

P^.mNumber:= aNumber; P^.mFam:= aFam;

P^.mNext:= List; { Цепляем предыдущую запись к новой записи }

List:= P; { Теперь голова указывает на новую запись }

end;

{ Распечатка списка }

procedure PrintList;

var P : PRec;

begin

P:= List;

while Assigned(P) do begin

Writeln(P^.mNumber, '':3, P^.mFam);

P:= P^.mNext;

end;

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

List:= nil;

AddToList(10, 'Иванов');

AddToList(20, 'Петров');

AddToList(30, 'Сидоров');

PrintList;

Readln;

end.

Основу программы составляют процедуры вставки в список и его распечатки. В процедуре AddToList – добавить в список – первые строки вам знакомы: после создания динамической переменной P^ данные копируются в её поля. Обратите внимание на то, что указатель P – это локальная переменная, которая исчезнет после выхода из процедуры. И тогда, если не сохранить этот указатель, адрес новой переменной будет утерян, что приведет к утечке памяти. Поэтому после создания новой переменной P^ адрес из головы списка List копируется в поле mNext вновь созданной записи, и адрес новой записи P помещается в голову списка. Вот эти операторы.

P^.mNext:= List; { Цепляем предыдущую запись к новой записи }

List:= P; { Теперь голова указывает на новую запись }

Все просто, но если эти строки поменять местами, катастрофа неминуема!

Следующие рисунки показывают порядок наращивания списка. Здесь локальная переменная P обведена пунктиром, что отмечает её временный характер. Пунктирные стрелки с цифрами отмечают порядок выполняемых действий.

На рис. 121 и рис. 122 выполняется вставка первого элемента. В начальный момент, когда список ещё пуст, его голова – глобальная переменная List – содержит заглушку NIL, помещенную туда главной программой.

В результате присваивания оператором

P^.mNext:= List;

значение NIL попадает в поле новой переменной P^.mNext (после создания переменной это поле было не определено и содержало мусор).

Рис.121 – Состояние списка перед вставкой первого элемента

Следующий затем оператор

List:= P;

сохраняет указатель на вновь созданную переменную в голове списка List. Теперь, перед выходом из процедуры, на эту переменную ссылаются уже два указателя (рис. 122). Но поскольку P – это локальная переменная, которая вскоре исчезнет, то после выхода из процедуры единственной ссылкой на первый элемент останется голова списка List.

Рис.122 – Состояние списка после вставки первого элемента

Следующая пара рисунков показывает вставку второго и последующих элементов. Сначала адрес бывшего первого элемента копируется из головы списка List в поле mNext вновь созданной переменной. Теперь доступ ко всем последующим элементам возможен через это поле. А следующий оператор ставит во главе списка вновь созданную переменную. Так новичок возглавляет список, оттесняя старожилов на последующие места.

Рис. 123 – Состояние списка перед вставкой второго элемента

Рис. 124 – Состояние списка после вставки второго элемента

Распечатка списка

Теперь рассмотрим процедуру распечатки списка PrintList. Кто скажет, что она проста? Не проста, а очень проста! Подобные ей процедуры обработки списков строятся на основе цикла While. Скелет такой типовой процедуры показан ниже.

P:= List;

while Assigned(P) do begin

{ Здесь обрабатывается элемент списка }

P:= P^.mNext; { переход к следующему элементу }

end;

На входе в цикл указатель P загружается из головы списка. Внутри цикла, после обработки очередного элемента, переходим по указателю mNext к следующему. Напомню, что функция Assigned(P)равнозначна выражению P<>NIL. Таким образом, цикл завершится после обработки последнего элемента списка, поскольку его поле mNext содержит NIL. А если список пуст (голова содержит NIL), цикл не выполнится ни разу.

Программа «P_54_1» покажет на экране следующий результат.

30 Сидоров

20 Петров

10 Иванов

Как и следовало ожидать, порядок элементов в списке оказался обратным порядку вставки в него. Этим можно воспользоваться для построения стека, что мы и сделаем в свое время.

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

Углубившись в списки, мы чуть не забыли о нашем пользователе – полицейском. А ведь ему придется искать в базе данных информацию об угнанных автомобилях. Дополнив предыдущую программу функцией поиска, получим представленную ниже программу «P_54_2». Для экономии бумаги я не показал здесь процедуры вставки и распечатки списка.

{ P_54_2 – Размещение и поиск данных в несортированном списке }

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

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

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

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

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

end;

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

procedure AddToList(aNumber: integer; const aFam : string);

{– взять из P_54_1 –}

end;

procedure PrintList;