Списки с двойной связью
Каждый элемент в списке с двойной связью имеет указатель на
следующий элемент списка и указатель на предыдущий элемент спис-
ка. Рис.11 иллюстрирует характер связей в таком списке. Список,
который вместо одной имеет две связи, отличается двумя основными
преимуществами. Во-первых, список может читаться в обоих направ-
лениях. Это не только упрощает сортировку списка, но также позво-
ляет пользователям базы данных просматривать данные в обоих нап-
равлениях. Во-вторых, и прямая и обратная связь позволяют
прочитать список полностью и поэтому при нарушении одной из свя-
зей список может быть восстановлен по другой связи. Это свойство
имеет смысл использовать при отказах оборудования, приводящих к
нарушению списка.
+----------+ +----------+ +-----------+
¦1 info ¦ ¦1 info ¦ ¦1 info ¦
+----------¦ +----------¦ +-----------¦
¦2nil ¦ ¦ ¦ ¦ ¦ ¦ ¦2 nil¦
+----------+ +----------+ +-----------+
Рис.11. Список с двойной связью:
1 - информационные поля; 2 - связь с нулевым значением.
Для списка с двойной связью предусматриваются три основные
операции: вставка нового первого элемента, вставка нового средне-
го элемента и вставка нового последнего элемента. Эти операции
проиллюстрированы на рис.12.
Список с двойной связью строится подобно списку с одной
связью, причем в записи должно быть предусмотрено место для двух
указателей. Для примера со списком почтовых корреспонденций за-
пись адреса можно модифицировать следующим образом:
type
str80 = string[80];
AddrPointer = ^address;
address = record
1 Inserling a New First Element
+------+ +------+
¦2 new ¦ ¦2 new ¦
+------¦ +------¦
¦ ¦ ¦ ¦ ¦ ¦
+------+ +------+
4becomes
Энциклопедия по Турбо-Паскалю ч.1 = 56 =
+------+ +------+ +------+ +------+ +------+ +------+
¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦
+------¦ +------¦ +------¦ +------¦ +------¦ +------¦
3¦nil¦ ¦ ¦ ¦ ¦ ¦ ¦nil¦3 ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦nil¦3
+------+ +------+ +------+ +------+ +------+ +------+
6 Inserling a New Middle Element
+------+ +------+
¦2 new ¦ ¦2 new ¦
+------¦ +------¦
¦ ¦ ¦ ¦ ¦ ¦
+------+ +------+
4becomes
+------+ +------+ +------+ +------+ +------+ +------+
¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦
+------¦ +------¦ +------¦ +------¦ +------¦ +------¦
3¦nil¦ ¦ ¦ ¦ ¦ ¦ ¦nil¦3 3¦nil¦ ¦ ¦ ¦ ¦ ¦ ¦nil¦3
+------+ +------+ +------+ +------+ +------+ +------+
7 Inserling a New Last Element
+------+ +------+
¦2 new ¦ ¦2 new ¦
+------¦ +------¦
¦ ¦ ¦ ¦ ¦nil¦3
+------+ +------+
4becomes
+------+ +------+ +------+ +------+ +------+ +------+
¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦
+------¦ +------¦ +------¦ +------¦ +------¦ +------¦
3¦nil¦ ¦ ¦ ¦ ¦ ¦ ¦nil¦3 3¦nil¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
+------+ +------+ +------+ +------+ +------+ +------+
Рис.12. Вставка элемента в список с двойной связью:
1 - вставка нового первого элемента;
2 - новый элемент;
3 - указатель с нулевым значением;
4 - левый список преобразуется в правый;
5 - информационные поля;
6 - вставка нового среднего элемента;
7 - вставка нового последнего элемента.
name : string[30];
street: string[40];
city: string[20];
state: string[2];
zip: string[9];
next: AddrPointer; { указатель на следующую запись }
prior: AddrPointer; { указатель на предыдущую запись }
end;
Энциклопедия по Турбо-Паскалю ч.1 = 57 =
DataItem = address;
DataArray = array [1..100] of AddrPointer;
Ниже приводится функция, которая позволяет строить список с
двойной связью для записей адресов:
{добавление элементов в список с двойной связью }
procedure DL_Store(i: AddrPointer);
begin
if last=nil then { первый элемент списка }
begin
last:=i;
start:=i;
i^.next:=nil;
i^.prior:=nil;
end
else
begin
last^.next:=i;
i^.next:=nil;
i^.prior:=last;
last:=i;
end;
end; { конец функции добавления в список с двойной связью }
Эта функция помещает каждый новый элемент в конец списка.
Следует иметь в виду, что перед первым обращением к функции пере-
менные "start" и "last" должны устанавливаться в нулевое значе-
ние.
В ходе построения списка с двойной связью каждый новый эле-
мент может /как и для списка с одной связью/ устанавливаться не в
конец, а в соответствующее место, обеспечивая упорядочность эле-
ментов в списке. Ниже приводится функция, которая создает список
с двойной связью, упорядоченый по возрастанию фамилий из записей
адресов:
{упорядоченная установка элементов в список с двойной связью}
function DSL_Store(info, start: AddrPointer;
var last: AddrPointer): AddrPointer;
{ вставка элементов в соответствующее место с сохранением
порядка }
var
old, top: AddrPointer;
done: boolean;
begin
top := start;
old := nil;
Энциклопедия по Турбо-Паскалю ч.1 = 58 =
done := FALSE;
if start = nil then begin { первый элемент списка }
info^.next := nil;
last := info;
info^.prior :=nil;
DCL_Store := info;
end else
begin
while (start<>nil) and (not done) do
begin
if start^.name < info^.name then
begin
old := start;
start := start^.next;
end else
begin { вставка в середину }
if old <>nil then
begin
old^.next := info;
info^.next := start;
start^.prior := info;
info^.prior := old;
DSL_Store := top; { сохранение начала }
done := TRUE;
end else
begin
info^.next := start;{новый первый элемент }
info^.prior := nil;
DSL_Store := info;
done := TRUE;
end;
end;
end; { конец цикла }
if not done then begin
last^.next := info;
info^.next := nil;
info^.prior := last;
last := info;
DSL_Store := top; { сохранение начала }
end;
end;
end; { конец функции DSL_Store }
Поскольку элемент может помещаться в самое начало списка,
эта функция должна выдавать указатель на начало списка, чтобы в
других частях программы учесть изменения начала списка. При поис-
ке конкретного элемента списка, как и для списка с одиночной
Энциклопедия по Турбо-Паскалю ч.1 = 59 =
связью, делается последовательный проход по цепочке связей пока
не будет найден требуемый элемент.
При удалении элемента из списка возникает одна из трех ситу-
аций: удаление первого элемента, удаление среднего элемента и
удаление последнего элемента. Рис.13 иллюстрирует изменение свя-
зей для этих случаев.
1 Deleting the First Item
3becomes
+------+ +------+ +------+ +-------+ +------+ +------+
¦2 info¦ ¦2 info¦ ¦2 info¦ 4¦2 info ¦ ¦2 info¦ ¦2 info¦
+------¦ +------¦ +------¦ +-------¦ +------¦ +------¦
5¦nil¦ ¦ ¦ ¦ ¦ ¦ ¦nil¦5 5¦nil¦nil¦55¦nil¦ ¦ ¦ ¦nil¦5
+------+ +------+ +------+ +-------+ +------+ +------+
6 Deleting a Middle Item
3becomes
+------+ +------+ +------+ +------+ +-------+ +------+
¦2 info¦ ¦2 info¦ ¦2 info¦ ¦2 info¦ ¦2 info ¦ ¦2 info¦
+------¦ +------¦ +------¦ +------¦ +-------¦ +------¦
5¦nil¦ ¦ ¦ ¦ ¦ ¦ ¦nil¦5 5¦nil¦ ¦5 ¦nil¦nil¦5¦ ¦nil¦5
+------+ +------+ +------+ +------+ +-------+ +------+
7 Deleting the Last Item
3becomes
+------+ +------+ +------+ +------+ +------+ +-------+
¦2 info¦ ¦2 info¦ ¦2 info¦ ¦2 info¦ ¦2 info¦ ¦2 info ¦
+------¦ +------¦ +------¦ +------¦ +------¦ +-------¦
5¦nil¦ ¦ ¦ ¦ ¦ ¦ ¦nil¦5 5¦nil¦ ¦ ¦ ¦nil¦55¦nil¦nil¦5
+------+ +------+ +------+ +------+ +------+ +-------+
Рис.13. Удаление элемента из списка с двойной связью:
1 - удаление первого элемента; 2 - информационные поля; 3 - левый
список преобразуется в правый; 4 - удаленный элемент; 5 - указа-
тель с нулевым значением; 6 - удаление среднего элемента; 7 -
удаление последнего элемента.
Ниже приводится функция, которая выполняет удаление элемента
типа "address" из списка с двойной связью:
{ удаление элемента из списка с двойной связью }
function DL_Delete(start: AddrPointer;
key: str80): AddrPointer;
var
temp, temp2: AddrPointer;
done: boolean;
begin
if start^.name=key then begin { первый элемент списка}
DL_Delete:=start^.next;
if temp^.next <> nil then
Энциклопедия по Турбо-Паскалю ч.1 = 60 =
begin
temp := start^.next;
temp^.prior := nil;
end;
dispose(start);
end else
begin
done := FALSE;
temp := start^.next;
temp2 := start;
while (temp<>nil) and (not done) do
begin
if temp^.name=key then
begin
temp^.next:=temp^.next;
if temp^.next<>nil then
temp^.next^.prior:=temp2;
done:=TRUE;
dispose(temp);
end else
begin
temp2:=temp;
temp:=temp^.next;
end;
end;
DL_Delete:=start; { начало не изменяется }
if not done then WriteLn('not found');
end;
end; { конец функции удаления элемента
из списка с двойной связью }
Этой функции передается на один указатель меньше, чем для
соответствующей функции при использовании списка с одной связью.
/Удаленный элемент уже имеет указатель на предыдущий элемент и
указатель на следующий элемент/. Поскольку первый элемент в спис-
ке может измениться, функция возвращает указатель на начало спис-
ка.
