End else

Begin

Begin

Var

Begin

Begin

Begin

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

В разделе рассматриваются некоторые операции над линейными списками. Выполнение операций иллюстрируется рисунками со схемами изменения связей и программными примерами. На всех рисунках сплошными линиями показаны связи, имевшиеся до выполнения и сохранившиеся после выполнения операции, а значком 'x' отмечены связи, разорванные при выполнении операции.

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

структура информационного поля списка:

type

data = ...;

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

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

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

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

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

end;

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

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

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

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

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

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

end;

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

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

procedure LookSll(head: sllptr);

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

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

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

while cur <> nil do

< обработка c^.inf >

{ обрабатывается информационная часть

эл-та, на который указывает cur.

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

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

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

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

cur:=cur^.next;

{ из текущего элемента выбирается указатель

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

следующий элемент становится текущим; если текущий

элемент был последний, то его поле next содержит

пустой указатель и в cur запишется nil, что приведет

к выходу из цикла при проверке условия while }

end;

end;

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

cur:=cur^.prev;

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

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

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

Следующий пример демонстрирует реализацию этой операции.

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

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

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

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

{ Создание нового элемента – выделение

памяти для него и запись инф. части }

New(cur);

cur^.inf:=inf;

{ элемент, следовавший за предыдущим

теперь будет следовать за новым }

cur^.next:=prev^.next;

{ новый элемент следует за предыдущим }

prev^.next:=cur;

end;

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

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

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

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

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

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

procedure InsertSll(

{ указатель на начало списка, может измениться в

процедуре, если head=nil - список пустой }

head: sllptr;

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

если prev=nil - вставка перед первым элементом }

prev: sllptr;

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

cur: sllptr); { адрес нового элемента }

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

New(cur);

cur^.inf:=inf;

{ если есть предыдущий элемент - вставка в середину списка }

if prev <> nil then

cur^.next:=prev^.next;

prev^.next:=cur;

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