Сначала определяем элемент, после которого необходимо вставить элемент в список. Вставка производится с помощью процедуры InsAfter(P, x), а удаление - DelAfter(P).
При этом рабочий указатель P будет указывать на элемент, после которого необходимо произвести вставку или удаление (рис 3.9).
Пусть необходимо вставить новый элемент с информационным полем x после элемента, на который указывает рабочий указатель P.
Для этого:
1) Необходимо сгенерировать новый элемент.
Q = GetNode
2) Информационному полю этого элемента присвоить значение x.
Info(Q) = x
3) Вставить полученный элемент.
Ptr(Q) = Ptr(P)
Ptr(P) = Q
Окончательно алгоритм функции InsAfter(P,x) будет следующий:
Q = GetNode
info(Q) = x
ptr(Q) = ptr(P)
ptr(P) = Q
return
Пусть необходимо удалить элемент списка, который следует после элемента, на который указывает рабочий указатель P.
Для этого:
1) Присваиваем Q значение указателя на удаляемый элемент.
Q = Ptr(P)
2) В переменную x сохраняем значение информационного поля удаляемого элемента.
X = Info(Q)
3) Меняем значение указателя на удаляемый элемент на значение указателя на следующий элемент и производим удаление .
Ptr(P) = Ptr(Q)
FreeNode(Q)
Окончательно алгоритм функции DelAfter(P) будет следующий:
Q = ptr(P)
X = info(Q)
ptr(P) = ptr(Q)
FreeNode(Q)
return
Для вставки или удаления элемента в списке (не первого) необходимо совершить «проход» по списку до элемента, после которого осуществляется вставка или удаление. Данную операцию называют просмотром односвязного списка при вставке или удалении. Без данной операции невозможно осуществлять работу со списком, соответственно для нее необходим алгоритм.
Обозначим через P - рабочий указатель; в начале просмотра P = Lst.
Введем также указатель Q, который отстает на один элемент от P ; в начале просмотра Q = nil.
Когда указатель P получит значение nil , цикл просмотра заканчивается.
Алгоритм просмотра односвязного списка при вставке и удалении следующий:
Q =Nil
P = Lst
while (P <> nil) do
Q = P
P = ptr(P)
endwhile
return
Примеры типичных операций над списками
Задача 1.
Требуется просмотреть список и удалить элементы, у которых информационные поля равны 4.
Обозначим P - рабочий указатель, в начале просмотра P = Lst. Введем также указатель Q, который отстает на один элемент от P. Когда указатель P найдет элемент, последний будет удален относительно указателя Q как последующий элемент.
Алгоритм решения данной конкретной задачи следующий:
x = 4
Q = nil
P = Lst
while P <> nil do
if info(P) = x then
if Q = nil then
Pop(Lst)
P = Lst
else
DelAfter(Q) endif
else
Q = P
P = Ptr(P)
endif
endwhile
return
Задача 2.
Дан упорядоченный по возрастанию Info - полей список. Необходимо вставить в этот список элемент со значением x, не нарушив упорядоченности списка.
Пусть x = 16. Начальное условие: Q = Nil, P = Lst. Вставка элемента должна произойти между 3 и 4 элементом (рис.3.10).
Алгоритм решения данной задачи следующий:
X = 16
Q =Nil
P = Lst
while (P <> nil) and (X > info(P)) do
Q = P
P = Ptr(P)
endwhile
if Q = nil then
Push(Lst, X)
endif
InsAfter ( Q , X )
return
Дата: 2019-12-10, просмотров: 278.
