В компьютерном программировании сигнальный узел - это специально назначенный узел, используемый со связанными списками и деревьями в качестве ограничителя пути обхода. Этот тип узла не содержит и не ссылается на какие-либо данные, управляемые структурой данных.
Преимущества
Стражи используются в качестве альтернативы использованию NULL
в качестве ограничителя пути, чтобы получить одно или несколько из следующих преимуществ:
- Незначительно повышенная скорость работы
- Повышенная надежность структуры данных (возможно)
Недостатки
- Незначительно увеличенная алгоритмическая сложность и размер кода.
- Если к структуре данных осуществляется одновременный доступ (что означает, что все узлы, к которым осуществляется доступ, должны быть защищены, по крайней мере, «только для чтения» ), для реализации на основе дозорного устройства дозорный узел должен быть защищен от «чтения-записи» мьютекс . Этот дополнительный мьютекс во многих сценариях использования может вызвать серьезное снижение производительности. [1] Один из способов избежать этого - защитить структуру списка в целом для «чтения-записи», тогда как в версии с
NULL
этим достаточно защитить структуру данных в целом для «только для чтения» (если операция обновления не последует). - Концепция дозорного устройства бесполезна для записи структуры данных на диск.
Примеры
Искать в связанном списке
Ниже приведены две версии подпрограммы (реализованной на языке программирования C ) для поиска заданного ключа поиска в односвязном списке . Первый использует значение дозорного NULL
, а второй (указатель на) сторожевой узел в Sentinel
качестве индикатора конца списка. Объявления структуры данных односвязного списка и результаты обеих подпрограмм одинаковы.
struct sll_node { // один узел односвязного списка struct sll_node * next ; // индикатор конца списка или -> следующий узел int key ; } sll , * первый ;
Первая версия с использованием NULL в качестве индикатора конца списка
// глобальная инициализацияfirst = NULL ; // перед первой вставкой (не показано)структура sll_node * Поиск ( структура sll_node * первый , ИНТ SEARCH_KEY ) { struct sll_node * узел ; для ( узел = первый ; узел ! = NULL ; узел = узел -> следующий ) { если ( узел -> ключ == ключ_поиска ) возвратный узел ; // нашел } // search_key отсутствует в списке: return NULL ;}
for
-Loop содержит два теста (желтые линии) за итерацию:
node != NULL;
if (node->key == search_key)
.
Вторая версия с использованием дозорного узла
Глобально доступный указатель sentinel
на специально подготовленную структуру данных Sentinel
используется как индикатор конца списка.
// глобальная переменнаяsll_node Sentinel , * sentinel = & Sentinel ;// глобальная инициализациячасовой -> следующий = дозорный ;первый = дозорный ; // перед первой вставкой (не показано)
Обратите внимание, что указатель- страж всегда должен находиться в конце списка. Это должно поддерживаться функциями вставки и удаления. Однако это примерно такое же усилие, как и при использовании указателя NULL.
структура sll_node * SearchWithSentinelnode ( структура sll_node * первый , INT SEARCH_KEY ) { структура sll_node * узел ; // Подготавливаем «узел» Sentinel к поиску: sentinel -> key = search_key ; для ( узел = первый ; узел -> ключ ! = ключ_поиска ; node = node -> следующий ) {} // Постобработка: if ( node ! = Sentinel ) return node ; // найдено // search_key не содержится в списке: return NULL ; }
for
-Loop содержит только один тест (желтая линия) на одну итерацию:
node->key != search_key;
.
Реализация в Python кругового двусвязного списка
Реализации связанного списка, особенно кругового двусвязного списка, можно значительно упростить, используя контрольный узел для разграничения начала и конца списка.
- Список начинается с единственного узла, сигнального узла, у которого есть следующий и предыдущий указатели, указывающие на самого себя. Это условие определяет, пуст ли список.
- В непустом списке следующий указатель контрольного узла дает начало списка, а предыдущий указатель дает конец списка.
Ниже приводится реализация кругового двусвязного списка на Python:
узел класса : def __init__ ( self , data , next = None , prev = None ): self . data = data self . next = следующий я . пред = пред def __repr__ ( self ) -> str : return f 'Node (data = { self . data } )'класс LinkedList : def __init__ ( self ): self . _sentinel = Node ( data = None ) self . _sentinel . следующий = себя . _sentinel self . _sentinel . prev = self . _sentinel def pop_left ( self ) -> Узел : вернуть себя . remove_by_ref ( сам . _sentinel . далее ) def pop ( self ) -> Узел : вернуть себя . remove_by_ref ( сам . _sentinel . пред. ) def append_nodeleft ( сам , узел ): сам . add_node ( сам . _sentinel , узел ) def append_node ( сам , узел ): сам . add_node ( сам . _sentinel . пред. , узел ) def append_left ( self , data ): node = Node ( data = data ) self . append_nodeleft ( узел ) def append ( self , data ): node = Node ( data = data ) self . append_node ( узел ) Защиту remove_by_ref ( самостоятельно , узел ) -> Node : если узел является самостоятельным . _sentinel : повышение Exception ( 'никогда не может удалить часовой. ) узел . пред . следующий = узел . следующий узел . следующий . пред = узел . предыдущий узел . prev = Нет узла . next = Нет возвращаемого узла def add_node ( self , curnode , newnode ): newnode . next = curnode . следующий новый узел . prev = curnode curnode . следующий . prev = newnode curnode . next = newnode def search ( self , value ): self . _sentinel . data = value node = self . _sentinel . следующий пока узел . данные ! = значение : узел = узел . следующий я . _sentinel . Данные = Отсутствует , если узел является самостоятельно . _sentinel : return None return node def __iter__ ( self ): node = self . _sentinel . Следующий в то время как узел является не сам . _sentinel : узел выхода . узел данных = узел . следующий def reviter ( сам ): узел = сам . _sentinel . предыдущий в то время как узел является не сам . _sentinel : узел выхода . узел данных = узел . предыдущий
Обратите внимание, как add_node()
метод принимает узел, который будет смещен новым узлом в параметре curnode
. Для добавления слева это голова непустого списка, а для добавления справа - хвост. Но из-за того, как настроена связь, чтобы вернуться к дозорному, код работает также и для пустых списков, где curnode
будет дозорный узел.
Искать в двоичном дереве
Общие декларации, аналогичные статье Двоичное дерево поиска :
struct bst_node { // один узел двоичного дерева поиска struct bst_node * child [ 2 ]; // каждый: -> индикатор узла или конца пути int key ; } ;struct bst { // двоичное дерево поиска struct bst_node * root ; // -> индикатор узла или конца пути } * BST ;
Глобально доступный указатель sentinel
на единственную намеренно подготовленную структуру данных Sentinel = *sentinel
используется для обозначения отсутствия дочернего элемента.
// глобальная переменнаяbst_node Sentinel , * sentinel = & Sentinel ;// глобальная инициализацияСтраж . child [ 0 ] = Страж . ребенок [ 1 ] = дозорный ;BST -> root = sentinel ; // перед первой вставкой (не показано)
Обратите внимание, что часовой указатель всегда должен представлять каждый лист дерева. Это должно поддерживаться функциями вставки и удаления. Однако это примерно такое же усилие, как и при использовании указателя NULL.
struct bst_node * SearchWithSentinelnode ( struct bst * bst , int search_key ) { struct bst_node * node ; // Подготавливаем «узел» Sentinel к поиску: часовой -> ключ = ключ_поиска ; for ( node = bst -> root ;;) { если ( search_key == node -> key ) перерыв ; если search_key < узел -> ключ : узел = узел -> дочерний [ 0 ]; // налево еще узел = узел -> дочерний [ 1 ]; // Иди направо } // Постобработка: если ( узел ! = дозорный ) возвратный узел ; // нашел // search_key не содержится в дереве: return NULL ;}
- Замечания
- При использовании SearchWithSentinelnode поиск теряет свойство R / O. Это означает, что в приложениях с параллелизмом он должен быть защищен мьютексом , что обычно превышает экономию дозорного.
- SearchWithSentinelnode не поддерживает допуск дубликатов.
- Для использования в качестве дозорного должен быть ровно один «узел», но на него может быть очень много указателей.
Смотрите также
Рекомендации
- ^ Игнатченко, Сергей (1998), "Реализации STL и безопасность потоков", Отчет C ++