Книга: Песни о Паскале

Глава 54 Односвязные списки

Глава 54

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

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

Ключ к безупречному решению – в сочетании записи с указателем. Запись может содержать в своей обёртке разнородные элементы: числа, символы, строки, массивы и так далее. А если внедрить в неё указатель на другую запись этого же типа? Тогда мы сможем погрузить в кучу цепочку элементов так, как показано на рис. 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;
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 (после создания переменной это поле было не определено и содержало мусор).

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

      List:= P;

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

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

Теперь рассмотрим процедуру распечатки списка 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;
{--- взять из P_54_1 ---}
end;
      { Поиск в несортированном списке }
function Find(aNumber: integer): PRec;
var p : PRec;
begin
p:= List; { Поиск начинаем с головы списка }
{ Продвигаемся по списку, пока не найдем нужный номер
или не "упремся" в конец списка }
while Assigned(p) and (P^.mNumber <> aNumber) do p:= p^.mNext;
Find:= p; { результат поиска }
end;
var i, N : integer; P : PRec;
begin {--- Главная программа ---}
List:= nil;
      { Заполним список случайными значениями номеров }
for i:=1 to 20 do AddToList(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.

Простенькая функция Find ищет в списке элемент с нужным номером автомобиля, и возвращает указатель на этот элемент списка. При неудачном исходе функция возвращает NIL.

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

Итак, мы построили список и организовали в нём поиск данных. Довольны ли мы результатом? Для начала – неплохо, но если копнуть глубже…

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

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

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

Вот пример с тремя записями (на рис. 125 и рис. 126 показаны лишь номера автомобилей). Предположим, что список содержит записи с номерами 20, 30 и 40, и мы вставляем запись с номером 35. После создания переменной p^ надо найти предыдущий элемент, чтобы подцепить к нему новый. Обозначим указатель на такой элемент буквой q. Найдя элемент q (об этом чуть позже), вставку делаем на «раз и два» (рис. 125).

      p^.mNext:=q^.mNext; { связываем текущий со следующим }
      q^.mNext:=p;       { связываем предыдущий с текущим }

Состояние списка после вставки элемента показано на рис. 126.

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

      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.

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

Создав функцию поиска номера в сортированном списке, поставим победную точку. Будем искать запись, для которой номер в следующей за ней записи больше искомого (если следующая запись существует). Это условие совпадает с условием поиска при вставке в сортированный список. Найдя такую запись и сравнив её номер с искомым, сформируем результат: если номер найден, возвращаем указатель на эту запись, а иначе – 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-Г. Создайте несколько наборов таких данных и сравните время их обработки двумя типами контроллеров: «умным» и «глупым».

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

Оглавление книги