Энциклопедия Turbo Pascal. Главы 1-4 - Связанные списки с одиночной связью
ОГЛАВЛЕНИЕ
Связанные списки с одиночной связью
В списке с одиночной связью каждый элемент данных имеет связь с последующим элементом в списке. Каждый элемент данных обычно представляет собой запись, которая содержит информационные поля и указатель связи. Список с одиночной связью показан на рис. 8.
------¬ ------¬ ------¬
¦1info¦ ¦1info¦ ¦1info¦
+-----+ +-----+ +-----+
¦2link¦ ¦2link¦ ¦3 nil¦
L------ L------ L-----.
Рис.8. Расположение списка с одиночной связью в памяти:
1 - информация; 2 - указатель связи; 3 - нуль.
Имеется два способа построения списка с одиночной связью. В первом случае каждый новый элемент добавляется в начало или в конец списка. Во втором случае каждый элемент добавляется в свое место в списке /например, так, чтобы обеспечить упорядочность по возрастанию/.
Способ построения списка определяется процедурой постановки нового элемента в список. Ниже дается такая процедура для простого случая, когда элементы добавляются в конец списка. Необходимо определить запись, которая будет содержать информацию и указатели связи. В этом примере запись содержит адрес почтовой корреспонденции. Тип записи для каждого элемента в списке адресов определяется ниже:
AddrPointer = ^address;
address = record
name: string[30];
street: string[40];
city: string[20];
state: string[2];
zip: string[9];
next: AddrPointer; { указатель на следующую запись }
end;
DataItem = address;
var
start.last: AddrPointer;
Ниже представлена функция добавления в список с одной связью, когда каждый новый элемент помещается в конец списка.
Указатель записи типа "address" должен передаваться в качестве аргумента функции:
{ добавление в список с одной связью }
procedure SL_Store(i: AddrPointer);
Legin
if last=nil then { первый элемент списка } 2
begin
last := i;
start := i;
i^.next := nil;
end else
begin
last^.next := i;
i^.next := nil;
last := i;
end;
end; { конец процедуры добавления элементов в список с
одной связью }Следует помнить, что до первого обращения к этой функции переменные "start" и "last" должны быть установлены на значение "nil".
Можно предусмотреть отдельную операцию по сортировке списка, созданного с помощью указанной функции добавления элементов в список с одной связью. Однако упорядочения легче добиться во время вставки путем установки каждого нового элемента в соответствующее место списка. Кроме того, если список уже является отсортированным, то имеет смысл сохранить его упорядоченность, вставляя каждый новый элемент в соответствующее место списка. Для этого делается последовательный просмотр списка до тех пор, пока не будет найдено нужное место. В это место вставляется новый адрес и делается соответствующее изменение связей.
При вставке элемента в список с одной связью может воникнуть одна из трех ситуаций. Во-первых, новый элемент может оказаться первым в списке. Во-вторых, он может встать между другими двумя элементами и в-третьих, он может оказаться последним элементом в списке. На рис.9 показано, как для каждого из этих случаев изменяются связи.
Если изменяется первый элемент списка, то везде в программе должна быть изменена точка входа в список. Для того, чтобы избежать этого, в качестве первого элемента нужно использовать фиктивный элемент. Этот фиктивный элемент должен иметь такое значение, которое обеспечивает ему первое место в списке. В этом случае точка входа в список не будет меняться. Однако, недостатком такого метода является необходимость расхода дополнительной памяти для фиктивного элемента и поэтому в показанном примере этот метод не используется.
1 Новый первый элемент
------¬ ------¬
¦2 new¦ ¦2 new¦
+-----+ +-----+
¦ ¦ ¦ ¦
L------ L----- 4becomes
------¬ ------¬ ------¬ ------¬ ------¬ ------¬
¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+
¦ ¦ ¦ ¦ ¦5 nil¦ ¦ ¦ ¦ ¦ ¦5 nil¦
L------ L------ L------ L------ L------ L-----
6 New Middle Item
------¬ ------¬
¦2 new¦ ¦2 new¦
+-----+ +-----+
¦ ¦ ¦ ¦
L------ L----- 4becomes
------¬ ------¬ ------¬ ------¬ ------¬ ------¬
¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+
¦ ¦ ¦ ¦ ¦5 nil¦ ¦ ¦ ¦ ¦ ¦5 nil¦
L------ L------ L------ L------ L------ L-----
7 New Last Item
------¬ ------¬
¦2 new¦ ¦2 new¦
+-----+ +-----+
¦ ¦ ¦5 nil¦
L------ L----- 4becomes
------¬ ------¬ ------¬ ------¬ ------¬ ------¬
¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+
¦ ¦ ¦ ¦ ¦5 nil¦ ¦ ¦ ¦ ¦ ¦ ¦
L------ L------ L------ L------ L------ L------
Рис.9. Вставка элемента в список с одной связью:
1 - новый первый элемент;
2 - новый элемент;
3 - информационные поля;
4 - справа дается преобразованный список;
5 - нулевой указатель связи;
6 - новый средний элемент;
7 - новый последний элемент.
Приводимая ниже функция используется для вставки адресов почтовых корреспонденций в порядке возрастания фамилий /поле
"name"/. В качестве результата функции выдается первый элемент списка. Входными аргументами этой функции являются указатели на начало и конец списка.
{ добавление элементов в список с одной связью с сохранением
упорядоченности }
function SLS_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;
SLS_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;
SLS_Store:=top; { сохранить начало }
done:=TRUE;
end else
begin
info^.next:=start; { новый первый элемент }
SLS_Store:=info;
done:=TRUE;
end;
end;
end; {while}
if not done then
begin
last^.next:=info; { вставка в конец }
info^.next:=nil;
last:=info;
SLS_Store:=top;
end;
end;
end;
{ конец процедуры упорядоченной вставки в список с одной связью}Для связанного списка обычно не предусматривается отдельная функция, связанная с процессом поиска, при котором элементы выдаются в порядке их расположения в списке. Эта функция обычно программируется очень просто и оформляется вместе с другими функциями, например, поиском отдельного элемента, его удалением или выводом на экран. В качестве примера ниже приводится процедура вывода всех фамилий в списке адресов почтовых корреспонденций:
procedure Display(start: AddrPointer);
begin
while start<>nil do begin
WriteLn(start^.name);
start:=start^.next;
end;
end; { конец процедуры вывода}
Здесь переменная "start" является указателем на первую запись в списке.
Поиск элемента в списке представляет собой простую процедуру прохода по цепочке. Процедуру поиска адресов по фамилиям можно составить следующим образом:
function Search(start:AddrPointer;name:str80):AddrPointer;
var
done:boolean;
begin
done := FALSE;
while (start<>nil) and (not done) do
begin
if name=start^.name then
begin
Search:=start;
done:=TRUE;
end else
start:=start^.next;
end;
if start=nil then Search := nil; { нет в списке }
end; { конец процедуры поиска элемента }
Поскольку эта процедура поиска в результате выдает указатель на тот элемент списка, который соответствует искомой фамилии, переменная "Search" должна объявляться как указатель записи типа
"address". Если требуемый элемент отсутствует в списке, то в результате выдается нулевой указатель.
Процедура удаления элемента из списка с одной связью программируется просто. Как при вставке элемента здесь может встретиться один из трех случаев: удаляется первый элемент, удаляется средний элемент и удаляется последний элемент. На рис.10 иллюстрируется каждая ситуация.
1 Deleting the First Item 2becomes
------¬ ------¬ ------¬ ------¬ ------¬ ------¬
¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+
¦ ¦ ¦ ¦ ¦5 nil¦ ¦5 nil¦ ¦ ¦ ¦5 nil¦
L------ L------ L------ L------ L------ L-----
6 Deleting a Middle Item 2becomes
------¬ ------¬ ------¬ ------¬ ------¬ ------¬
¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦ ¦ ¦3info¦
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+
¦ ¦ ¦ ¦ ¦5nil ¦ ¦ ¦ ¦5 nil¦ ¦5 nil¦
L------ L------ L------ L------ L------ L-----
7 Deleting the Last Item 2becomes
------¬ ------¬ ------¬ ------¬ ------¬ ------¬
¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦ ¦
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+
¦ ¦ ¦ ¦ ¦5 nil¦ ¦ ¦ ¦5 nil¦ ¦5 nil¦
L------ L------ L------ L------ L------ L------
Рис.10. Удаление элемента из списка с одной связью:
1 - удаление первого элемента;
2 - левый список преобразуется в правый;
3 - информационные поля;
4 - удаленный элемент;
5 - связь с нулевым значением;
6 - удаление среднего элемента;
7 - удаление последнего элемента.
Приводимая ниже функция выполняет удаление заданного элемента из списка записей адресов:
function SL_Delete(start, item, prior_item: AddrPointer)
:AddrPointer;
begin
if prior_item<>nil then
prior_item^.next:=item^.next
else start:= item^.next;
SL_Delete:=start;
end; { конец функции удаления элемента из списка с одной
связью }
Приведенная функция передает указатель элемента, указатель элемента, стоящего перед удаленным, и указатель на начало списка.
Если удаляется первый элемент, то указатель элемента, стоящего перед удаленным, будет иметь нулевое значение. Значением функции должен являться указатель на начало списка, поскольку может удалиться первый элемент и необходимо знать, где будет новый первый элемент списка.
Списки с одной связью имеют один большой недостаток, который препятствует их широкому применению: такой список нельзя просматривать в обратном направлении. Для этих целей используются списки с двойной связью.