Двусвязные списки

В двусвязных списках базовый комбинированный тип S для указателей типа P будет иметь два адресных поля: поле ls ссылки на следующую запись списка и поле lp ссылки на предыдущую запись списка. Описание двусвязных списков аналогично приведенному выше (для односвязных списков) с отличием в структуре S:

P=^S; {тип указатель записи базового типа S}

S=Record {базовый тип для указателей типа Р}

ls: P; {поле типа Р ссылки на следующую запись}

lp: P; {поле типа Р ссылки на предыдущую запись}

Dt: Z {поле типа Z записи данных}

end;

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

Обычно считается, что список пуст, если в нем имеется только звено заголовка и нет ни одного звена с данными. При работе с такими списками в начале необходимо создать заголовок (процедурой New), а в конце программы этот заголовок должен быть удален процедурой Dispose. Добавление звена в список и удаление из списка обычно оформляется в виде процедур. Перемещение по списку чаще всего выполняется с помощью итеративного цикла (" …Пока не достигнем звена с нужными данными или не просмотрим весь список…"). Ниже приведены некоторые примеры процедур для разных видов списков. Проверка " пуст ли список" обычно нужна для того, чтобы упростить процедуры работы со списками, так как с пустыми списками не все операции возможны.

Для линейных и кольцевых списков с заголовком вне кольца, проверяется ссылка из заголовка на следующее звено. Если Uz^.ls=nil, то список пуст. Для кольцевых с заголовком в кольце – если Uz^.ls=Uz, то список пуст.

Пример процедуры добавления элемента в линейный односвязный список (определяемый указателем Uz) после звена, заданного текущим указателем (U).

procedure PutS1(Var U: P; E: Z);

var

q: P1; { Завели рабочий указатель }

begin

new(q); { Создаем новое звено, пока вне списка }

q^.Dt: =E; { заполняем его информацией }

q^.ls: =U^.ls; {подцепляем к новому звену конец списка за U }

U^.ls: =q {подцепляем к началу списка (до U) новое звено}

end;

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

Пример процедуры удаления элемента, заданного текущим указателем (U) из линейного двусвязного списка.

procedure DelS2(Var U: P);

var

q: P; { Завели рабочий указатель }

begin

q: =U^.lp; {q указывает звено перед тем, на которое указывает U }

q^.ls: =U^.ls; {в звене q^ меняем ссылку на следующее звено – за U^}

if U^.ls< > nil then {если удаляемое звено – не последнее, то }

begin

q: =U^.ls; { в звене за удаляемым }

q^.lp: =U^.lp { меняем ссылку на предыдущее звено }

end;

dispose(U); { собственно удаление звена }

U: =nil { очистка указателя на удаленное звено }

end;

После срабатывания этой процедуры текущий указатель перестает указывать на что-либо (равен nil).

Пример процедуры удаления элемента, заданного текущим указателем (U) из кольцевого двусвязного списка.

procedure DelS2K(Var U: P);

var

q: P;

begin

q: =U^.lp;

q^.ls: =U^.ls;

q: =U^.ls;

q^.lp: =U^.lp;

dispose(U);

U: =nil;

end;

Выбор данных из списка производится без изменения списка, путем ссылки на информационную часть нужного звена: U^.Dt. Чтобы добраться до нужного звена списка, по нему приходится последовательно перемещаться (в цикле, начиная от начала или от текущего звена). Так же как при работе с массивом, для перехода от элемента A[i] к следующему элементу необходимо выполнить i: =i+1.

При работе со списком следует использовать оператор U: =U^ls.

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