(2) … prevInf next
Inf next
Inf next
Inf next
…
cur
(1)
Рис. 6.4. Вставка элемента в середину 1-связного списка.
Следующий пример демонстрирует реализацию этой операции.
{ Вставка элемента в середину 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;
Рисунок 6.5 представляет вставку в двухсвязный список.
(2) (1) (3) (4) cur prev … …
PREV
INF NEXT
PREV
INF NEXT
PREV
INF NEXT
PREV
INF NEXT … …
Рис. 6.5. Вставка элемента в середину 2-связного списка.
Приведенные примеры обеспечивают вставку в середину списка, но не могут быть применены для вставки в начало списка. В этом случае должен модифицироваться указатель на начало списка, как показано на рис. 6.6.
head
– указатель
на начало cur (1) (2) …Inf next
Inf next
Inf next
Рис. 6.6. Вставка элемента в начало 1-связного списка.
В примере процедура выполняет вставку элемента в любое место односвязного списка.
{ Вставка элемента в любое место 1-связного списка }
procedure InsertSll(
var
{ указатель на начало списка, может измениться в
процедуре, если head=nil - список пустой }
head: sllptr;
{ указатель на элемент, после которого делается вставка,
если prev=nil - вставка перед первым элементом }
prev: sllptr;
inf: data { данные нового элемента }
cur: sllptr); { адрес нового элемента }
begin
{ выделение памяти для нового элемента и запись его инф. части }
New(cur);
cur^.inf:=inf;
{ если есть предыдущий элемент - вставка в середину списка }
if prev <> nil then
begin
cur^.next:=prev^.next;
prev^.next:=cur;
end else
{ вставка в начало списка }
begin
{ новый элемент указывает на бывший первый элемент списка;
если head = nil, то новый элемент будет и последним элементом списка }
cur^.next:=head;
{ новый элемент становится первым в списке,
указатель на начало теперь указывает на него }
head:=cur;
end;
end;
Удаление элемента из списка. Удаление элемента из односвязного списка показано на рис. 6.7. Процедуру удаления легко выполнить, если известен адрес элемента, предшествующего удаляемому (prev на рис. 6.7. а). Однако на рис. 6.7 и в примере приводится процедура для случая, когда удаляемый элемент задается своим адресом del.
prev … INF
NEXT INF
NEXT delInf next
…
а).
del head INF
NEXT INF
NEXT …
б).
Рис. 6.7. Удаление элемента из 1-связного списка из середины списка (а) и из начала (б).
Процедура обеспечивает удаление из середины и из начала списка.
{ Удаление элемента из любого места 1-связного списка }
procedure DeleteSll(
var head: sllptr; { указатель на начало списка, может измениться в процедуре }
del: sllptr); { указатель на элемент, который удаляется }
var prev: sllptr; { адрес предыдущего элемента }
begin
{ попытка удаления из пустого списка расценивается как ошибка
(в последующих примерах этот случай учитываться не будет) }
if head = nil then
begin
Writeln('Ошибка!');
Halt;
end;
{ если удаляемый элемент - первый в списке,
то следующий за ним становится первым }
if del = head then
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;
Удаление элемента из двухсвязного списка требует коррекции большего числа указателей, как показано на рис. 6.8. Процедура удаления, чем для односвязного списка, так как в ней не нужен поиск предыдущего элемента (выбирается по указателю назад).
(1) (2) del … …
PREV
INF NEXT
PREV
INF NEXT
PREV
INF NEXT … …
Рис. 6.8. Удаление элемента из 2-связного списка.
Перестановка элементов списка.Изменчивость динамических структур предполагает не только изменения размера структуры, но и изменения связей между элементами. В качестве примера приведем перестановку двух соседних элементов списка (рис. 6.9). В алгоритме предполагается известным адрес элемента, предшествующего паре, в которой производится перестановка. В алгоритме также не учитывается случай перестановки первого и второго элементов.
