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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

91
и в этом случае лексикографическое отношение порядка соответствует
обычному упорядочению множества неотрицательных чисел. Ключи
также могут быть цепочками букв алфавита и т.д.
Во время сортировки формируется М «стопок», которые фактически
представляют собой очереди, поскольку они всегда просматриваются по
принципу «первым включается – первым исключается». Для каждой
стопки имеется два указателя: TOP[i] и BOTM[i], 0 ≤ i < M.
R1. [Цикл по k.] Вначале установить P ← LOC(R
N
) – указатель на
последнюю запись. Затем выполнить шаги с R2 по R6 при k = 1, 2, …, p
(шаги с R2 по R6 составляют один «просмотр») и завершить работу алго-
ритма. Переменная P будет указывать на запись с наименьшим ключом,
LINK(P) – на запись со следующим по величине ключом, LINK(LINK(P)) –
на следующую и т.д. Поле LINK последней записи будет равно Λ.
R2. [Очистка стопок.] При 0 ≤ i < M установить TOP[i] ← Λ и
BOTM [i] ← Λ.
R3. [Выделение k-й цифры ключа.] Пусть KEY(P) – ключ записи, на
которую указывает P, и равен (a
p
,
…, a
2
, a
1
). Присвоить i ← a
k
(k-я млад-
шая цифра этого ключа).
R4. [Коррекция связей.] Если BOTM[i] = Λ, то BOTM[i] ← P и
TOP[i] ← P; иначе LINK (TOP[i]) ← P и затем TOP[i] ← P.
R5. [Переход к следующей записи.] Если k = 1 (первый просмотр) и
если Р = LOC(R
j
) при некотором j ≠ 1, то присвоить P ← LOC(R
j–1
)
и вернуться к шагу R3. Если k > 1 (не первый просмотр), то присвоить
P ← LINK(P) и если P ≠ Λ, то вернуться к шагу R3.
R6. [Вызов алгоритма H.] (Теперь все элементы уже распределены
по стопкам.) Выполнить приведённый ниже алгоритм Н, который сцеп-
ляет отдельные «стопки» в один список, подготавливая их к следующему
просмотру. Затем выполнить P ← BOTM[0] – указатель на первый эле-
мент объединённого списка. ■
Алгоритм Н. (Сцепление очередей.) Из М данных очередей со свя-
зями, удовлетворяющими соглашениям алгоритма R, данный алгоритм
создаёт одну очередь, меняя при этом не более чем М связей. В результа-
те BOTM[0] указывает на первый элемент, и стопка 0 предшествует стоп-
ке 1, …, стопка (М – 2) предшествует стопке (М – 1).
Н1. [Начальная установка.] Присвоить i ← 0.
Н2. [Указатель на вершину стопки.] Выполнить P ← TOP[i].
Н3. [Следующая стопка.] Увеличить i на 1. Если i = М, то присвоить
LINK(P) ← Λ и конец алгоритма.
Н4. [Стопка пуста?] Если BOTM[i] = Λ, то вернуться к шагу Н3.
Н5. [Сцепить стопки.] Присвоить LINK(P) ← BOTM[i] и вернуться к
шагу Н2. ■

Страницы