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