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

Ниже рассматриваются некоторые простые операции над линейны-

ми списками. Выполнение операций иллюстрируется в общем случае

рисунками со схемами изменения связей и программными примерами.

На всех рисунках сплошными линиями показаны связи, имевшиеся

до выполнения и сохранившиеся после выполнения операции. Пункти-

ром показаны связи, установленные при выполнении операции. Знач-

ком 'x' отмечены связи, разорванные при выполнении операции. Во

всех операциях чрезвычайно важна последовательность коррекции

указателей, которая обеспечивает корректное изменение списка, не

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

легко потерять часть списка. Поэтому на рисунках рядом с устанав-

ливаемыми связями в скобках показаны шаги, на которых эти связи

устанавливаются.

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

щие типы данных:

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

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;

Словесные описания алгоритмов даны в виде комментариев к

программным примерам.

В общем случае примеры должны были бы показать реализацию

каждой операции для списков: односвязного линейного, одсвязного

кольцевого, двухсвязного линейного, двухсвязного кольцевого. Объ-

ем нашего издания не позволяет привести полный набор примеров,

разработку недостающих примеров мы предоставляем читателю.

3Перебор элементов списка. 0 Эта операция, возможно, чаще дру-

гих выполняется над линейными списками. При ее выполнении осу-

ществляется последовательный доступ к элементам списка - ко всем

до конца списка или до нахождения искомого элемента.

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

программным примером 5.1.

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

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

Procedure LookSll(head : sllptr);

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

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

begin

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

while cur<>nil do begin < обработка c^.inf >

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

указывает cur. Обработка может состоять в:

- печати содержимого инф.части;

- модификации полей инф.части;

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

- подсчете итераций цикла при поиске по номеру;

- и т.д., и т.п. }

cur:=cur^.next; { из текущего эл-та выбирается указатель на

следующий эл-т и для следующей итерации следующий эл-т

становится текущим; если текущий эл-т был последний, то

его поле next содержит пустой указатель и, т.обр. в cur

запишется nil, что приведет к выходу из цикла при

проверке условия while }

end; end;

В двухсвязном списке возможен перебор как в прямом направле-

нии (он выглядит точно так же, как и перебор в односвязном спис-

ке), так и в обратном. В последнем случае параметром процедуры

должен быть tail - указатель на конец списка, и переход к следую-

щему элементу должен осуществляться по указателю назад:

cur:=cur^.prev;

В кольцевом списке окончание перебора должно происходить не

по признаку последнего элемента - такой признак отсутствует, а по

достижению элемента, с которого начался перебор. Алгоритмы пере-

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

самостоятельную разработку.

3Вставка элемента в список. 0 Вставка элемента в середину од-

носвязного списка показана на рис.5.4 и в примере 5.2.

 

prev

└─>┌───┬────┐ ┌───┬────┐ ┌───┬────┐

...──>│INF│NEXT┼─────x────>│INF│NEXT┼─>│INF│NEXT┼─>...

└───┴─┬──┘ ┌->└───┴────┘ └───┴────┘

| cur └---┐

| └─>┌───┬────┐ |

(2)└--->│INF│NEXT┼-┘(1)

└───┴────┘

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

 

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

{ Вставка элемента в середину 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;

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

 

prev

└>┌────┬───┬────┐ ┌────┬───┬────┐ ┌────┬───┬────┐

...──┼PREV│INF│ │<─x───┼PREV│INF│ │<┼PREV│INF│ │<─...

...─>│ │ │NEXT┼──x──>│ │ │NEXT┼>│ │ │NEXT┼─>...

└────┴───┴──┼─┘<─┐┌─>└─┼──┴───┴────┘ └────┴───┴────┘

(3)┌---┘ (4)||(1) └----┐(2)

|┌-------┘└--------┐|

|| ┌────┬───┬────┐ ||

cur |└-┼PREV│INF│ ┼─┘|

└──>└->│ │ │NEXT│<-┘

└────┴───┴────┘

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

 

Приведенные примеры обеспечивают вставку в середину списка,

но не могут быть применены для вставки в начало списка. При пос-

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

показано на рис.5.6.

ш1

head - указатель на начало

│ ┌───┬────┐ ┌───┬────┐

├─x──>│INF│NEXT┼─>│INF│NEXT┼─>...

| ┌->└───┴────┘ └───┴────┘

| └--------------┐

(2)| cur─>┌───┬────┐ |(1)

└----->│INF│NEXT┼-┘

└───┴────┘

Рис.5.6. Вставка элемента в начало 1-связного списка

Программный пример 5.3 представляет процедуру, выполняющую

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

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

{ Вставка элемента в любое место 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;

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

prev del

└>┌───┬────┐ └>┌───┬────┐ ┌───┬────┐

...─>│INF│NEXT┼x─>│INF│NEXT┼x─>│INF│NEXT┼─>...

└───┴───┬┘ └───┴────┘ ┌>└───┴────┘

└---------------┘

а). из середины

head del

│ └>┌───┬────┐ ┌───┬────┐

├──x──>│INF│NEXT┼x─>│INF│NEXT┼─>...

| └───┴────┘ ┌>└───┴────┘

└-----------------┘

б). из начала

Рис.5.7. Удаление элемента из 1-связного списка

Очевидно, что процедуру удаления легко выполнить, если из-

вестен адрес элемента, предшествующего удаляемому (prev на рис.

5.7.а). Мы, однако, на рис. 5.7 и в примере 5.4 приводим процеду-

ру для случая, когда удаляемый элемент задается своим адресом

(del на рис.5.7). Процедура обеспечивает удаления как из середи-

ны, так и из начала списка.

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

{ Удаление элемента из любого места 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^.next<>del) and (prev^.next<>nil) do

prev:=prev^.next;

if prev^.next=nil then begin { это случай, когда перебран

весь список, но эл-т не найден, он отсутствует в списке;

расценивается как ошибка (в последующих примерах этот

случай учитываться на будет) }

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

end;

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

на следующий за удаляемым }

end;

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

занимаемую им память }

Dispose(del); end;

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

большего числа указателей, как показано на рис.5.8.

del

┌-│-----------------------┐(1)

┌────┬───┬────┐<┘ └>┌────┬───┬────┐ ┌─┼──┬───┬────┐

...─>│PREV│INF│ │<──x─│PREV│INF│ │<──x─┼PREV│INF│ │<─...

...─>│ │ │NEXT┼─x──>│ │ │NEXT┼─x──>│ │ │NEXT┼─>...

└────┴───┴──┼─┘ └────┴───┴────┘ ┌>└────┴───┴────┘

└-------------------------┘(2)

Рис.5.8. Удаление элемента из 2-связного списка

 

Процедуру удаления элемента из двухсвязного списка окажется

даже проще, чем для односвязного, так как в ней не нужен поиск

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

Перестановка элементов списка. Изменчивость динамических

структур данных предполагает не только изменения размера структу-

ры, но и изменения связей между элементами. Для связных структур

изменение связей не требует пересылки данных в памяти, а только

изменения указателей в элементах связной структуры. В качестве

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

алгоритме перестановки в односвязном списке (рис.5.9, пример 5.5)

исходили из того, что известен адрес элемента, предшествующего

паре, в которой производится перестановка. В приведенном алгорит-

ме также не учитывается случай перестановки первого и второго

элементов.

 

prеv ┌─---------------------┐(2)

└─>┌───┬────┐ └>┌───┬────┐ ┌───┬───┴┐ ┌───┬────┐

...─>│INF│NEXT┼x─>│INF│NEXT┼x─>│INF│NEXT┼x─>│INF│NEXT┼─>...

└───┴───┬┘ └───┴───┬┘ ┌>└───┴────┘ ┌>└───┴────┘

(3)└------------|--┘ (1)|

└---------------┘

Рис.5.9. Перестановка соседних элементов 1-связного списка

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

{ Перестановка двух соседних элементов в 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.)

нетрудно учесть и перестановку в начале/конце списка.

Копирование части списка. При копировании исходный список

сохраняется в памяти, и создается новый список. Информационные

поля элементов нового списка содержат те же данные, что и в эле-

ментах старого списка, но поля связок в новом списке совершенно

другие, поскольку элементы нового списка расположены по другим

адресам в памяти. Существенно, что операция копирования предпола-

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

дут изменены данные в исходном списке, то изменение не будет от-

ражено в копии и наоборот.

(5)

┌────┬───┬────┐ ┌------------>┌────┬───┬────┐

...<──┼PREV│INF│ │<─┐ | ┌───┼PREV│INF│ │<─...

...──>│ │ │NEXT┼─┬│-----|----┐(1) │┌─>│ │ │NEXT┼──...

┌>└────┴───┴────┘ ││ | | ││ └─┼──┴───┴────┘

| ┌───────┘│ | | │└────|──────────┐

| │┌───────┘ | | └─────|─────────┐│

| ││┌------------|----|----------┘(2) ││

| ││└>┌────┬───┬─┼──┐ └-->┌────┬───┬────┐ ││

| │└──┼PREV│INF│ │<────┼PREV│INF│ │<─┘│

| └──>│ │ │NEXT┼────>│ │ │NEXT┼───┘

| ┌>└─┼──┴───┴────┘ ┌>└─┼──┴───┴─┼──┘

| └---|---------------|---|--------┘(6)

| (4)└---------------┘ |

└-----------------------------------┘(3)

Рис.5.10. Перестановка соседних элементов 2-связного списка

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

примере 5.6.

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

{ Копирование части 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 (cur<>nil) do begin

{ выделение памяти для эл-та выходного списка и запись в него

информационной части }

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

{ если 1-й эл-т выходного списка - запоминается указатель на

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

if prev2<>nil then prev2^.next:=cur2 else head2:=cur2;

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

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

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

end;

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

выходного списка }

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

end; end;

3Слияние двух списков. 0 Операция слияния заключается в форми-

ровании из двух списков одного - она аналогична операции сцепле-

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

5.7, слияние выполняется очень просто. Последний элемент первого

списка содержит пустой указатель на следующий элемент, этот ука-

затель служит признаком конца списка. Вместо этого пустого указа-

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

начало второго списка. Таким образом, второй список становится

продолжением первого.

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

{ Слияние двух списков. head1 и head2 - указатели на начала

списков. На результирующий список указывает head1 }

Procedure Unite (var head1, head2 : sllptr);

var cur : sllptr;

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

if head2<>nil then begin

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

if head1=nil then head1:=head2

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

begin cur:=head1;

while cur^.next<>nil do cur:=cur^.next;

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

cur^.next:=head2;

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

end; end;