Песни о Паскале

Глава 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;