|
Страница 25 из 60
Связанные списки с одиночной связью В списке с одиночной связью каждый элемент данных имеет
связь с последующим элементом в списке. Каждый элемент данных
обычно представляет собой запись, которая содержит информационные
поля и указатель связи. Список с одиночной связью показан на рис.
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; { конец функции удаления элемента из списка с одной
связью }
Приведенная функция передает указатель элемента, указатель
элемента, стоящего перед удаленным, и указатель на начало списка.
Если удаляется первый элемент, то указатель элемента, стоящего
перед удаленным, будет иметь нулевое значение. Значением функции
должен являться указатель на начало списка, поскольку может уда-
литься первый элемент и необходимо знать, где будет новый первый
элемент списка.
Списки с одной связью имеют один большой недостаток, который
препятствует их широкому применению: такой список нельзя просмат-
ривать в обратном направлении. Для этих целей используются списки
с двойной связью.
|