Связанные списки с одиночной связью
В списке с одиночной связью каждый элемент данных имеет связь с последующим элементом в списке. Каждый элемент данных обычно представляет собой запись, которая содержит информационные поля и указатель связи. Список с одиночной связью показан на рис. 8.
Рис.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 показано, как для каждого из этих случаев изме- няются связи.
Если изменяется первый элемент списка, то везде в программе должна быть изменена точка входа в список. Для того, чтобы избе- жать этого, в качестве первого элемента нужно использовать фик- тивный элемент. Этот фиктивный элемент должен иметь такое значе- ние, которое обеспечивает ему первое место в списке. В этом случае точка входа в список не будет меняться. Однако, недостат- ком такого метода является необходимость расхода дополнительной памяти для фиктивного элемента и поэтому в показанном примере этот метод не используется.
Рис.9. Вставка элемента в список с одной связью:1 - новый первый элемент;
2 - новый элемент;
3 - информационные поля;
4 - справа дается преобразованный список;
5 - нулевой указатель связи;
6 - новый средний элемент;
7 - новый последний элемент.
Приводимая ниже функция используется для вставки адресов почтовых корреспонденций в порядке возрастания фамилий /поле "name"/. В качестве результата функции выдается первый элемент списка. Входными аргументами этой функции являются указатели на начало и конец списка.
{ добавление элементов в список с одной связью с сохранением упорядоченности }function SLS_Store(info, start: AddrPointer;
var last: AddrPointer): AddrPointer;
var
old, top: AddrPoin
ter;
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 иллюст- рируется каждая ситуация.
Рис.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; { конец функции удаления элемента из списка с одной связью }
Приведенная функция передает указатель элемента, указатель элемента, стоящего перед удаленным, и указатель на начало списка. Если удаляется первый элемент, то указатель элемента, стоящего перед удаленным, будет иметь нулевое значение. Значением функции должен являться указатель на начало списка, поскольку может уда- литься первый элемент и необходимо знать, где будет новый первый элемент списка. Списки с одной связью имеют один большой недостаток, который препятствует их широкому применению: такой список нельзя просмат- ривать в обратном направлении. Для этих целей используются списки с двойной связью. Приведенная функция передает указатель элемента, указатель элемента, стоящего перед удаленным, и указатель на начало списка. Если удаляется первый элемент, то указатель элемента, стоящего перед удаленным, будет иметь нулевое значение. Значением функции должен являться указатель на начало списка, поскольку может уда- литься первый элемент и необходимо знать, где будет новый первый элемент списка. Списки с одной связью имеют один большой недостаток, который препятствует их широкому применению: такой список нельзя просмат- ривать в обратном направлении. Для этих целей используются списки с двойной связью.
Приведенная функция передает указатель элемента, указатель элемента, стоящего перед удаленным, и указатель на начало списка. Если удаляется первый элемент, то указатель элемента, стоящего перед удаленным, будет иметь нулевое значение. Значением функции должен являться указатель на начало списка, поскольку может уда- литься первый элемент и необходимо знать, где будет новый первый элемент списка.
Списки с одной связью имеют один большой недостаток, который препятствует их широкому применению: такой список нельзя просмат- ривать в обратном направлении. Для этих целей используются списки с двойной связью.?
