Наиболее удобной в двунаправленном списке является та организация ссылок, при которой движение, перебор элементов в обратном направлении является строго противоположным перебору элементов в прямом направлении. Такой двунаправленный список называется симметричным.Например, в прямом направлении элементы линейного списка пронумерованы и выбираются так: 1, 2, 3, 4, 5. Строго говоря, перебирать элементы в обратном направлении можно по-разному, соответствующим способом организуя ссылки, например: 4, 1, 5, 3, 2. Симметричным же будет называться список, реализующий перебор элементов в таком порядке: 5, 4, 3, 2, 1.
Следует заметить, что «обратный» список, так же, как и прямой, является просто линейным однонаправленным списком, который заканчивается элементом со ссылкой, имеющей значение nil. Для удобства работы со списком в обратном направлении и в соответствии с идеологией однонаправленного списка нужен доступ к первому в обратном направлении элементу. Такой доступ осуществляется с помощью указателя LAST («говорящее» имя) на этот первый в обратном направлении элемент.Структура линейного двунаправленного симметричного списка дана на рис. 19 .
Как указывалось ранее, замкнутый, циклический, кольцевой список организован таким образом, что в адресную часть конечного элемента вместо константы nil помещается адрес начального элемента (список замыкается сам на себя). В симметричном кольцевом списке такое положение характерно для обоих - прямого и обратного - списков, следовательно, можно построить циклический двунаправленный список (см. рис. 20 ) .
Описание элементов списков
Элементоднонаправленного списка
Описать структуру условного элемента однонаправленного списка (см. рис 1) можно следующим образом:
Type
point=^zap;
zap=record
nf1 : integer; { первое информационное поле }
inf2 : string; { второе информационное поле }
next : point; {ссылочное поле }
end;
Из этого описания видно, что имеет место рекурсивная ссылка: для описания типа point используется тип zap, а при описании типа zapиспользуется тип point. По соглашениям Паскаля в этом случае сначала описывается тип «указатель», а затем уже тип связанной с ним переменной. Правила Паскаля только при описании ссылок допускают использование идентификатора (zap) до его описания. Во всех остальных случаях, прежде чем упомянуть идентификатор, необходимо его определить.
Элементдвунаправленного списка
В случае двунаправленного списка в описании должно появиться еще одно ссылочное поле того же типа, например,
Type
point=^zap;
zap=record
inf1 : integer; { первое информационное поле }
inf2 : string; { второе информационное поле }
next:point; {ссылочное поле на следующий элемент}
prev:point; {ссылочное поле на предыдущий элемент}
end;
Как уже отмечалось, последовательность обработки элементов списка задается системой ссылок. Отсюда следует важный факт: все действия над элементами списка, приводящие к изменению порядка обработки элементов списка - вставка, удаление, перестановка - сводятся к действиям со ссылками.Сами же элементы не меняют своего физического положения в памяти.
При работе со списками любых видов нельзя обойтись без указателя на первый элемент. Не менее полезными, хотя и не всегда обязательными, могут стать адрес последнего элемента списка и количество элементов. Эти данные могут существовать по отдельности, однако их можно объединить в единую структуру типа «запись» (из-за разнотипности полей: два поля указателей на элементы и числовое поле - для количества элементов). Эта структура и будет представлять так называемый головной элемент списка.
Type
hd_el =^ head_elem;
head_elem=record
First:el; {ссылочное поле на первый элемент списка}
prev: el; {ссылочное поле на последний элемент списка}
n : integer; { количество элементов списка }
inf : string; { необязательное поле
с произвольной информацией }
end;
Var
hd : hd_el;
Следуя идеологии динамических структур данных, головной элемент списка также необходимо сделать динамическим, выделяя под него память при создании списка и освобождая после окончания работы. Тем не менее, стоит отметить, что головной элемент может быть и статического типа. Тогда он описывается в разделе VAR как обычная переменная типа RECORD соответствующей структуры.
hd := nil;
. . .
new ( hd );
. . .
Использование данных головного элемента делает работу со списком более удобной, но требует определенных действий по его обслуживанию.
Рассмотрим основные процедуры работы с линейным однонаправленным списком без головного элемента. Действия оформлены в виде процедур или функций в соответствии с основными требованиями модульного программирования (см. соответствующий раздел пособия).
Приведем фрагменты разделов Type и Var, необходимые для дальнейшей работы с линейным однонаправленным списком без головного элемента.
Type
el = ^zap;
zap=record
inf1 : integer;{ первое информационное поле }
inf2 : string; { второе информационное поле }
next : el; {ссылочное поле }
end;
Var
first, { указатель на первый элемент списка }
p, q , t : el; { рабочие указатели, с помощью которых