Что такое сторож на языке Си?Я изучал сортировку слиянием и наткнулся на использование часового в бесконечности на этапе слияния

Question

Я изучал сортировку слиянием и наткнулся на использование часового в качестве бесконечности на этапе слияния.

Вот алгоритм из книги Кормена. Почему мы использовали бесконечность в шаге 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 («пустая строка»)), как страж.

Часовой - это просто значение, которое ваши действительные данные никогда не смогут принять.Поскольку его нельзя принять за действительное значение, ваш код может сделать «что-то особенное», когда он увидит значение часового, что-то отличное от обычной обработки, которую он будет выполнять для действительного значения.

Answer 3

В этом случае добавление бесконечности (больше любого числа) к концу каждого вложенного массива на каждом шаге рекурсии позволит избежать дополнительных сравнений в следующих случаях при объединении двух вложенных массивовпервый массив заканчивается, а второй массив остается

Или когда второй массив заканчивается и первый массив остается

нет необходимости писать дополнительную логику в обоих случаях, чтобы проверитьмассив заканчивается или нет, если закончил писать какой-то дополнительный код.