Энциклопедия Turbo Pascal. Главы 1-4 - Списки с двойной связью
ОГЛАВЛЕНИЕ
Списки с двойной связью
Каждый элемент в списке с двойной связью имеет указатель на следующий элемент списка и указатель на предыдущий элемент списка. Рис.11 иллюстрирует характер связей в таком списке. Список, который вместо одной имеет две связи, отличается двумя основными преимуществами. Во-первых, список может читаться в обоих направлениях. Это не только упрощает сортировку списка, но также позволяет пользователям базы данных просматривать данные в обоих направлениях. Во-вторых, и прямая и обратная связь позволяют прочитать список полностью и поэтому при нарушении одной из связей список может быть восстановлен по другой связи. Это свойство имеет смысл использовать при отказах оборудования, приводящих к нарушению списка.
-----------¬ -----------¬ ------------¬
¦1 info ¦ ¦1 info ¦ ¦1 info ¦
+-----T----+ +-----T----+ +-----T-----+
¦2nil ¦ ¦ ¦ ¦ ¦ ¦ ¦2 nil¦
L-----+----- L-----+----- L-----+-----
Рис.11. Список с двойной связью:
1 - информационные поля; 2 - связь с нулевым значением.
Для списка с двойной связью предусматриваются три основные операции: вставка нового первого элемента, вставка нового среднего элемента и вставка нового последнего элемента. Эти операции проиллюстрированы на рис.12.
Список с двойной связью строится подобно списку с одной связью, причем в записи должно быть предусмотрено место для двух указателей. Для примера со списком почтовых корреспонденций запись адреса можно модифицировать следующим образом:
type
str80 = string[80];
AddrPointer = ^address;
address = record
1 Inserling a New First Element
-------¬ -------¬
¦2 new ¦ ¦2 new ¦
+---T--+ +---T--+
¦ ¦ ¦ ¦ ¦ ¦
L---+--- L---+-- 4becomes
-------¬ -------¬ -------¬ -------¬ -------¬ -------¬
¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦
+---T--+ +--T---+ +--T---+ +--T---+ +---T--+ +--T---+
3¦nil¦ ¦ ¦ ¦ ¦ ¦ ¦nil¦3 ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦nil¦3
L---+--- L--+---- L--+---- L--+---- L---+--- L--+--- 6 Inserling a New Middle Element
-------¬ -------¬
¦2 new ¦ ¦2 new ¦
+--T---+ +---T--+
¦ ¦ ¦ ¦ ¦ ¦
L--+---- L---+-- 4becomes
-------¬ -------¬ -------¬ -------¬ -------¬ -------¬
¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦
+---T--+ +--T---+ +--T---+ +---T--+ +---T--+ +--T---+
3¦nil¦ ¦ ¦ ¦ ¦ ¦ ¦nil¦3 3¦nil¦ ¦ ¦ ¦ ¦ ¦ ¦nil¦3
L---+--- L--+---- L--+---- L---+--- L---+--- L--+--- 7 Inserling a New Last Element
-------¬ -------¬
¦2 new ¦ ¦2 new ¦
+--T---+ +--T---+
¦ ¦ ¦ ¦ ¦nil¦3
L--+---- L--+--- 4becomes
-------¬ -------¬ -------¬ -------¬ -------¬ -------¬
¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦ ¦5 info¦
+---T--+ +--T---+ +--T---+ +---T--+ +--T---+ +---T--+
3¦nil¦ ¦ ¦ ¦ ¦ ¦ ¦nil¦3 3¦nil¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
L---+--- L--+---- L--+---- L---+--- L--+---- L---+---
Рис.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;
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;
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 }Поскольку элемент может помещаться в самое начало списка, эта функция должна выдавать указатель на начало списка, чтобы в других частях программы учесть изменения начала списка. При поиске конкретного элемента списка, как и для списка с одиночной связью, делается последовательный проход по цепочке связей пока не будет найден требуемый элемент.
При удалении элемента из списка возникает одна из трех ситуаций: удаление первого элемента, удаление среднего элемента и удаление последнего элемента. Рис.13 иллюстрирует изменение связей для этих случаев.
1 Deleting the First Item
3becomes
-------¬ -------¬ -------¬ --------¬ -------¬ -------¬
¦2 info¦ ¦2 info¦ ¦2 info¦ 4¦2 info ¦ ¦2 info¦ ¦2 info¦
+---T--+ +--T---+ +--T---+ +---T---+ +---T--+ +--T---+
5¦nil¦ ¦ ¦ ¦ ¦ ¦ ¦nil¦5 5¦nil¦nil¦55¦nil¦ ¦ ¦ ¦nil¦5
L---+--- L--+---- L--+---- L---+---- L---+--- L--+---
6 Deleting a Middle Item
3becomes
-------¬ -------¬ -------¬ -------¬ --------¬ -------¬
¦2 info¦ ¦2 info¦ ¦2 info¦ ¦2 info¦ ¦2 info ¦ ¦2 info¦
+---T--+ +--T---+ +--T---+ +---T--+ +---T---+ +--T---+
5¦nil¦ ¦ ¦ ¦ ¦ ¦ ¦nil¦5 5¦nil¦ ¦5 ¦nil¦nil¦5¦ ¦nil¦5
L---+--- L--+---- L--+---- L---+--- L---+---- L--+---
7 Deleting the Last Item
3becomes
-------¬ -------¬ -------¬ -------¬ -------¬ --------¬
¦2 info¦ ¦2 info¦ ¦2 info¦ ¦2 info¦ ¦2 info¦ ¦2 info ¦
+---T--+ +--T---+ +--T---+ +---T--+ +--T---+ +---T---+
5¦nil¦ ¦ ¦ ¦ ¦ ¦ ¦nil¦5 5¦nil¦ ¦ ¦ ¦nil¦55¦nil¦nil¦5
L---+--- L--+---- L--+---- L---+--- L--+---- L---+----
Рис.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
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; { конец функции удаления элемента
из списка с двойной связью }Этой функции передается на один указатель меньше, чем для соответствующей функции при использовании списка с одной связью. /Удаленный элемент уже имеет указатель на предыдущий элемент и указатель на следующий элемент/. Поскольку первый элемент в списке может измениться, функция возвращает указатель на начало списка.