|
Циклически связанный список (сокращенно – циклический список) обладает той особенностью, что поле связи его последнего элемента не содержит значения nil, а указывает на первый узел списка. В целях удобства обработки в структуру циклического списка включают специальный узел с особым содержанием информационного поля (на рис. 29 это поле заштриховано), называемый головой списка или “сторожем”. Голова списка является дополнительным элементом. Назначение этого элемента состоит в том, чтобы отмечать точку входа в циклический список, а также упростить включение узлов в начало списка и исключение узлов из начала списка.
Выполнение условия head = nil означает, что односвязный циклический список не существует. Выполнение условия head ^. link = head означает, что односвязный циклический список существует, но является пустым, т.е. содержит только головной элемент. Пустой циклический список с головным элементом представляется структурой элементарного кольца.
Односвязные циклические списки можно использовать для реализации линейных структур, таких как очереди, стеки, списки произвольного вида. При создании очереди новый узел включается в “хвост” списка, т.е. “перед” головным элементом. При создании стека новый узел включается в начало списка, т.е. непосредственно “за” головным элементом.
Т.к. в циклическом списке каждый элемент, в том числе первый и последний, имеют предшественника и последователя (“перед” первым элементом и “за” последним элементом находится голова), все n элементов списка создаются и включаются в список одинаково (см. процедуру Create_Cikl). Каким образом включаются узлы в список при выполнении процедуры Create_Cikl: “за” головным узлом или “перед” ним? Исключение первого или последнего узла циклического списка также не имеет никаких особенностей за счет использования головного элемента. Операции включения / исключения узлов в список произвольного вида, реализованный в виде циклического списка, выполняются так же, как в нецикличесом списке.
В циклическом списке можно получить доступ к любому элементу списка, продвигаясь от произвольного элемента по кольцу. Поиск элемента по заданному условию в односвязном циклическом списке организуется в цикле, включающем операции проверки выполнения условия для текущего элемента, на который ссылается указатель, и перестановки указателя на соседний элемент. В процессе поиска используется вспомогательный указатель, который первоначально следует установить на узел, следующий за головным.
Поиск заканчивается либо при обнаружении элемента списка, соответствующего заданному условию (результатом поиска в этом случае является значение указателя, установленного на искомый узел), либо при возвращении к головному узлу после прохождения всего кольца, если элемент, соответствующий условию поиска, не обнаружен (результатом поиска в этом случае является адрес головного узла). Заметим, что в случае пустого списка цикл не выполнится ни разу.
Указатель на головной элемент циклического списка не изменяет своего значения при выполнении любых операций над элементами списка, за исключением разрушения списка. При разрушении следует освободить области памяти, занятые элементами хранения узлов списка и головного элемента, после чего список прекращает свое существование (указатель head следует установить равным NIL).
|
