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;
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 Иванов
Как и следовало ожидать, порядок элементов в списке оказался обратным порядку вставки в него. Этим можно воспользоваться для построения стека, что мы и сделаем в свое время.
Поиск в несортированном списке
