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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

102
(Установка LOSER(J) и RN(J) представляет собой искусственный
способ образования начального дерева путём рассмотрения фиктивного
отрезка с номером 0, который никогда не выводится.)
R2. [Конец отрезка?] Если RQ = RC, то перейти к шагу R3. (В про-
тивном случае RQ = RC + 1, и обработка отрезка с номером RC завершена.
Здесь следует выполнить те специальные действия, которые соответствуют
схеме слияния для последующих этапов сортировки.) Если RQ > RMAX, то
алгоритм завершён; в противном случае присвоить RC ← RQ.
R3. [Вывод вершины дерева.] (Сейчас Q указывает на «чемпиона» и
RQ – номер его отрезка.) Если RQ ≠ 0, то вывести RECORD(Q) и присво-
ить LASTKEY ← KEY(Q).
R4. [Ввод новой записи.] Если входной файл исчерпан, присвоить
RQ ← RMAX + 1 и перейти к шагу R5. В противном случае поместить
новую запись из входного файла в RECORD(Q). Если KEY(Q) < LASTKEY
(т.е. эта запись не принадлежит текущему отрезку), то RQ ← RQ + 1, и
теперь, если RQ > RMAX, присвоить RMAX ← RQ.
R5. [Подготовка к изменению.] (Сейчас Q указывает на новую за-
пись с номером отрезка RQ.) Присвоить T ← PE(Q). (T – переменный
указатель, который будет двигаться по дереву.)
R6. [Установка нового проигравшего.] Если RN(T) < RQ или если
RN(T) = RQ и KEY(LOSER(T)) < KEY(Q), то поменять местами LOSER(T) ↔ Q,
RN(T) ↔ RQ. (В переменных Q и RQ запоминается текущий победитель и
номер его отрезка.)
R7. [Сдвиг вверх.] Если T = LOC(X[1]), то вернуться к шагу R2; в
противном случае T ← PI(T) и вернуться к шагу R6. ■
В алгоритме R говорится о вводе и выводе записей по одной, тогда
как практически оказывается лучше читать и записывать относительно
большие блоки записей. Следовательно, на самом деле необходимы бу-
феры ввода и вывода. Отметим, что их присутствие в памяти приводит к
уменьшению значения Р.
Упражнения
1. С помощью алгоритма R выбора с замещением (для Р = 4) уста-
новите образуемые в выходном файле отрезки, если во входном файле
находится последовательность из шестнадцати записей с ключами:
а) 79, 69, 4, 25, 64, 87, 13, 94, 3, 20, 16, 15, 30, 44, 9, 72;
б) 77, 92, 42, 94
1
, 74, 96, 88, 56, 94
2
, 45, 55, 40, 36, 37, 22, 5;
в) 3, 64, 34, 61, 32, 98, 12, 65, 21, 73, 35, 82, 38, 81, 54, 69.

Страницы