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