Вставка элемента в цепочку
Вставка элемента в цепочку основывается на объединении отдельных звеньев в единую цепочку.
Пусть в исходную цепочку (Рисунок 7 .60) после элемента 1 необходимо вставить элемент 4.
Рисунок 7.60 – Фрагмент исходной цепочки
После вставки цепочка схематически будет выглядеть так, как изображает Рисунок 7 .61.
Рисунок 7.61 – Результат вставки элемента 4
Алгоритм вставки нового звена после заданного:
Создать новую динамическую переменную (запись типа Zveno), которой будет представленно вставляемое звено.
В поле Element этой пременной занести вставляемый элемент (символ).
В поле Adrcled этой переменной занести ссылку, взятую из поля Adrcled предшествующего звена.
В поле Adrcled предшествующего звена занести ссылку на это вставляемое звено.
Номерами 3), 4) (см. Рисунок 7 .61) обозначены действия, соответствующие третьему и четвертому этапам алгоритма.
Пример 7.6.
Процедура вставки элемента в цепочку.
Procedure Vstav (Zv: Adr; El: Char); {Zv – адрес звена, предшествующего
вставляемому}
Var
Q: Adr;
Begin
{1} New (Q);
{2} Q^.Element := El;
{3} Q^.Adrcled := Zv^.Adrcled;
{4} Zv^.Adrcled := Q
End;
Номера операторов в данном примере соответствуют номерам этапов алгоритма вставки.
Линейный однонаправленный список
Динамическая строка-цепочка является частным случаем линейного однонаправленного списка. В случае строки информационными элементами списка являются символы (тип Char). В общем случае информационными элементами списка могут быть значения любого типа – числа, массивы, записи и т.п. Принцип организации информационных элементов в список – тот же: информационный элемент очередного звена снабжается ссылкой на следующее звено.
Пример 7.7.
Определение структуры звена однонаправленного списка.
Type Adres1 = ^Zveno1;
Zveno1 = Record
Adrcled: Adres1;
Element: <Тип_элемента_списка>
End;
Элементами списка являются значения одного и того же типа.
Недостаток однонаправленного списка – по нему можно двигаться только в одном направлении, от заглавного звена к последнему звену списка. Это замедляет работу с ним.
Двунаправленные списки
Двунаправленные списки, в отличие от однонаправленных, позволяют от каждого звена двигаться по списку в любом направлении.
Каждое звено двунаправленного списка содержит два поля ссылочного типа. Значением одного поля является ссылка на последующее звено списка. Значением другого поля является ссылка на предыдущее звено списка.
Структура звена двунаправленного списка определяется описанием типа, приведенным в примере 7.8.
Пример 7.8.
Описание типа звена двунаправленного списка.
Type
Adr2 = ^Zveno2;
Zveno2 = Record
Adrcled: Adr2;
Adrpred: Adr2;
Element: <Тип элемента-списка>
End;
Схематично двунаправленный список с заглавным звеном изображает Рисунок 7 .62.
На данном рисунке «элем. i» (элемент i) представляет собой информационную часть i-ого звена.
У заглавного звена списка нет предыдущего элемента. У последнего звена списка нет последующего элемента. Поэтому в поле Adrcled последнего звена и в поле Adrpred заглавного звена двунаправленного списка должна быть пустая ссылка Nil.
На основе двунаправленного списка могут быть организованы двунаправленные кольцевые списки.
В кольцевом списке значением поля Adrcled последнего звена является ссылка на заглавное звено, значением поля Adrpred заглавного звена является ссылка на последнее звено (Рисунок 7 .63).
Рисунок 7.62 – Представление двунаправленного списка с заглавным звеном
Рисунок 7.63 – Представление двунаправленного кольцевого списка с заглавным звеном (первый способ организации кольца)
Данный рисунок отражает первый способ организации кольцевого списка. При этом способе заглавное звено списка включается в кольцо.
При втором способе способ организации кольцевого списка заглавное звено списка в кольцо не включается (Рисунок 7 .64).
Рисунок 7.64 – Представление двунаправленного кольцевого списка с заглавным звеном (второй способ организации кольца)
Достоинство первого способа организации кольцевого списка – просто реализуется вставка нового звена как в начало списка, так и в конец.
Недостаток – при циклической обработке элементов списка необходимо проверять, не является ли очередное звено заглавным звеном списка.
У второго способа организации кольцевого списка данный недостаток отсутствует, но труднее реализовывается добавление звена в конец списка.
Над двунаправленными списками определены те же три операции, что и над строкой-цепочкой:
поиск элемента в списке;
вставка элемента в указанное место списка;
удаление из списка заданного элемента.
Для работы сдвунаправленными списками необходимо использовать два указателя – на заглавное звено и на текущее звено.
Ниже рассмотрена их реализация для первого способа организации кольцевого списка.