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

В двусвязных списках базовый комбинированный тип 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.

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

Дата добавления: 2014-11-06