Реализация операций над связными линейными списками

Во всех операциях чрезвычайно важна последовательность коррекции указателей, которая обеспечивает корректное изменение списка, не затрагивающее другие элементы. При неправильном порядке коррекции легко потерять часть списка.

В программных примерах подразумеваются определенными следующие типы данных:

любая структура информационной части списка:

type data = …;

элемент односвязного списка (sll — single linked list):

type.

sllptr = ^slltype; { указатель в односвязном списке }.

slltype = record { элемент односвязного списка }.

inf: data; { информационная часть }.

next: sllptr; { указатель на следующий элемент }.

end;

элемент двухсвязного списка (dll — double linked list):

type.

dllptr = ^dlltype; { указатель в двухсвязном списке }.

dlltype = record { элемент односвязного списка }.

inf: data; { информационная часть }.

next: sllptr; { указатель на следующий элемент (вперед) }.

prev: sllptr; { указатель на предыдущий элемент (назад) }.

end;

Перебор элементов списка.

Эта операция, возможно, чаще других выполняется над линейными списками. При ее выполнении осуществляется последовательный доступ к элементам списка — ко всем до конца списка или до нахождения искомого элемента.

Алгоритм перебора для односвязного списка представляется программным примером.

{==== Программный пример ====}.

{ Перебор 1-связного списка }.

Procedure LookSll (head: sllptr);

{ head — указатель на начало списка }.

var cur: sllptr; { адрес текущего элемента }.

begin.

cur:=head; { 1-й элемент списка назначается текущим }.

while cur nil do begin.

{обрабатывается информационная часть того эл-та, на который указывает cur.

Обработка может состоять в:

• · печати содержимого инф. части;
• · модификации полей инф. части;
• · сравнения полей инф. части с образцом при поиске по ключу;
• · подсчете итераций цикла при поиске по номеру;

cur:=cur^.next;

{ из текущего эл-та выбирается указатель на следующий эл-т и для следующей итерации следующий эл-т становится текущим; если текущий эл-т был последний, то его поле next содержит пустой указатель и, т.обр. в cur запишется nil, что приведет к выходу из цикла при проверке условия while } end; end;

В двухсвязном списке возможен перебор как в прямом направлении (он выглядит точно так же, как и перебор в односвязном списке), так и в обратном. В последнем случае параметром процедуры должен быть tail — указатель на конец списка, и переход к следующему элементу должен осуществляться по указателю назад: cur:=cur^.prev;

В кольцевом списке окончание перебора должно происходить не по признаку последнего элемента — такой признак отсутствует, а по достижению элемента, с которого начался перебор.

Вставка элемента в середину односвязного списка показана на рисунке.

{==== Программный пример ====}.

{ Вставка элемента в середину 1-связного списка }.

Procedure InsertSll (prev: sllptr; inf: data);

{ prev — адрес предыдущего эл-та; inf — данные нового эл-та }.

var cur: sllptr; { адрес нового эл-та }.

begin.

{ выделение памяти для нового эл-та и запись в его инф. часть }.

New (cur); cur^.inf:=inf;

cur^.next:=prev^.next; { эл-т, следовавший за предыдущим теперь будет следовать за новым }.

prev^.next:=cur; { новый эл-т следует за предыдущим }.

end;

Рисунок представляет вставку в двухсвязный список.

Приведенные примеры обеспечивают вставку в середину списка, но не могут быть применены для вставки в начало списка. При последней должен модифицироваться указатель на начало списка, как показано на рисунке.

Программный пример представляет процедуру, выполняющую вставку элемента в любое место односвязного списка.

{==== Программный пример ====}.

{ Вставка элемента в любое место 1-связного списка }.

Procedure InsertSll.

var head: sllptr; { указатель на начало списка, может измениться в процедуре, если head=nil — список пустой }.

prev: sllptr; { указатель на эл-т, после к-рого делается вставка, если prev-nil — вставка перед 1-ым эл-том }.

inf: data { - данные нового эл-та }.

var cur: sllptr; { адрес нового эл-та }.

begin.

{ выделение памяти для нового эл-та и запись в его инф. часть }.

New (cur); cur^.inf:=inf;

if prev nil then begin { если есть предыдущий эл-т — вставка в середину списка, см. прим.5.2 }.

cur^.next:=prev^.next; prev^.next:=cur;

end.

else begin { вставка в начало списка }.

cur^.next:=head; { новый эл-т указывает на бывший 1-й эл-т списка;

если head=nil, то новый эл-т будет и последним эл-том списка }.

head:=cur; { новый эл-т становится 1-ым в списке, указатель на начало теперь указывает на него }.

end; end;

Удаление элемента из списка.

Удаление элемента из односвязного списка показано на рисунке.

Очевидно, что процедуру удаления легко выполнить, если известен адрес элемента, предшествующего удаляемому. Процедура обеспечивает удаления как из середины, так и из начала списка.

{==== Программный пример ====}.

{ Удаление элемента из любого места 1-связного списка }.

Procedure DeleteSll (.

var head: sllptr; { указатель на начало списка, может измениться в процедуре }.

del: sllptr { указатель на эл-т, к-рый удаляется });

var prev: sllptr; { адрес предыдущего эл-та }.

begin.

if head=nil then begin { попытка удаления из пустого списка асценивается как ошибка (в последующих примерах этот случай учитываться на будет) }.

Writeln ('Ошибка!'); Halt;

end;

if del=head then { если удаляемый эл-т — 1-й в списке, то следующий за ним становится первым }.

head:=del^.next.

else begin { удаление из середины списка }.

{ приходится искать эл-т, предшествующий удаляемому; поиск производится перебором списка с самого его начала, пока не будет найдет эл-т, поле next к-рого совпадает с адресом удаляемого элемента }.

prev:=head^.next;

while (prev^.nextdel) and (prev^.nextnil) do.

prev:=prev^.next;

if prev^.next=nil then begin.

{ это случай, когда перебран весь список, но эл-т не найден, он отсутствует в списке; расценивается как ошибка (в последующих примерах этот случай учитываться на будет) }.

Writeln ('Ошибка!'); Halt;

end;

prev^.next:=del^.next; { предыдущий эл-т теперь указывает на следующий за удаляемым }.

end;

{ элемент исключен из списка, теперь можно освободить занимаемую им память }.

Dispose (del);

end;

Удаление элемента из двухсвязного списка требует коррекции большего числа указателей, как показано на рисунке.

Процедуру удаления элемента из двухсвязного списка окажется даже проще, чем для односвязного, так как в ней не нужен поиск предыдущего элемента, он выбирается по указателю назад.

Перестановка элементов списка.

Изменчивость динамических структур данных предполагает не только изменения размера структуры, но и изменения связей между элементами. Для связных структур изменение связей не требует пересылки данных в памяти, а только изменения указателей в элементах связной структуры. В качестве примера приведена перестановка двух соседних элементов списка. В алгоритме перестановки в односвязном списке исходили из того, что известен адрес элемента, предшествующего паре, в которой производится перестановка. В приведенном алгоритме также не учитывается случай перестановки первого и второго элементов.

{==== Программный пример ====}.

{ Перестановка двух соседних элементов в 1-связном списке }.

Procedure ExchangeSll (.

prev: sllptr { указатель на эл-т, предшествующий переставляемой паре });

var p1, p2: sllptr; { указатели на эл-ты пары }.

begin.

p1:=prev^.next; { указатель на 1-й эл-т пары }.

p2:=p1^.next; { указатель на 2-й эл-т пары }.

p1^.next:=p2^.next; { 1-й элемент пары теперь указывает на следующий за парой }.

p2^.next:=p1; { 1-й эл-т пары теперь следует за 2-ым }.

prev^.next:=p2; { 2-й эл-т пары теперь становится 1-ым }.

end;

В процедуре перестановки для двухсвязного списка (рис. 5.10.) нетрудно учесть и перестановку в начале/конце списка.

Копирование части списка.

При копировании исходный список сохраняется в памяти, и создается новый список. Информационные поля элементов нового списка содержат те же данные, что и в элементах старого списка, но поля связок в новом списке совершенно другие, поскольку элементы нового списка расположены по другим адресам в памяти. Существенно, что операция копирования предполагает дублирование данных в памяти. Если после создания копии будут изменены данные в исходном списке, то изменение не будет отражено в копии и наоборот.

Копирование для односвязного списка показано в программном примере.

{==== Программный пример ====}.

{ Копирование части 1-связного списка. head — указатель на начало копируемой части; num — число эл-тов. Ф-ция возвращает указатель на список-копию }.

Function CopySll (head: sllptr; num: integer): sllptr;

var cur, head2, cur2, prev2: sllptr;

begin.

if head=nil then { исходный список пуст — копия пуста }.

CopySll:=nil.

else begin.

cur:=head; prev2:=nil;

{ перебор исходного списка до конца или по счетчику num }.

while (num>0) and (curnil) do begin.

{ выделение памяти для эл-та выходного списка и запись в него информационной части }.

New (cur2); cur2^.inf:=cur^.inf;

{ если 1-й эл-т выходного списка — запоминается указатель на начало, иначе — записывается указатель в предыдущий элемент }.

if prev2nil then prev2^.next:=cur2 else head2:=cur2;

prev2:=cur2; { текущий эл-т становится предыдущим }.

cur:=cur^.next; { продвижение по исходному списку }.

num:=num-1; { подсчет эл-тов }.

end;

cur2^.next:=nil; { пустой указатель — в последний эл-т выходного списка }.

CopySll:=head2; { вернуть указатель на начало вых. списка }.

end; end;

Слияние двух списков.

Операция слияния заключается в формировании из двух списков одного — она аналогична операции сцепления строк. В случае односвязного списка, показанном в примере слияние выполняется очень просто. Последний элемент первого списка содержит пустой указатель на следующий элемент, этот указатель служит признаком конца списка. Вместо этого пустого указатель в последний элемент первого списка заносится указатель на начало второго списка. Таким образом, второй список становится продолжением первого.

{==== Программный пример ====}.

{ Слияние двух списков. head1 и head2 — указатели на начала списков. На результирующий список указывает head1 }.

Procedure Unite (var head1, head2: sllptr);

var cur: sllptr;

begin { если 2-й список пустой — нечего делать }.

if head2nil then begin.

{ если 1-й список пустой, выходным списком будет 2-й }.

if head1=nil then head1:=head2.

else { перебор 1-го списка до последнего его эл-та }.

begin cur:=head1;

while cur^.nextnil do cur:=cur^.next;

{ последний эл-т 1-го списка указывает на начало 2-го }.

cur^.next:=head2;

end; head2:=nil; { 2-й список аннулируется }.

end; end;