什么是C语言中的sentinel？我正在学习合并排序，并且在合并步骤中遇到了使用sentinel作为无穷大的问题

Question

我正在学习合并排序，并在合并步骤中遇到了使用sentinel作为无穷大的问题。

这是科尔曼的书中的算法。为什么我们在第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

Answer 1

标记是一个虚拟值，用于区分应该存在的值(例如用户输入)和控制值(需要特殊处理的值)。一个简单的例子是使用null到null来标记列表的结尾。

在这种特定情况下，当列表的两部分被合并回一起时，无穷大的使用简化了比较逻辑(例如，当合并任何与无穷大相比要少的东西时，因此合并结束的处理被简化了)。

Answer 2

标记值只是一个没有有效值的值。

如果我的域被限制为正的非零数，零可以是一个前哨。

如果我的域被限制为正数，否则我将使用无符号整数，我可以使用有符号整数和负数作为标记。(当然，我失去了unsigned范围的上半部分。)

如果我使用一个指针指向一个值，空指针可以是一个标记。

如果我使用c字符串，它是一个指针(或衰减为指针的数组)，我可以使用空指针，或者在某些情况下，指向(char) 0 (“空字符串”)作为标记。

sentinel只是一个值，即您的有效输入永远不能接受。因为它不会被误认为是有效值，所以当您的代码看到该标记值时，它可以做一些“特殊的事情”，而不是对有效值所做的正常处理。

Answer 3

在这种情况下，在每个递归步骤中将无穷大(大于任何数字)添加到每个子数组的末尾，将避免在合并回两个子数组时在以下情况下进行额外的比较

• 当第一个阵列结束而第二个阵列仍为
• 时，或者当第二个阵列结束但第一个阵列仍为

时

在这两种情况下，都不需要编写额外的逻辑来检查是否有任何数组结束，如果结束，则编写一些额外的代码。