Методы программирования. Громов Ю.Ю - 101 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

101
которому принадлежит данная запись. Выходную последовательность,
порождённую выбором с замещением, можно получить, если лексико-
графически упорядочить эти расширенные ключи. При этом S считается
старше чем K.
В приведённом ниже алгоритме для представления дерева выбора ис-
пользуется структура данных, состоящая из Р узлов. Предполагается, что
j-й узел Х[j] содержит с слов, начинающихся с LOC(X[j]) = L
0
+ c
j при 0 ≤
j < P.
Он представляет как внутренний узел с номером j, так и концевой узел с
номером P + j (см. рис. 37). В каждом узле имеется несколько полей:
KEY – ключ, находящийся в данном концевом узле;
RECORD – запись, находящаяся в данном концевом узле (включая
KEY как подполе);
LOSER – указатель на «проигравшего» в данном внутреннем узле;
RN – номер отрезка, содержащего запись, на которую указывает
LOSER;
PE – указатель на внутренний узел, расположенный в дереве выбора
выше данного конечного узла;
PI – указатель на внутренний узел, расположенный в дереве выбора
выше данного внутреннего узла.
Например, при Р = 12 и внутренний узел с номером 5 и конечный узел
с номером 17 на рис. 37 будут представлены узлом Х[5] с полями KEY =
= 170, LOSER = L
0
+ 9c (адрес конечного узла с номером 21), PE = L
0
+ 8c,
PI = L
0
+ 2c.
Значения в полях PE и PI являются константами, и поэтому нет не-
обходимости хранить их в явном виде. Однако иногда на начальной фазе
внешней сортировки для быстрой работы с устройствами ввода/вывода
выгоднее хранить эту избыточную информацию, чем вычислять её каж-
дый раз заново.
Алгоритм R. (Выбор с замещением.)
Этот алгоритм читает записи последовательно из входного файла и
записывает их последовательно в выходной файл, производя RMAX от-
резков длиной Р или больше (за исключением последнего отрезка). Име-
ется Р ≥ 2 узлов Х[0], ..., Х[Р – 1] с полями, описанными выше.
R1. [Начальная установка.] Присвоить RMAX ← 0, RC ← 0,
LASTKEY ← ∞, Q ← LOC(X[0]) и RQ ← 0. (RC – номер текущего отрезка,
а LASTKEY – ключ последней выведенной записи. Начальное значение
LASTKEY должно быть больше любого возможного ключа.) Для 0 ≤
j < P,
если обозначить J = LOC(X[j]), начальное содержимое X[j] установить
следующим образом:
LOSER(J) ← J; RN(J) ← 0;
PE(J) ← LOC(X[
2/)( jP +
]); PI(J) ← LOC(X[
2/j
]).

Страницы