Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Операции вставки и извлечения элементов из списка. Сравнение этих операций с аналогичными в массивах. Недостаток связного списка по сравнению с массивом.
Вставка и извлечение элементов из списка Cначала определяем элемент, после которого необходимо провести операцию вставки или удаления. Вставка производится с помощью функции InsAfter(P, x), а удаление - DelAfter(P). При этом рабочий указатель P должен указывать на элемент, после которого необходимо произвести вставку или удаление. Вставка Пусть необходимо вставить новый элемент с информационным полем 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
Удаление Пусть необходимо удалить элемент списка, который следует после элемента, на который указывает рабочий указатель 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.
Алгоритм 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 с.) |