Операции вставки и извлечения элементов из списка. Сравнение этих операций с аналогичными в массивах. Недостаток связного списка по сравнению с массивом.

↑

▷ Содержание

⇐ ПредыдущаяСтр 9 из 15Следующая ⇒

▷ Похожие статьи

Вставка и извлечение элементов из списка

Cначала определяем элемент, после которого необходимо провести операцию вставки или удаления.

Вставка производится с помощью функции InsAfter(P, x), а удаление - DelAfter(P).

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

Вставка
InsAfter(P, x)

Пусть необходимо вставить новый элемент с информационным полем x после элемента, на который указывает рабочий указатель P.

1)Необходимо сгенерировать новый элемент.

Q = GetNode

2)Информационному полю этого элемента присвоить значение X.

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

Требуется просмотреть список и удалить элементы, у которых информационные поля равны 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

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

Дан упорядоченный по возрастанию info - полей список. Необходимо вставить в этот список элемент со значением X, не нарушив упорядоченности списка.

Пусть X = 16

Начальные условия:

Q = Nil, P = Lst

Алгоритм

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

Познавательные статьи:



Коммуникативные барьеры и пути их преодоления

Рынок недвижимости. Сущность недвижимости

Решение задач с использованием генеалогического метода

История происхождения и развития детской игры