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


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

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



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

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

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

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

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

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

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

Q = GetNode

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

Info(Q) = x

3)Вставить полученный элемент.

Ptr(Q) = Ptr(P)

Ptr(P) = Q

Это и есть функция InsAfter(Q, X), алгоритм которой ниже

Q = GetNode

info(Q) = x

ptr(Q) = ptr(P)

ptr(P) = Q

return

 

Удаление
DelAfter(P)

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

Для этого:

1) Присваиваем Q значение указателя на удаляемый элемент.

Q = Ptr(P)

2) В переменную X сохраняем значение информационного поля удаляемого элемента.

X = Info(Q)

3) Меняем значение указателя на удаляемый элемент на значение указателя на следующий элемент и производим удаление.

Ptr(P) = Ptr(Q)

FreeNode(Q)

Это и есть процедура DelAfter(P, X), ниже записан алгоритм

Q = ptr(P)

X = info(Q)

ptr(P) = ptr(Q)

FreeNode(Q)

return

При работе с односвязным спиком доступ имеется к его началу, поэтому, для вставки или удаления любого элемента, кроме первого, необходим алгоритм просмотра односвязного списка

Алгоритм просмотра односвязного списка при вставке и удалении

Q =Nil

P = Lst

while (P <> nil) do

Q = P

P = ptr(P)

endwhile

return

 

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

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

 



Поделиться:


Последнее изменение этой страницы: 2017-02-05; просмотров: 678; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.242.165.255 (0.006 с.)