Книга: Фундаментальные алгоритмы и структуры данных в Delphi

Использование начального узла

Использование начального узла

Еще раз просмотрите код вставки и удаления элемента связного списка. Не кажется ли вам неудобным наличие двух случаев для обеих операций? Отдельные специальные случаи нужны для обработки вставки и удаления первого узла - операция, которая, возможно, будет выполняться не очень часто. Может быть, существует другой способ? Другой способ действительно есть, он предусматривает использование фиктивного начального узла. Фиктивный начальный узел - это узел, который нужен только в качестве заполнителя, в нем не будут храниться данные. Первым реальным узлом будет тот, на который указывает указатель Next фиктивного узла. Связный список, как и раньше, заканчивается узлом, указатель Next которого равен nil. При создании такого списка его нужно правильно инициализировать, выделив память под начальный узел и установив его указатель Next равным nil.

var

HeadNode : PSimpleNode;

begin

• • •

New(HeadNode);

HeadNode^.Next := nil;

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

Конечно, введение фиктивного начального узла усложнило реализацию класса: теперь при создании нового связного списка нам нужно распределить и инициализировать дополнительный узел, а при удалении списка - уничтожить этот узел.

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