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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

81
а) постройте полное бинарное дерево с 16 ячейками (без всяких
бесполезных ячеек, содержащих «–
∞») и расположите ключи в соответ-
ствующих ячейках;
б) выполните по алгоритму H пирамидальную сортировку этих
ключей, прослеживая изменения, происходящие в построенном бинарном
дереве.
14. СОРТИРОВКА СЛИЯНИЕМ
Слияние означает объединение двух или более упорядоченных под-
файлов в один упорядоченный файл. Можно, например, слить два под-
файла – 503 703 765 и 87 512 677, получив 87 503 512 677 703 765. Про-
стой способ сделать это – сравнить наименьшие элементы подфайлов,
вывести в файл наименьший из них и повторить эту процедуру.
Начав с
67751287
765703503
,
получим
87
677512
765703503
.
Затем
87 503
677512
765703
и т.д. Заметим, что при этом необходимо позаботиться о действиях на
случай, когда исчерпается один из подфайлов.
Весь процесс слияния подробно описан в следующем алгоритме.
Алгоритм М. (Двухпутевое слияние.)
Этот алгоритм осуществляет слияние двух упорядоченных подфай-
лов x
1
≤ x
2
≤ … ≤ x
m
и y
1
≤ y
2
≤ … ≤ y
n
в один файл z
1
≤ z
2
≤ … ≤ z
m+n
.
М1. [Начальная установка.] Установить i ← 1, j ← 1, k ← 1.
М2. [Найти наименьший элемент.] Если x
i
≤ y
j
, то перейти к шагу
М3; в противном случае – к шагу М5.
М3. [Вывести x
i
.] Установить z
k
← x
i
, k ← k + 1, i ← i + 1. Если i ≤ m,
то вернуться к шагу М2.
M4. [Вывести y
j
, …, y
n
.] Установить (z
k
, …, z
m+n
) ← (y
j
, …, y
n
) и за-
вершить работу алгоритма.
М5. [Вывести y
j
.] Установить z
k
← y
j
, k ← k + 1, j ← j + 1. Если j ≤ n,
то вернуться к шагу М2.
М6. [Вывести x
i
, …, x
m
.] Установить (z
k
, …, z
m+n
) ← (x
i
, …, x
m
) и за-
вершить работу алгоритма. ■

Страницы