TaiwanTonguesApiRobot：從 JSON 檔案批量匯入

2025-09-23T09:19:45Z

從 JSON 檔案批量匯入

新頁面

在電腦程式設計中，哨兵節點（sentinel node）是一種特殊指定的節點，在鏈結串列和樹中用作遍歷路徑的終止符。此類節點不持有或引用該資料結構所管理的任何資料。

==優點==

哨兵節點被用來替代 `NULL` 作為路徑終止符，以獲得以下一個或多個好處：
* 略微提升操作速度
* 提升資料結構的穩健性（有爭議）

==缺點==
* 略微增加記憶體用量，尤其是在鏈結串列很短時。

== 範例 ==

=== 在鏈結串列中搜尋 ===
以下是兩個用於在單向鏈結串列中查找給定搜尋鍵的子程式版本（以 C 程式語言實作）。第一個版本使用哨兵值 `NULL`，第二個版本使用（指向）哨兵節點 `Sentinel` 的指標，作為串列結尾的指示符。兩種子程式的單向鏈結串列資料結構宣告和結果都是相同的。

<syntaxhighlight lang="c">
struct sll_node { // 單向鏈結串列的一個節點
struct sll_node *next; // 串列結尾指示符或 -> 下一個節點
int key;

</syntaxhighlight>

==== 第一個版本，使用 NULL 作為串列結尾指示符 ====
<syntaxhighlight lang="c" line highlight="7,10">
// 全域初始化
first = NULL; // 在首次插入前（未顯示）

struct sll_node *Search(struct sll_node *first, int search_key) {
struct sll_node *node;
for (node = first;
node != NULL;
node = node->next)

if (node->key == search_key)
return node; // 找到

// search_key 不包含在串列中：
return NULL;

</syntaxhighlight>
`for` 迴圈的每次迭代包含兩個測試（黃色標示行）：
* `node != NULL;`
* `if (node->key == search_key)`。

==== 第二個版本，使用哨兵節點 ====
全域可用的指標 `sentinel` 指向特意準備的資料結構 `Sentinel`，並被用作串列結尾指示符。
<syntaxhighlight lang="c" line>
// 全域變數
sll_node Sentinel, *sentinel = &Sentinel;
// 全域初始化
sentinel->next = sentinel;
first = sentinel; // 在首次插入前（未顯示）
</syntaxhighlight>
請注意，`sentinel` 指標必須始終保持在串列的末端。
這必須由插入和刪除函式來維護。然而，這與使用 NULL 指標所需的功夫大致相同。

<syntaxhighlight lang="c" highlight="6">
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;

</syntaxhighlight>
`for` 迴圈的每次迭代只包含一個測試（黃色標示行）：
* `node->key != search_key;`。

==== Python 的環狀雙向鏈結串列實作 ====
鏈結串列的實作，特別是環狀雙向鏈結串列，可以透過使用哨兵節點來標記串列的開頭和結尾，從而顯著簡化。

* 串列始於一個單一節點，即哨兵節點，其 `next` 和 `previous` 指標都指向自身。此條件可用於判斷串列是否為空。
* 在非空串列中，哨兵節點的 `next` 指標指向串列的頭部，而 `previous` 指標則指向串列的尾部。

以下是 Python 的環狀雙向鏈結串列實作：

<syntaxhighlight lang="python">
class Node:
def __init__(self, data, next=None, prev=None):
self.data = data
self.next = next
self.prev = prev

def __repr__(self) -> str:
return f'Node(data={self.data})'

class LinkedList:
def __init__(self):
self._sentinel = Node(data=None)
self._sentinel.next = self._sentinel
self._sentinel.prev = self._sentinel

def pop_left(self) -> Node:
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):
node = Node(data=data)
self.append_node(node)

def remove_by_ref(self, node) -> Node:
if node is self._sentinel:
raise Exception('Can never remove 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
if node is self._sentinel:
return None
return node

def __iter__(self):
node = self._sentinel.next
while node is not self._sentinel:
yield node.data
node = node.next

def reviter(self):
node = self._sentinel.prev
while node is not self._sentinel:
yield node.data
node = node.prev
</syntaxhighlight>

請注意 `add_node()` 方法如何將會被新節點取代的節點作為參數 `curnode` 傳入。當在左側附加時，此節點是非空串列的頭部；而在右側附加時，則是尾部。但由於鏈結的設定方式會指回哨兵節點，因此這段程式碼對於空串列同樣有效，此時 `curnode` 會是哨兵節點。

=== 在二元樹中搜尋 ===
一般宣告，類似於二元搜尋樹的文章：
<syntaxhighlight lang="c">
struct bst_node { // 二元搜尋樹的一個節點
struct bst_node *child[2]; // 每個：->node 或結尾路徑指示符
int key;

struct bst { // 二元搜尋樹
struct bst_node *root; // ->node 或結尾路徑指示符

</syntaxhighlight>

全域可用的指標 `sentinel` 指向單一特意準備的資料結構 `Sentinel = *sentinel`，用來指示子節點不存在。
<syntaxhighlight lang="c" line highlight="12">
// 全域變數
bst_node Sentinel, *sentinel = &Sentinel;
// 全域初始化
Sentinel.child[0] = Sentinel.child[1] = sentinel;

BST->root = sentinel; // 在首次插入前（未顯示）
</syntaxhighlight>
請注意，`sentinel` 指標必須始終代表樹中的每一個葉節點。
這必須由插入和刪除函式來維護。然而，這與使用 NULL 指標所需的功夫大致相同。

<syntaxhighlight lang="c" line="11">
struct bst_node *SearchWithSentinelnode(struct bst *bst, int search_key) {
struct bst_node *node;
// 為搜尋準備「節點」Sentinel：
sentinel->key = search_key;

for (node = bst->root;;) {
if (search_key == node->key)
break;
if search_key < node->key:
node = node->child[0]; // 向左
else
node = node->child[1]; // 向右

// 後續處理：
if (node != sentinel)
return node; // 找到
// search_key 不包含在樹中：
return NULL;

</syntaxhighlight>

;備註：
# 使用 `SearchWithSentinelnode` 會使搜尋失去其唯讀屬性。這意味著在有並行處理的應用程式中，它必須受到互斥鎖（mutex）的保護，這種額外開銷通常會超過使用哨兵節點所節省的效益。
# `SearchWithSentinelnode` 不支援處理重複值。
# 必須有且僅有一個「節點」用作哨兵，但可以有極多個指標指向它。

== 參見 ==
* 金絲雀值 (Canary value)
* 開羅的大象 (Elephant in Cairo)
* 衛述句 (電腦科學) (Guard (computer science))，一個布林表達式，若程式要繼續在該分支中執行，則此表達式必須為真
* 魔法數字 (程式設計) (Magic number (programming))
* 魔法字串 (Magic string)
* 空物件模式 (Null object pattern)
* 半謂詞問題 (Semipredicate problem)
* 哨兵值 (Sentinel value)
* 時間格式化與儲存錯誤 (Time formatting and storage bugs)

==參考資料==

[[分類: 待校正]]

前哨節點 - 修訂紀錄

TaiwanTonguesApiRobot：​從 JSON 檔案批量匯入

TaiwanTonguesApiRobot：從 JSON 檔案批量匯入