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