什麼是C語言的哨兵？我正在學習合併排序，並在合併步驟中使用哨兵作爲無窮大

我學習了合併排序，並在合併步驟中將sentinel用作無窮大。什麼是C語言的哨兵？我正在學習合併排序，並在合併步驟中使用哨兵作爲無窮大

這是來自Cormen的書中的算法。爲什麼我們在步驟8和9中使用了無窮大？

MERGE(A, p, q, r) 

1 n1 ← q − p + 1 

2 n2 ← r − q 

3 create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1] 

4 for i ← 1 to n1 

5 do L[i ] ← A[ p + i − 1] 

6 for j ← 1 to n2 

7 do R[ j ] ← A[q + j ] 

8 L[n1 + 1] ← ∞ 

9 R[n2 + 1] ← ∞ 

10 i ← 1 

11 j ← 1 

12 for k ← p to r 

13 do if L[i ] ≤ R[ j ] 

14 then A[k] ← L[i ] 

15 i ← i + 1 

16 else A[k] ← R[ j ] 

17 j ← j + 1

來源

2011-11-01 zedai

這不是一個c代碼??。 – obo

這只是算法...僞代碼 – zedai

甲前哨是一個僞值，使用被認爲是有值（例如用戶輸入）和控制值（值需要被特殊處理）之間進行區分。一個簡單的例子就是使用null來標記列表的末尾。

在這種特定情況下，當列表的兩半被合併回來時（例如，合併任何與無窮大相比將會更少時，使用無限簡化了比較邏輯，因此處理結束合併簡化）。

來源

2011-11-01 16:24:28

以空字符結尾的字符串也是一個很好的例子。 –

那麼爲什麼我們在這裏使用它...請解釋。我應該在c代碼中寫入什麼來代替無窮大？ – zedai

我試着解釋。如果你用C語言編寫，你可以用一個非常大的數字來表示哨兵:) –

一個定點值只是一個沒有有效值的值。

如果我的域限制爲正的非零數字，則零可以是標記。

如果我的域限制爲正數，否則我使用無符號整數，我可以使用帶符號整數和負數作爲標記。（當然，我失去了無符號範圍的上半部分來做到這一點。）

如果我使用的指針指向一個值，空指針可以是一個sentinel。

如果我使用的是一個c字符串，它是一個指針（或衰減爲指針的數組），我可以使用空指針，或者在某些情況下指向(char) 0（「空字符串」），作爲哨兵。

哨兵只是一個值，您的有效輸入永遠不會發生。由於它不會被誤認爲有效值，因此您的代碼在看到標記值時可以做「特別的事情」，而不是正常處理它爲有效值所做的事情。

來源

2011-11-01 16:27:39 tpdi

在這種情況下添加無窮大（比任何數目大）以在每一遞歸步驟的每個子陣列的端部，合併回兩個子陣列

時將避免在下列情況下，額外的comparisions當第一陣列結束和第二陣列是餘下
或者當第二陣列結束，第一陣列剩餘

無需編寫額外的邏輯在這兩種情況下，要檢查是否有任何陣列的結束與否，如果寫了一些額外的鱈魚即

來源

2013-12-03 14:46:00 pashaplus

什麼是C語言的哨兵？我正在學習合併排序，並在合併步驟中使用哨兵作爲無窮大

回答

相關問題