Файл: Алгоритмы и структуры данныхНовая версия для Оберона cdмосква, 2010Никлаус ВиртПеревод с английского под редакцией.pdf

2.4.4. Многофазная сортировка
Мы обсудили необходимые приемы и приобрели достаточно опыта, чтобы иссле%
довать и запрограммировать еще один алгоритм сортировки, который по произ%
водительности превосходит сбалансированную сортировку. Мы видели, что сба%
лансированные слияния устраняют операции простого копирования, которые нужны, когда операции распределения и слияния объединены в одной фазе. Воз%
никает вопрос: можно ли еще эффективней обработать последовательности. Ока%
зывается, можно. Ключом к очередному усовершенствованию является отказ от жесткого понятия проходов, то есть более изощренная работа с последователь%
ностями, нежели использование проходов с
N
источниками и с таким же числом приемников, которые в конце каждого прохода меняются местами. При этом по%
нятие прохода размывается. Этот метод был изобретен Гильстадом [2.3] и называ%
ется многофазной сортировкой.
Проиллюстрируем ее сначала примером с тремя последовательностями. В лю%
бой момент времени элементы сливаются из двух источников в третью последо%
вательность. Как только исчерпывается одна из последовательностей%источни%
ков, она немедленно становится приемником для операций слияния данных из еще не исчерпанного источника и последовательности, которая только что была принимающей.
Так как при наличии n
серий в каждом источнике получается n
серий в прием%
нике, достаточно указать только число серий в каждой последовательности (вме%
Сортировка последовательностей

Сортировка
114
сто того чтобы указывать конкретные ключи). На рис. 2.14 предполагается, что сначала есть 13 и 8 серий в последовательностях%источниках f0
и f1
соответ%
ственно. Поэтому на первом проходе 8 серий сливается из f0
и f1
в f2
, на втором проходе остальные 5 серий сливаются из f2
и f0
в f1
и т. д. В конце концов, f0
содержит отсортированную последовательность.
Рис. 2.14. Многофазная сортировка с тремя последовательностями, содержащими 21 серию
Рис. 2.15. Многофазная сортировка слиянием 65 серий с использованием 6 последовательностей
Второй пример показывает многофазный метод с 6 последовательностями.
Пусть вначале имеются 16 серий в последовательности f0
, 15 в f1
, 14 в f2
, 12 в f3
и
8 в f4
. В первом частичном проходе 8 серий сливаются на f5
. В конце концов,
f1
содержит отсортированный набор элементов (см. рис. 2.15).

115
Многофазная сортировка более эффективна, чем сбалансированная, так как при наличии
N
последовательностей она всегда реализует
N–1
%путевое слияние вместо
N/2
%путевого. Поскольку число требуемых проходов примерно равно l
og
N n
, где n
– число сортируемых элементов, а
N
– количество сливаемых серий в одной операции слияния, то идея многофазной сортировки обещает существен%
ное улучшение по сравнению со сбалансированной.
Разумеется, в приведенных примерах на%
чальное распределение серий было тщательно подобрано. Чтобы понять, как серии должны быть распределены в начале сортировки для ее правильного функционирования, будем рассуж%
дать в обратном порядке, начиная с окончатель%
ного распределения (последняя строка на рис. 2.15). Ненулевые числа серий в каждой строке рисунка (2 и 5 таких чисел на рис. 2.14 и
2.15 соответственно) запишем в виде строки таблицы, располагая по убыванию (порядок чи%
сел в строке таблицы не важен). Для рис. 2.14 и
2.15 получатся табл. 2.13 и 2.14 соответственно.
Количество строк таблицы соответствует числу проходов.
L
a
0
(L)
a
1
(L)
Sum a i
(L)
0 1
0 1
1 1
1 2
2 2
1 3
3 3
2 5
4 5
3 8
5 8
5 13 6
13 8
21
Таблица 2.13.
Таблица 2.13.
Таблица 2.13.
Таблица 2.13.
Таблица 2.13. Идеальные распределения серий в двух последовательностях
Таблица 2.14.
Таблица 2.14.
Таблица 2.14.
Таблица 2.14.
Таблица 2.14. Идеальные распределения серий в пяти последовательностях
L
a
0
(L)
a
1
(L)
a
2
(L)
a
3
(L)
a
4
(L) Sum a i
(L)
0 1
0 0
0 0
1 1
1 1
1 1
1 5
2 2
2 2
2 1
9 3
4 4
4 3
2 17 4
8 8
7 6
4 33 5
16 15 14 12 8
65
Для табл. 2.13 получаем следующие соотношения для
L > 0
:
a
1
(L+1) = a
0
(L)
a
0
(L+1) = a
0
(L) + a
1
(L)
вместе с a
0
(0) = 1
, a
1
(0) = 0
. Определяя f
i+1
= a
0
(i)
, получаем для i > 0
:
f i+1
= f i
+ f i–1
, f
1
= 1, f
0
= 0
Это в точности рекуррентное определение чисел Фибоначчи:
f = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
Сортировка последовательностей

Сортировка
116
Каждое число Фибоначчи равно сумме двух своих предшественников. Следова%
тельно, начальные числа серий в двух последовательностях%источниках должны быть двумя последовательными числами Фибоначчи, чтобы многофазная сорти%
ровка правильно работала с тремя последовательностями.
А как насчет второго примера (табл. 2.14) с шестью последовательностями?
Нетрудно вывести определяющие правила в следующем виде:
a
4
(L+1) = a
0
(L)
a
3
(L+1) = a
0
(L) + a
4
(L) = a
0
(L) + a
0
(L–1)
a
2
(L+1) = a
0
(L) + a
3
(L) = a
0
(L) + a
0
(L–1) + a
0
(L–2)
a
1
(L+1) = a
0
(L) + a
2
(L) = a
0
(L) + a
0
(L–1) + a
0
(L–2) + a
0
(L–3)
a
0
(L+1) = a
0
(L) + a
1
(L) = a
0
(L) + a
0
(L–1) + a
0
(L–2) + a
0
(L–3) + a
0
(L–4)
Подставляя f
i вместо a
0
(i)
, получаем f
i+1
= f i
+ f i–1
+ f i–2
+ f i–3
+ f i–4
для i > 4
f
4
= 1
f i
= 0 для i < 4
Это числа Фибоначчи порядка 4. В общем случае числа Фибоначчи порядка p
определяются так:
f i+1
(p) = f i
(p) + f i–1
(p) + ... + f i–p
(p) для i > p f
p
(p)
= 1
f i
(p)
= 0 для
0
≤ i < p
Заметим, что обычные числа Фибоначчи получаются для p = 1
Видим, что идеальные начальные числа серий для многофазной сортировки с
N
последовательностями суть суммы любого числа –
N–1, N–2, ... , 1
– после%
довательных чисел Фибоначчи порядка
N–2
(см. табл. 2.15).
Таблица 2.15.
Таблица 2.15.
Таблица 2.15.
Таблица 2.15.
Таблица 2.15. Числа серий, допускающие идеальное распределение
L \ N:
3 4
5 6
7 8
1 2
3 4
5 6
7 2
3 5
7 9
11 13 3
5 9
13 17 21 25 4
8 17 25 33 41 49 5
13 31 49 65 81 97 6
21 57 94 129 161 193 7
34 105 181 253 321 385 8
55 193 349 497 636 769 9
89 355 673 977 1261 1531 10 144 653 1297 1921 2501 3049 11 233 1201 2500 3777 4961 6073 12 377 2209 4819 7425 9841 12097 13 610 4063 9289 14597 19521 24097 14 987 7473 17905 28697 38721 48001

117
Казалось бы, такой метод применим только ко входным данным, в которых число серий равно сумме
N–1
таких чисел Фибоначчи. Поэтому возникает важ%
ный вопрос: что же делать, когда число серий вначале не равно такой идеальной сумме? Ответ прост (и типичен для подобных ситуаций): будем имитировать существование воображаемых пустых серий, так чтобы сумма реальных и вообра%
жаемых серий была равна идеальной сумме. Такие серии будем называть фиктив
ными (dummy).
Но этого на самом деле недостаточно, так как немедленно встает другой, более сложный вопрос: как распознавать фиктивные серии во время слияния? Прежде чем отвечать на него, нужно исследовать возникающую еще раньше проблему распределения начальных серий и решить, каким правилом руководствоваться при распределении реальных и фиктивных серий на
N–1
лентах.
Чтобы найти хорошее правило распределения, нужно знать, как выполнять слияние реальных и фиктивных серий. Очевидно, что выбор фиктивной серии из i- й последовательности в точности означает, что i- я последовательность игно%
рируется в данном слиянии, так что речь идет о слиянии менее
N–1
источников.
Слияние фиктивных серий из всех
N–1
источников означает отсутствие реальной операции слияния, но при этом в приемник нужно записать фиктивную серию.
Отсюда мы заключаем, что фиктивные серии должны быть распределены по n–1
последовательностям как можно равномернее, так как хотелось бы иметь актив%
ные слияния с участием максимально большого числа источников.
На минуту забудем про фиктивные серии и рассмотрим проблему распределе%
ния некоторого неизвестного числа серий по
N–1
последовательностям. Ясно, что числа Фибоначчи порядка
N–2
, указывающие желательное число серий в каждом источнике, могут быть сгенерированы в процессе распределения. Например,
предположим, что
N = 6
, и, обращаясь к табл. 2.14, начнем с распределения серий,
показанного в строке с индексом
L = 1 (1, 1, 1, 1, 1)
; если еще остаются серии,
переходим ко второму ряду
(2, 2, 2, 2, 1)
; если источник все еще не исчерпан,
распределение продолжается в соответствии с третьей строкой
(4, 4, 4, 3, 2)
и т. д.
Индекс строки будем называть уровнем. Очевидно, что чем больше число серий,
тем выше уровень чисел Фибоначчи, который, кстати говоря, равен числу прохо%
дов слияния или переключений приемника, которые нужно будет сделать в сор%
тировке. Теперь первая версия алгоритма распределения может быть сформули%
рована следующим образом:
1. В качестве цели распределения (то есть желаемых чисел серий) взять числа
Фибоначчи порядка
N–2
, уровня 1.
2. Распределять серии, стремясь достичь цели.
3. Если цель достигнута, вычислить числа Фибоначчи следующего уровня;
разности между ними и числами на предыдущем уровне становятся новой целью распределения. Вернуться на шаг 2. Если же цель не достигнута, хотя источник исчерпан, процесс распределения завершается.
Правило вычисления чисел Фибоначчи очередного уровня содержится в их определении. Поэтому можно сосредоточить внимание на шаге 2, где при задан%
Сортировка последовательностей

Сортировка
118
ной цели еще не распределенные серии должны быть распределены по одной в
N–1
последовательностей%приемников. Именно здесь вновь появляются фик%
тивные серии.
Пусть после повышении уровня очередная цель представлена разностями d
i
,
i = 0 ... N–2
, где d
i обозначает число серий, которые должны быть распределены в i
%ю последовательность на очередном шаге. Здесь можно представить себе, что мы сразу помещаем d
i фиктивных серий в i
%ю последовательность и рассматрива%
ем последующее распределение как замену фиктивных серий реальными, при каждой замене вычитая единицу из d
i
. Тогда d
i будет равно числу фиктивных се%
рий в i- й последовательности на момент исчерпания источника.
Неизвестно, какой алгоритм дает оптималь%
ное распределение, но очень хорошо зарекомен%
довало себя так называемое горизонтальное
распределение (см. [2.7], с. 297). Это название можно понять, если представить себе, что серии сложены в стопки, как показано на рис. 2.16 для
N = 6
, уровень
5
(ср. табл. 2.14). Чтобы как мож%
но быстрее достичь равномерного распределе%
ния остаточных фиктивных серий, последние заменяются реальными послойно слева напра%
во, начиная с верхнего слоя, как показано на рис. 2.16.
Теперь можно описать соответствующий ал%
горитм в виде процедуры select
, которая вызы%
вается каждый раз, когда завершено копирова%
ние серии и выбирается новый приемник для очередной серии. Для обозначения текущей принимающей последовательности используется переменная j
a i
и d
i обозначают соответственно идеальное число серий и число фиктивных серий для i
%й последо%
вательности.
j, level: INTEGER;
a, d: ARRAY N OF INTEGER;
Эти переменные инициализируются следующими значениями:
a i
= 1,
d i
= 1
для i = 0 ... N–2
a
N–1
= 0,
d
N–1
= 0
(принимающая последовательность)
j = 0,
level = 0
Заметим, что процедура select должна вычислить следующую строчку табл. 2.14, то есть значения a
0
(L) ... a
N–2
(L)
, при увеличении уровня. Одновременно вычисляется и очередная цель, то есть разности d
i
= a i
(L) – a i
(L–1)
. Приводимый алгоритм использует тот факт, что получающиеся d
i убывают с возрастанием ин%
декса («нисходящая лестница» на рис. 2.16). Заметим, что переход с уровня 0 на уровень 1 является исключением; поэтому данный алгоритм должен стартовать
Рис. 2.16. Горизонтальное распределение серий

119
с уровня 1. Процедура select заканчивается уменьшением d
j на 1; эта операция соответствует замене фиктивной серии в j
%й последовательности на реальную.
PROCEDURE select; (* *)
VAR i, z: INTEGER;
BEGIN
IF d[j] < d[j+1] THEN
INC(j)
ELSE
IF d[j] = 0 THEN
INC(level);
z := a[0];
FOR i := 0 TO N–2 DO
d[i] := z + a[i+1] – a[i]; a[i] := z + a[i+1]
END
END;
j := 0
END;
DEC(d[j])
END select
Предполагая наличие процедуры для копирования серии из последовательно%
сти%источника src с бегунком
R
в последовательность f
j с бегунком r
j
, мы можем следующим образом сформулировать фазу начального распределения (предпола%
гается, что источник содержит хотя бы одну серию):
REPEAT select; copyrun
UNTIL R.eof
Однако здесь следует остановиться и вспомнить о явлении, имевшем место при распределении серий в ранее обсуждавшейся сортировке естественными слияниями, а именно: две серии, последовательно попадающие в один приемник,
могут «слипнуться» в одну, так что подсчет серий даст неверный результат. Этим можно пренебречь, если алгоритм сортировки таков, что его правильность не за%
висит от числа серий. Но в многофазной сортировке необходимо тщательно от%
слеживать точное число серий в каждом файле. Следовательно, здесь нельзя пренебрегать случайным «слипанием» серий. Поэтому невозможно избежать дополнительного усложнения алгоритма распределения. Теперь необходимо удерживать ключ последнего элемента последней серии в каждой последователь%
ности. К счастью, именно это делает наша реализация процедуры
Runs
. Для при%
нимающих последовательностей поле бегунка r.first хранит последний записан%
ный элемент. Поэтому следующая попытка написать алгоритм распределения может быть такой:
REPEAT select;
IF r[j].first <= R.first THEN
€ END;
copyrun
UNTIL R.eof
Сортировка последовательностей

Сортировка
120
Очевидная ошибка здесь в том, что мы забыли, что r[j].first получает значение только после копирования первой серии. Поэтому корректное решение требует сначала распределить по одной серии в каждую из
N–1
принимающих последо%
вательностей без обращения к first
. Оставшиеся серии распределяются следую%
щим образом:
WHILE R.eof DO
select;
IF r[j].first <= R.first THEN
copyrun;
IF R.eof THEN INC(d[j]) ELSE copyrun END
ELSE
copyrun
END
END
Наконец, можно заняться главным алгоритмом многофазной сортировки. Его принципиальная структура подобна основной части программы
N
%путевого слия%
ния: внешний цикл, в теле которого сливаются серии, пока не исчерпаются источ%
ники, внутренний цикл, в теле которого сливается по одной серии из каждого ис%
точника, а также самый внутренний цикл, в теле которого выбирается начальный ключ и соответствующий элемент пересылается в выходной файл. Главные отли%
чия от сбалансированного слияния в следующем:
1. Теперь на каждом проходе вместо
N
приемников есть только один.
2. Вместо переключения
N
источников и
N
приемников после каждого прохо%
да происходит ротация последовательностей. Для этого используется косвенная индексация последовательностей при посредстве массива t
3. Число последовательностей%источников меняется от серии к серии; в нача%
ле каждой серии оно определяется по счетчикам фиктивных последова%
тельностей d
i
. Если d
i
> 0
для всех i
, то имитируем слияние
N–1
фиктивных последовательностей в одну простым увеличением счетчика d
N–1
для пос%
ледовательности%приемника. В противном случае сливается по одной се%
рии из всех источников с d
i
= 0
, а для всех остальных последовательностей d
i уменьшается, показывая, что число фиктивных серий в них уменьши%
лось. Число последовательностей%источников, участвующих в слиянии,
обозначим как k
4. Невозможно определить окончание фазы по обнаружению конца после%
довательности с номером
N–1
, так как могут понадобиться дальнейшие сли%
яния с участием фиктивных серий из этого источника. Вместо этого теоре%
тически необходимое число серий определяется по коэффициентам a
i
. Эти коэффициенты были вычислены в фазе распределения; теперь они могут быть восстановлены обратным вычислением.
Теперь в соответствии с этими правилами можно сформулировать основную часть многофазной сортировки, предполагая, что все
N–1
последовательности с начальными сериями подготовлены для чтения и что массив отображения ин%
дексов инициализирован как t
i
= i

121
REPEAT (* t[0] ... t[N–2] t[N–1]*)
z := a[N–2]; d[N–1] := 0;
REPEAT (* *)
k := 0;
(* *)
FOR i := 0 TO N–2 DO
IF d[i] > 0 THEN
DEC(d[i])
ELSE
ta[k] := t[i]; INC(k)
END
END;
IF k = 0 THEN
INC(d[N–1])
ELSE
t[0] ... t[k–1] t[N–1]
END;
DEC(z)
UNTIL z = 0;
Runs.Set(r[t[N–1]], f[t[N–1]]);
€ t;
a[i] # ;
DEC(level)
UNTIL level = 0
(* f[t[0]]*)
Реальная операция слияния почти такая же, как в сортировке
N
%путевыми слияниями, единственное отличие в том, что слегка упрощается алгоритм исклю%
чения последовательности. Ротация в отображении индексов последовательно%
стей и соответствующих счетчиков d
i
(а также перевычисление a
i при переходе на уровень вниз) не требует каких%либо ухищрений; детали можно найти в следую%
щей программе, целиком реализующей алгоритм многофазной сортировки:
PROCEDURE Polyphase (src: Files.File): Files.File;
(* ADruS24_MergeSorts *)
(* #! *)
VAR i, j, mx, tn: INTEGER;
k, dn, z, level: INTEGER;
x, min: INTEGER;
a, d: ARRAY N OF INTEGER;
t, ta: ARRAY N OF INTEGER; (* € *)
R: Runs.Rider; (* *)
f: ARRAY N OF Files.File;
r: ARRAY N OF Runs.Rider;
PROCEDURE select; (**)
VAR i, z: INTEGER;
BEGIN
IF d[j] < d[j+1] THEN
INC(j)
Сортировка последовательностей

Сортировка
122
ELSE
IF d[j] = 0 THEN
INC(level);
z := a[0];
FOR i := 0 TO N–2 DO
d[i] := z + a[i+1] – a[i]; a[i] := z + a[i+1]
END
END;
j := 0
END;
DEC(d[j])
END select;
PROCEDURE copyrun; (* src f[j]*)
BEGIN
REPEAT Runs.copy(R, r[j]) UNTIL R.eor
END copyrun;
BEGIN
Runs.Set(R, src);
FOR i := 0 TO N–2 DO
a[i] := 1; d[i] := 1;
f[i] := Files.New(""); Files.Set(r[i], f[i], 0)
END;
(* *)
level := 1; j := 0; a[N–1] := 0; d[N–1] := 0;
REPEAT
select; copyrun
UNTIL R.eof OR (j = N–2);
WHILE R.eof DO
select; (*r[j].first = , f[j]*)
IF r[j].first <= R.first THEN
copyrun;
IF R.eof THEN INC(d[j]) ELSE copyrun END
ELSE
copyrun
END
END;
FOR i := 0 TO N–2 DO
t[i] := i; Runs.Set(r[i], f[i])
END;
t[N–1] := N–1;
REPEAT (* t[0] ... t[N–2] t[N–1]*)
z := a[N–2]; d[N–1] := 0;
f[t[N–1]] := Files.New(""); Files.Set(r[t[N–1]], f[t[N–1]], 0);
REPEAT (* *)
k := 0;
FOR i := 0 TO N–2 DO
IF d[i] > 0 THEN
DEC(d[i])

123
ELSE
ta[k] := t[i]; INC(k)
END
END;
IF k = 0 THEN
INC(d[N–1])
ELSE (* t[0] ... t[k–1] t[N–1]*)
REPEAT
mx := 0; min := r[ta[0]].first; i := 1;
WHILE i < k DO
x := r[ta[i]].first;
IF x < min THEN min := x; mx := i END;
INC(i)
END;
Runs.copy(r[ta[mx]], r[t[N–1]]);
IF r[ta[mx]].eor THEN
ta[mx] := ta[k–1]; DEC(k)
END
UNTIL k = 0
END;
DEC(z)
UNTIL z = 0;
Runs.Set(r[t[N–1]], f[t[N–1]]); (* *)
tn := t[N–1]; dn := d[N–1]; z := a[N–2];
FOR i := N–1 TO 1 BY –1 DO
t[i] := t[i–1]; d[i] := d[i–1]; a[i] := a[i–1] – z
END;
t[0] := tn; d[0] := dn; a[0] := z;
DEC(level)
UNTIL level = 0 ;
RETURN f[t[0]]
END Polyphase
2.4.5. Распределение начальных серий
Необходимость использовать сложные программы последовательной сортировки возникает из%за того, что более простые методы, работающие с массивами, можно применять только при наличии достаточно большого объема оперативной памяти для хранения всего сортируемого набора данных. Часто оперативной памяти не хватает; вместо нее нужно использовать достаточно вместительные устройства хранения данных с последовательным доступом, такие как ленты или диски. Мы знаем, что развитые выше методы сортировки последовательностей практически не нуждаются в оперативной памяти, не считая, конечно, буферов для файлов и,
разумеется, самой программы. Однако даже в небольших компьютерах размер оперативной памяти, допускающей произвольный доступ, почти всегда больше,
чем нужно для разработанных здесь программ. Не суметь ее использовать опти%
мальным образом непростительно.
Сортировка последовательностей

Сортировка
124
Решение состоит в том, чтобы скомбинировать методы сортировки массивов и последовательностей. В частности, в фазе начального распределения серий мож%
но использовать вариант сортировки массивов, чтобы серии сразу имели длину
L
,
соответствующую размеру доступной оперативной памяти. Понятно, что в после%
дующих проходах слияния нельзя повысить эффективность с помощью сорти%
ровок массивов, так как длина серий только растет, и они в дальнейшем остаются больше, чем доступная оперативная память. Так что можно спокойно ограничить%
ся усовершенствованием алгоритма, порождающего начальные серии.
Естественно, мы сразу ограничим наш выбор логарифмическими методами сортировки массивов. Самый подходящий здесь метод – турнирная сортировка,
или
HeapSort
(см. раздел 2.3.2). Используемую там пирамиду можно считать фильтром, сквозь который должны пройти все элементы – одни быстрее, другие медленнее. Наименьший ключ берется непосредственно с вершины пирамиды,
а его замещение является очень эффективной процедурой. Фильтрация элемента из последовательности%источника src
(бегунок r0
) сквозь всю пирамиду
H
в при%
нимающую последовательность (бегунок r1
) допускает следующее простое опи%
сание:
Write(r1, H[0]); Read(r0, H[0]); sift(0, n–1)
Процедура sift описана в разделе 2.3.2, с ее помощью вновь вставленный эле%
мент
H
0
просеивается вниз на свое правильное место. Заметим, что
H
0
является наименьшим элементом в пирамиде. Пример показан на рис. 2.17. В итоге про%
грамма существенно усложняется по следующим причинам:
1. Пирамида
H
вначале пуста и должна быть заполнена.
2. Ближе к концу пирамида заполнена лишь частично, и в итоге она становит%
ся пустой.
3. Нужно отслеживать начало новых серий, чтобы в правильный момент из%
менить индекс принимающей последовательности j
Прежде чем продолжить, формально объявим переменные, которые заведомо нужны в процедуре:
VAR L, R, x: INTEGER;
src, dest: Files.File;
r, w: Files.Rider;
H: ARRAY M OF INTEGER; (* *)
Константа
M
– размер пирамиды
H
. Константа mh будет использоваться для обозначения
M/2
;
L и
R
суть индексы, ограничивающие пирамиду. Тогда процесс фильтрации разбивается на пять частей:
1. Прочесть первые mh ключей из src
(
r
) и записать их в верхнюю половину пирамиды, где упорядоченность ключей не требуется.
2. Прочесть другую порцию mh ключей и записать их в нижнюю половину пи%
рамиды, просеивая каждый из них в правильную позицию (построить пира%
миду).

125 3. Установить
L
равным
M
и повторять следующий шаг для всех остальных элементов в src
: переслать элемент
H
0
в последовательность%приемник.
Если его ключ меньше или равен ключу следующего элемента в исходной последовательности, то этот следующий элемент принадлежит той же се%
рии и может быть просеян в надлежащую позицию. В противном случае нужно уменьшить размер пирамиды и поместить новый элемент во вторую,
верхнюю пирамиду, которая строится для следующей серии. Границу меж%
ду двумя пирамидами указывает индекс
L
, так что нижняя (текущая) пи%
рамида состоит из элементов
H
0
... H
L–1
, а верхняя (следующая) – из
H
L
H
M–1
. Если
L = 0
, то нужно переключить приемник и снова установить
L
рав%
ным
M
4. Когда исходная последовательность исчерпана, нужно сначала установить
R
равным
M
; затем «сбросить» нижнюю часть, чтобы закончить текущую се%
рию, и одновременно строить верхнюю часть, постепенно перемещая ее в позиции
H
L
... H
R–1 5. Последняя серия генерируется из элементов, оставшихся в пирамиде.
Теперь можно в деталях выписать все пять частей в виде полной программы,
вызывающей процедуру switch каждый раз, когда обнаружен конец серии и требу%
ется некое действие для изменения индекса выходной последовательности. Вмес%
то этого в приведенной ниже программе используется процедура%«затычка», а все серии направляются в последовательность dest
Рис. 2.17. Просеивание ключа сквозь пирамиду
Сортировка последовательностей

Сортировка
126
Если теперь попытаться объединить эту программу, например, с многофазной сортировкой, то возникает серьезная трудность: программа сортировки содержит в начальной части довольно сложную процедуру переключения между последо%
вательностями и использует процедуру copyrun
, которая пересылает в точности одну серию в выбранный приемник. С другой стороны, программа
HeapSort слож%
на и использует независимую процедуру select
, которая просто выбирает новый приемник. Проблемы не было бы, если бы в одной (или обеих) программе нужная процедура вызывалась только в одном месте; но она вызывается в нескольких ме%
стах в обеих программах.
В таких случаях – то есть при совместном существовании нескольких процес%
сов – лучше всего использовать сопрограммы. Наиболее типичной является ком%
бинация процесса, производящего поток информации, состоящий из отдельных порций, и процесса, потребляющего этот поток. Эта связь типа производитель%
потребитель может быть выражена с помощью двух сопрограмм; одной из них мо%
жет даже быть сама главная программа. Сопрограмму можно рассматривать как процесс, который содержит одну или более точек прерывания (breakpoint). Когда встречается такая точка, управление возвращается в процедуру, вызвавшую со%
программу. Когда сопрограмма вызывается снова, выполнение продолжается с той точки, где оно было прервано. В нашем примере мы можем рассматривать много%
фазную сортировку как основную программу, вызывающую copyrun
, которая оформлена как сопрограмма. Она состоит из главного тела приводимой ниже про%
граммы, в которой каждый вызов процедуры switch теперь должен считаться точ%
кой прерывания. Тогда проверку конца файла нужно всюду заменить проверкой того, достигла ли сопрограмма своего конца.
PROCEDURE Distribute (src: Files.File): Files.File;
(* ADruS24_MergeSorts *)
CONST M = 16; mh = M DIV 2; (* *)
VAR L, R: INTEGER;
x: INTEGER;
dest: Files.File;
r, w: Files.Rider;
H: ARRAY M OF INTEGER; (* *)
PROCEDURE sift (L, R: INTEGER); (* *)
VAR i, j, x: INTEGER;
BEGIN
i := L; j := 2*L+1; x := H[i];
IF (j < R) & (H[j] > H[j+1]) THEN INC(j) END;
WHILE (j <= R) & (x > H[j]) DO
H[i] := H[j]; i := j; j := 2*j+1;
IF (j < R) & (H[j] > H[j+1]) THEN INC(j) END
END;
H[i] := x
END sift;
BEGIN
Files.Set(r, src, 0);

127
dest := Files.New(""); Files.Set(w, dest, 0);
(*v # 1: *)
L := M;
REPEAT DEC(L); Files.ReadInt(r, H[L]) UNTIL L = mh;
(*v # 2: € *)
REPEAT DEC(L); Files.ReadInt(r, H[L]); sift(L, M–1) UNTIL L = 0;
(*v # 3: *)
L := M;
Files.ReadInt(r, x);
WHILE r.eof DO
Files.WriteInt(w, H[0]);
IF H[0] <= x THEN
(*x € € *) H[0] := x; sift(0, L–1)
ELSE (* *)
DEC(L); H[0] := H[L]; sift(0, L–1); H[L] := x;
IF L < mh THEN sift(L, M–1) END;
IF L = 0 THEN (* ; *) L := M END
END;
Files.ReadInt(r, x)
END;
(*v # 4: € *)
R := M;
REPEAT
DEC(L); Files.WriteInt(w, H[0]);
H[0] := H[L]; sift(0, L–1); DEC(R); H[L] := H[R];
IF L < mh THEN sift(L, R–1) END
UNTIL L = 0;
(*v # 5: , *)
WHILE R > 0 DO
Files.WriteInt(w, H[0]); H[0] := H[R]; DEC(R); sift(0, R)
END;
RETURN dest
END Distribute
Анализ и выводы. Какой производительности можно ожидать от многофазной сортировки, если распределение начальных серий выполняется с помощью алго%
ритма
HeapSort
? Обсудим сначала, какого улучшения можно ожидать от введе%
ния пирамиды.
В последовательности со случайно распределенными ключами средняя длина серий равна
2
. Чему равна эта длина после того, как последовательность профиль%
трована через пирамиду размера m
? Интуиция подсказывает ответ m
, но, к счас%
тью, результат вероятностного анализа гораздо лучше, а именно
2m
(см. [2.7], раз%
дел 5.4.1). Поэтому ожидается улучшение на фактор m
Производительность многофазной сортировки можно оценить из табл. 2.15,
где указано максимальное число начальных серий, которые можно отсортировать за заданное число частичных проходов (уровней) с заданным числом последова%
тельностей
N
. Например, с шестью последовательностями и пирамидой размера
Сортировка последовательностей

Сортировка
128
m = 100
файл, содержащий до 165’680’100 начальных серий, может быть отсорти%
рован за 10 частичных проходов. Это замечательная производительность.
Рассматривая комбинацию сортировок
Polyphase и
HeapSort
, нельзя не удив%
ляться сложности этой программы. Ведь она решает ту же легко формулируемую задачу перестановки элементов, которую решает и любой из простых алгоритмов сортировки массива.
Мораль всей главы можно сформулировать так:
1. Существует теснейшая связь между алгоритмом и стуктурой обрабатывае%
мых данных, и эта структура влияет на алгоритм.
2. Удается находить изощренные способы для повышения производительно%
сти программы, даже если данные приходится организовывать в структуру,
которая плохо подходит для решения задачи (последовательность вместо массива).
Упражнения
2.1.
Какие из рассмотренных алгоритмов являются устойчивыми методами сор%
тировки?
2.2.
Будет ли алгоритм для двоичных вставок работать корректно, если в опера%
торе
WHILE
условие
L < R
заменить на
L
≤
R
? Останется ли он корректным,
если оператор
L := m+1
упростить до
L := m
? Если нет, то найти набор значе%
ний a
0
... a n–1
, на котором измененная программа сработает неправильно.
2.3.
Запрограммируйте и измерьте время выполнения на вашем компьютере трех простых методов сортировки и найдите коэффициенты, на которые нужно умножать факторы
C
и
M
, чтобы получались реальные оценки времени.
2.4.
Укажите инварианты циклов для трех простых алгоритмов сортировки.
2.5.
Рассмотрите следующую «очевидную» версию процедуры
Partition и най%
дите набор значений a
0
... a n–1
, на котором эта версия не сработает:
i := 0; j := n–1; x := a[n DIV 2];
REPEAT
WHILE a[i] < x DO i := i+1 END;
WHILE x < a[j] DO j := j–1 END;
w := a[i]; a[i] := a[j]; a[j] := w
UNTIL i > j
2.6.
Напишите процедуру, которая следующим образом комбинирует алгорит%
мы
QuickSort и
BubbleSort
: сначала
QuickSort используется для получения
(неотсортированных) сегментов длины m
(
1 < m < n
); затем для заверше%
ния сортировки используется
BubbleSort
. Заметим, что
BubbleSort может проходить сразу по всему массиву из n
элементов, чем минимизируются организационные расходы. Найдите значение m
, при котором полное время сортировки минимизируется.
Замечание. Ясно, что оптимальное значение m
будет довольно мало. Поэто%
му может быть выгодно в алгоритме
BubbleSort сделать в точности m–1
про%

129
ходов по массиву без использования последнего прохода, в котором прове%
ряется, что обмены больше не нужны.
2.7.
Выполнить эксперимент из упражнения 2.6, используя сортировку простым выбором вместо
BubbleSort
. Естественно, сортировка выбором не может ра%
ботать сразу со всем массивом, поэтому здесь работа с индексами потребует больше усилий.
2.8.
Напишите рекурсивный алгоритм быстрой сортировки так, чтобы сорти%
ровка более короткого сегмента производилась до сортировки длинного.
Первую из двух подзадач решайте с помощью итерации, для второй исполь%
зуйте рекурсивный вызов. (Поэтому ваша процедура сортировки будет со%
держать только один рекурсивный вызов вместо двух.)
2.9.
Найдите перестановку ключей
1, 2, ... , n
, для которой алгоритм
QuickSort демонстрирует наихудшее (наилучшее) поведение (
n = 5, 6, 8
).
2.10. Постройте программу естественных слияний, которая подобно процедуре простых слияний работает с массивом двойной длины с обоих концов внутрь; сравните ее производительность с процедурой в тексте.
2.11. Заметим, что в (двухпутевом) естественном слиянии, вместо того чтобы все%
гда слепо выбирать наименьший из доступных для просмотра ключей, мы поступаем по%другому: когда обнаруживается конец одной из двух серий,
хвост другой просто копируется в принимающую последовательность. На%
пример, слияние последовательностей
2, 4, 5, 1, 2, ...
3, 6, 8, 9, 7, ...
дает
2, 3, 4, 5, 6, 8, 9, 1, 2, ...
вместо последовательности
2, 3, 4, 5, 1, 2, 6, 8, 9, ...
которая кажется упорядоченной лучше. В чем причина выбора такой стра%
тегии?
2.12. Так называемое каскадное слияние (см. [2.1] и [2.7], раздел 5.4.3) – это ме%
тод сортировки, похожий на многофазную сортировку. В нем используется другая схема слияний. Например, если даны шесть последовательностей
T1
T6
, то каскадное слияние, тоже начинаясь с некоторого идеального рас%
пределения серий на
T1 ... T5
, выполняет 5%путевое слияние из
T1 ... T5
на
T6
, пока не будет исчерпана
T5
, затем (не трогая
T6
), 4%путевое слияние на
T5
, затем 3%путевое на
T4
, 2%путевое – на
T3
, и, наконец, копирование из
T1
на
T2
. Следующий проход работает аналогично, начиная с 5%путевого слия%
ния на
T1
,
и т. д. Хотя кажется, что такая схема будет хуже многофазной сортировки из%за того, что в ней некоторые последовательности иногда без%
действуют, а также из%за использования операций простого копирования,
она удивительным образом превосходит многофазную сортировку для
Упражнения

Сортировка
130
(очень) больших файлов и в случае шести и более последовательностей. На%
пишите хорошо структурированную программу на основе идеи каскадных слияний.
Литература
[2.1]
Betz B. K. and Carter. Proc. ACM National Conf. 14, (1959), Paper 14.
[2.2]
Floyd R. W. Treesort (Algorithms 113 and 243). Comm. ACM, 5, No. 8, (1962),
434, and Comm. ACM, 7, No. 12 (1964), 701.
[2.3]
Gilstad R. L. Polyphase Merge Sorting – An Advanced Technique. Proc. AFIPS
Eastern Jt. Comp. Conf., 18, (1960), 143–148.
[2.4]
Hoare C. A. R. Proof of a Program: FIND. Comm. ACM, 13, No. 1, (1970), 39–45.
[2.5]
Hoare C. A. R. Proof of a Recursive Program: Quicksort. Comp. J., 14, No. 4
(1971), 391–395.
[2.6]
Hoare C. A. R. Quicksort. Comp. J., 5. No. 1 (1962), 10–15.
[2.7]
Knuth D. E. The Art of Computer Programming. Vol. 3. Reading, Mass.: Addi%
son%Wesley, 1973 (имеется перевод: Кнут Д. Э. Искусство программирова%
ния. 2%е изд. Т. 3. – М.: Вильямс, 2000).
[2.8]
Lorin H. A Guided Bibliography to Sorting. IBM Syst. J., 10, No. 3 (1971),
244–254 (см. также Лорин Г. Сортировка и системы сортировки. – М.: На%
ука, 1983).
[2.9]
Shell D. L. A Highspeed Sorting Procedure. Comm. ACM, 2, No. 7 (1959),
30–32.
[2.10] Singleton R. C. An Efficient Algorithm for Sorting with Minimal Storage (Algo%
rithm 347). Comm. ACM, 12, No. 3 (1969), 185.
[2.11] Van Emden M. H. Increasing the Efficiency of Quicksort (Algorithm 402).
Comm. ACM, 13, No. 9 (1970), 563–566, 693.
[2.12] Williams J. W. J. Heapsort (Algorithm 232) Comm. ACM, 7, No. 6 (1964),
347–348.

1   ...   7   8   9   10   11   12   13   14   ...   22

Глава 3
Рекурсивные алгоритмы
3.1. Введение .......................... 132 3.2. Когда не следует использовать рекурсию ........... 134 3.3. Два примера рекурсивных программ ............ 137 3.4. Алгоритмы с возвратом .... 143 3.5. Задача о восьми ферзях ... 149 3.6. Задача о стабильных браках ...................................... 154 3.7. Задача оптимального выбора ..................................... 160
Упражнения ............................. 164
Литература .............................. 166

Рекурсивные алгоритмы
132
3.1. Введение
Объект называется рекурсивным, если его части определены через него самого.
Рекурсия встречается не только в математике, но и в обычной жизни. Кто не видел рекламной картинки, которая содержит саму себя?
Рис. 3.1. Рекурсивное изображение
Рекурсия особенно хорошо являет свою мощь в математических определени%
ях. Знакомые примеры – натуральные числа, древесные структуры и некоторые функции:
1. Натуральные числа:
(a) 0 является натуральным числом.
(b) Число, следующее за натуральным, является натуральным.
2. Древесные структуры:
(a)
∅ является деревом (и называется «пустым деревом»).
(b) Если t
1
и t
2
– деревья, то конструкция, состоящая из узла с двумя по%
томками t
1
и t
2
, тоже является деревом (двоичным или бинарным).
3. Факториальная функция f(n)
:
f(0) = 1
f(n) = n
×
f(n – 1)
для n > 0
Очевидно, мощь рекурсии заключается в возможности определить бесконеч%
ное множество объектов с помощью конечного утверждения. Подобным же обра%
зом бесконечное число расчетов может быть описано конечной рекурсивной программой, даже если программа не содержит явных циклов. Однако рекур%
сивные алгоритмы уместны прежде всего тогда, когда решаемая проблема, вычис%
ляемая функция или обрабатываемая структура данных заданы рекурсивным образом. В общем случае рекурсивная программа
P
может быть выражена как композиция
P
P
P
P
P
последовательности инструкций
S
(не содержащей
P
) и самой
P
:
P
≡ PPPPP[S, P]

133
Необходимое и достаточное средство для рекурсивной формулировки про%
грамм – процедура, так как она позволяет дать набору инструкций имя, с помо%
щью которого эти инструкции могут быть вызваны. Если процедура
P
содержит явную ссылку на саму себя, то говорят, что она явно рекурсивна; если
P
содержит ссылку на другую процедуру
Q
, которая содержит (прямую или косвенную) ссыл%
ку на
P
, то говорят, что
P
косвенно рекурсивна. Последнее означает, что наличие рекурсии может быть не очевидно из текста программы.
С процедурой обычно ассоциируется набор локальных переменных, констант,
типов и процедур, которые определены как локальные в данной процедуре и не существуют и не имеют смысла вне ее. При каждой рекурсивной активации про%
цедуры создается новый набор локальных переменных. Хотя у них те же имена,
что и у переменных в предыдущей активации процедуры, их значения другие,
и любая возможность конфликта устраняется правилами видимости идентифика%
торов: идентификаторы всегда ссылаются на набор переменных, созданный по%
следним. Такое же правило действует для параметров процедуры, которые по оп%
ределению связаны с ней.
Как и в случае операторов цикла, рекурсивные процедуры открывают возмож%
ность бесконечных вычислений. Следовательно, необходимо рассматривать про%
блему остановки. Очевидное фундаментальное требование состоит в том, чтобы рекурсивные вызовы процедуры
P
имели место лишь при выполнении условия
B
,
которое в какой%то момент перестает выполняться. Поэтому схема рекурсивных алгоритмов точнее выражается одной из следующих форм:
P
≡ IF B THEN PPPPP[S, P] END
P
≡ PPPPP[S, IF B THEN P END]
Основной метод доказательства остановки повторяющихся процессов состоит из следующих шагов:
1) определяется целочисленная функция f(x)
(где x
– набор переменных) –
такая, что из f(x) < 0
следует условие остановки (фигурирующее в операто%
ре while или repeat
);
2) доказывается, что f(x)
уменьшается на каждом шаге процесса.
Аналогично доказывают прекращение рекурсии: достаточно показать, что каж%
дая активация
P
уменьшает некоторую целочисленную функцию f(x)
и что f(x) < 0
влечет
B
. Особенно ясный способ гарантировать остановку состоит в том, чтобы ассоциировать передаваемый по значению параметр (назовем его n
) с процедурой
P
, и рекурсивно вызывать
P
с n–1
в качестве значения этого параметра. Тогда, под%
ставляя n > 0
вместо
B
, получаем гарантию прекращения. Это можно выразить следующими схемами:
P(n)
≡ IF n > 0 THEN PPPPP[S, P(n–1)] END
P(n)
≡ PPPPP[S, IF n > 0 THEN P(n–1) END]
В практических приложениях нужно доказывать не только конечность глуби%
ны рекурсии, но и что эта глубина достаточно мала. Причина в том, что при каж%
дой рекурсивной активации процедуры
P
используется некоторый объем опера%
Введение

Рекурсивные алгоритмы
134
тивной памяти для размещения ее локальных переменных. Кроме того, нужно за%
помнить текущее состояние вычислительного процесса, чтобы после окончания новой активации
P
могла быть возобновлена предыдущая. Мы уже встречали та%
кую ситуацию в процедуре
QuickSort в главе 2. Там было обнаружено, что при наивном построении программы из операции, которая разбивает n
элементов на две части, и двух рекурсивных вызовов сортировки для двух частей глубина ре%
курсии может в худшем случае приближаться к n
. Внимательный анализ позво%
лил ограничить глубину величиной порядка l og(n)
. Разница между n
и log(n)
дос%
таточно существенна, чтобы превратить ситуацию, в которой рекурсия в высшей степени неуместна, в такую, где рекурсия становится вполне практичной.
3.2. Когда не следует использовать
рекурсию
Рекурсивные алгоритмы особенно хорошо подходят для тех ситуаций, когда ре%
шаемая задача или обрабатываемые данные определены рекурсивно. Однако на%
личие рекурсивного определения еще не означает, что рекурсивный алгоритм даст наилучшее решение. Именно попытки объяснять понятие рекурсивного ал%
горитма с помощью неподходящих примеров стали главной причиной широко распространенного предубеждения против использования рекурсии в програм%
мировании, а также мнения о неэффективности рекурсии.
Программы, в которых следует избегать использования алгоритмической рекурсии, характеризуются определенной структурой. Для них характерно нали%
чие единственного вызова
P
в конце (или в начале) композиции (так называемая
концевая рекурсия):
P
≡ IF B THEN S; P END
P
≡ S; IF B THEN P END
Такие схемы естественно возникают в тех случаях, когда вычисляемые значе%
ния определяются простыми рекуррентными соотношениями. Возьмем извест%
ный пример факториала f
i
= i!
:
i
= 0, 1, 2, 3, 4, 5, ...
f i
= 1, 1, 2, 6, 24, 120, ...
Первое значение определено явно: f
0
= 1
, а последующие – рекурсивно через предшествующие:
f i+1
= (i+1) * f i
Это рекуррентное соотношение наводит на мысль использовать рекурсивный алгоритм для вычисления n
%го факториала. Если ввести две переменные
I
и
F
для обозначения значений i
и f
i на i
%м уровне рекурсии, то переход к следующим чле%
нам пары последовательностей для i
и f
i требует такого вычисления:
I := I + 1; F := I * F

135
Подставляя эту пару инструкций вместо
S
, получаем рекурсивную программу
P
≡ IF I < n THEN I := I + 1; F := I * F; P END
I := 0; F := 1; P
В принятой нами нотации первая строка выражается следующим образом:
PROCEDURE P;
BEGIN
IF I < n THEN I := I + 1; F := I*F; P END
END P
Чаще используется эквивалентная форма, данная ниже.
P
заменяется процеду%
рой%функцией
F
, то есть процедурой, с которой явно ассоциируется вычисляемое значение и которая может поэтому быть использована как непосредственная со%
ставная часть выражений. Тогда переменная
F
становится лишней, а роль
I
берет на себя явно задаваемый параметр процедуры:
PROCEDURE F(I: INTEGER): INTEGER;
BEGIN
IF I > 0 THEN RETURN I * F(I – 1) ELSE RETURN 1 END
END F
Ясно, что в этом примере рекурсия может быть довольно легко заменена итера%
цией. Это выражается следующей программой:
I := 0; F := 1;
WHILE I < n DO I := I + 1; F := I*F END
В общем случае программы, построенные по обсуждаемым частным рекурсив%
ным схемам, следует переписывать в соответствии со следующим образцом:
P
≡ [x := x0; WHILE B DO S END]
Существуют и более сложные рекурсивные композиционные схемы, которые могут и должны приводиться к итеративному виду. Пример – вычисление чисел
Фибоначчи, определенных рекуррентным соотношением fib n+1
= fib n
+ fib n–1
для n > 0
и соотношениями fib
1
= 1
, fib
0
= 0
. Непосредственный наивный перевод на язык программирования дает следующую рекурсивную программу:
PROCEDURE Fib (n: INTEGER): INTEGER;
VAR res: INTEGER;
BEGIN
IF n = 0 THEN res := 0
ELSIF n = 1 THEN res := 1
ELSE res := Fib(n–1) + Fib(n–2)
END;
RETURN res
END Fib
Когда не следует использовать рекурсию

Рекурсивные алгоритмы
136
Вычисление fib n
с помощью вызова
Fib(n)
вызывает рекурсивные активации этой процедуры%функции. Сколько происходит таких активаций? Очевидно, каж%
дый вызов с n > 1
приводит к двум дальнейшим вызовам, то есть полное число вы%
зовов растет экспоненциально (см. рис. 3.2). Такая программа явно непрактична.
Рис. 3.2. Пятнадцать активаций при вызове
Fib(5)
К счастью, числа Фибоначчи можно вычислять по итерационной схеме без многократного вычисления одних и тех же значений благодаря использованию вспомогательных переменных – таких, что x = fib i
и y = fib i–1
i := 1; x := 1; y := 0;
WHILE i < n DO z := x; x := x + y; y := z; i := i + 1 END
Отметим, что три присваивания переменным x
, y
, z
можно заменить всего лишь двумя присваиваниями без привлечения вспомогательной переменной z
:
x := x + y;
y := x – y
Отсюда мораль: следует избегать рекурсии, когда есть очевидное решение,
использующее итерацию. Но это не значит, что от рекурсии нужно избавляться любой ценой. Как будет показано в последующих разделах и главах, существует много хороших применений рекурсии. Тот факт, что имеются реализации рекур%
сивных процедур на принципиально нерекурсивных машинах, доказывает, что любая рекурсивная программа действительно может быть преобразована в чисто итерационную. Но тогда требуется явно управлять стеком рекурсии, и это часто затемняет сущность программы до такой степени, что понять ее становится весь%
ма трудно. Отсюда вывод: алгоритмы, которые по своей природе являются рекур%
сивными, а не итерационными, должны программироваться в виде рекурсивных процедур. Чтобы оценить это обстоятельство, полезно сравнить два варианта ал%
горитма быстрой сортировки в разделе 2.3.3: рекурсивный (
QuickSort
) и нерекур%
сивный (
NonRecursiveQuickSort
).
Оставшаяся часть главы посвящена разработке некоторых рекурсивных про%
грамм в ситуациях, когда применение рекурсии оправдано. Кроме того, в главе 4
рекурсия широко используется в тех случаях, когда соответствующие структуры данных делают выбор рекурсивных решений очевидным и естественным.

137
3.3. Два примера рекурсивных программ
Симпатичный узор на рис. 3.4 представляет собой суперпозицию пяти кривых.
Эти кривые являют регулярность структуры, так что их, вероятно, можно изобра%
зить на дисплее или графопостроителе под управлением компьютера. Наша цель –
выявить рекурсивную схему, с помощью которой можно написать программу для рисования этих кривых. Можно видеть, что три из пяти кривых имеют вид, пока%
занный на рис. 3.3; обозначим их как
H
1
,
H
2
и
H
3
. Кривая
H
i называется гильберто
вой кривой порядка i
в честь математика Гильберта (D. Hilbert, 1891).
Рис. 3.3. Гильбертовы кривые порядков 1, 2 и 3
Каждая кривая
H
i состоит из четырех копий кривой
H
i–1
половинного размера,
поэтому мы выразим процедуру рисования
H
i в виде композиции четырех вызовов для рисования
H
i–1
половинного размера и с соответствующими поворотами. Для целей иллюстрации обозначим четыре по%разному повернутых варианта базовой кривой как
A
,
B
,
C
и
D
, а шаги рисования соединительных линий обозначим стрел%
ками, направленными соответственно. Тогда возникает следующая рекурсивная схема (ср. рис. 3.3):
A:
D
←
A
↓
A
→
B
B:
C
↑
B
→
B
↓
A
C:
B
→
C
↑
C
←
D
D:
A
↓
D
←
D
↑
C
Предположим, что для рисования отрезков прямых в нашем распоряжении есть процедура line
, которая передвигает чертящее перо в заданном направлении на заданное расстояние. Для удобства примем, что направление указывается целочисленным параметром i
, так что в градусах оно равно
45
×
i
. Если длину от%
резков, из которых составляется кривая, обозначить как u
, то процедуру, соответ%
ствующую схеме
A
, можно сразу выразить через рекурсивные вызовы аналогич%
ных процедур
B
и
D
и ее самой:
PROCEDURE A (i: INTEGER);
BEGIN
IF i > 0 THEN
D(i–1); line(4, u);
A(i–1); line(6, u);
Два примера рекурсивных программ

Рекурсивные алгоритмы
138
A(i–1); line(0, u);
B(i–1)
END
END A
Эта процедура вызывается в главной программе один раз для каждой гильбер%
товой кривой, добавляемой в рисунок. Главная программа определяет начальную точку кривой, то есть начальные координаты пера, обозначенные как x0
и y0
,
а также длину базового отрезка u
. Квадрат, в котором рисуются кривые, помеща%
ется в середине страницы с заданными шириной и высотой. Эти параметры, так же как и рисующая процедура line
, берутся из модуля
Draw
. Отметим, что этот модуль помнит текущее положение пера.
DEFINITION Draw;
(* ADruS33_Draw *)
CONST width = 1024; height = 800;
PROCEDURE Clear; (* *)
PROCEDURE SetPen(x, y: INTEGER); (* x, y*)
PROCEDURE line(dir, len: INTEGER);
(* len dir*45 # ;
(*
# *)
END Draw.
Процедура
Hilbert рисует гильбертовы кривые
H
1
... H
n
. Она рекурсивно использует четыре процедуры
A
,
B
,
C
и
D
:
VAR u: INTEGER;
(* ADruS33_Hilbert *)
PROCEDURE A (i: INTEGER);
BEGIN
IF i > 0 THEN
D(i–1); Draw.line(4, u); A(i–1); Draw.line(6, u); A(i–1); Draw.line(0, u); B(i–1)
END
END A;
PROCEDURE B (i: INTEGER);
BEGIN
IF i > 0 THEN
C(i–1); Draw.line(2, u); B(i–1); Draw.line(0, u); B(i–1); Draw.line(6, u); A(i–1)
END
END B;
PROCEDURE C (i: INTEGER);
BEGIN
IF i > 0 THEN
B(i–1); Draw.line(0, u); C(i–1); Draw.line(2, u); C(i–1); Draw.line(4, u); D(i–1)
END
END C;
PROCEDURE D (i: INTEGER);
BEGIN
IF i > 0 THEN
A(i–1); Draw.line(6, u); D(i–1); Draw.line(4, u); D(i–1); Draw.line(2, u); C(i–1)
END
END D;

139
PROCEDURE Hilbert (n: INTEGER);
CONST SquareSize = 512;
VAR i, x0, y0: INTEGER;
BEGIN
Draw.Clear;
x0 := Draw.width DIV 2; y0 := Draw.height DIV 2;
u := SquareSize; i := 0;
REPEAT
INC(i); u := u DIV 2;
x0 := x0 + (u DIV 2); y0 := y0 + (u DIV 2);
Draw.Set(x0, y0);
A(i)
UNTIL i = n
END Hilbert.
Похожий, но чуть более сложный и эстетически изощренный пример показан на рис. 3.6. Этот узор тоже получается наложением нескольких кривых, две из ко%
торых показаны на рис. 3.5.
S
i называется кривой Серпиньского порядка i
. Какова ее рекурсивная структура? Есть соблазн в качестве основного строительного бло%
ка взять фигуру
S
1
, возможно, без одного ребра. Но так решение не получится.
Главное отличие кривых Серпиньского от кривых Гильберта – в том, что первые замкнуты (и не имеют самопересечений). Это означает, что базовой рекурсивной схемой должна быть разомкнутая кривая и что четыре части соединяются связка%
ми, не принадлежащими самому рекурсивному узору. В самом деле, эти связки состоят из четырех отрезков прямых в четырех самых внешних углах, показанных жирными линиями на рис. 3.5. Их можно считать принадлежащими непустой на%
чальной кривой
S
0
, представляющей собой квадрат, стоящий на одном из углов.
Теперь легко сформулировать рекурсивную схему. Четыре узора, из которых со%
ставляется кривая, снова обозначим как
A
,
B
,
C
и
D
, а линии%связки будем рисовать явно. Заметим, что четыре рекурсивных узора действительно идентичны, отлича%
ясь поворотами на 90 градусов.
Вот базовая схема кривых Серпиньского:
S: A
B C D
А вот схема рекурсий (горизонтальные и вертикальные стрелки обозначают линии двойной длины):
A: A
B → D A
B: B
C ↓ A B
C: C
D ← B C
D: D
A ↑ C D
Если использовать те же примитивы рисования, что и в примере с кривыми
Гильберта, то эта схема рекурсии легко превращается в рекурсивный алгоритм
(с прямой и косвенной рекурсиями).
Два примера рекурсивных программ

Рекурсивные алгоритмы
140
Рис. 3.4. Гильбертовы кривые
H
1
… H
5
Рис. 3.5. Кривые Серпиньского
S
1
и
S
2

141
PROCEDURE A (k: INTEGER);
BEGIN
IF k > 0 THEN
A(k–1); Draw.line(7, h); B(k–1); Draw.line(0, 2*h);
D(k–1); Draw.line(1, h); A(k–1)
END
END A
Эта процедура реализует первую строку схемы рекурсий. Процедуры для узо%
ров
B
,
C
и
D
получаются аналогично. Главная программа составляется по базовой схеме. Ее назначение – установить начальное положение пера и определить длину единичной линии h
в соответствии с размером рисунка. Результат выполнения этой программы для n = 4
показан на рис. 3.6.
VAR h: INTEGER;
(* ADruS33_Sierpinski *)
PROCEDURE A (k: INTEGER);
BEGIN
IF k > 0 THEN
A(k–1); Draw.line(7, h); B(k–1); Draw.line(0, 2*h);
D(k–1); Draw.line(1, h); A(k–1)
END
END A;
PROCEDURE B (k: INTEGER);
BEGIN
IF k > 0 THEN
B(k–1); Draw.line(5, h); C(k–1); Draw.line(6, 2*h);
A(k–1); Draw.line(7, h); B(k–1)
END
END B;
PROCEDURE C (k: INTEGER);
BEGIN
IF k > 0 THEN
C(k–1); Draw.line(3, h); D(k–1); Draw.line(4, 2*h);
B(k–1); Draw.line(5, h); C(k–1)
END
END C;
PROCEDURE D (k: INTEGER);
BEGIN
IF k > 0 THEN
D(k–1); Draw.line(1, h); A(k–1); Draw.line(2, 2*h);
C(k–1); Draw.line(3, h); D(k–1)
END
END D;
PROCEDURE Sierpinski* (n: INTEGER);
CONST SquareSize = 512;
VAR i, x0, y0: INTEGER;
BEGIN
Два примера рекурсивных программ

Рекурсивные алгоритмы
142
Draw.Clear;
h := SquareSize DIV 4;
x0 := Draw.width DIV 2; y0 := Draw.height DIV 2 + h;
i := 0;
REPEAT
INC(i); x0 := x0-h;
h := h DIV 2; y0 := y0+h; Draw.Set(x0, y0);
A(i); Draw.line(7,h); B(i); Draw.line(5,h);
C(i); Draw.line(3,h); D(i); Draw.line(1,h)
UNTIL i = n
END Sierpinski.
Элегантность приведенных примеров убеждает в полезности рекурсии. Пра%
вильность получившихся программ легко установить по их структуре и по схемам композиции. Более того, использование явного (и уменьшающегося) параметра уровня гарантирует остановку, так как глубина рекурсии не может превысить n
Напротив, эквивалентные программы, не использующие рекурсию явно, оказыва%
ются весьма громоздкими, и понять их нелегко. Читатель легко убедится в этом,
если попытается разобраться в программах, приведенных в [3.3].
Рис. 3.6. Кривые Серпиньского
S
1
… S
4

143

1   ...   8   9   10   11   12   13   14   15   ...   22

3.4. Алгоритмы с возвратом
Весьма интригующее направление в программировании – поиск общих методов решения сложных зачач. Цель здесь в том, чтобы научиться искать решения конк%
ретных задач, не следуя какому%то фиксированному правилу вычислений, а мето%
дом проб и ошибок. Общая схема заключается в том, чтобы свести процесс проб и ошибок к нескольким частным задачам. Эти задачи часто допускают очень естест%
венное рекурсивное описание и сводятся к исследованию конечного числа подза%
дач. Процесс в целом можно представлять себе как поиск%исследование, в ко%
тором постепенно строится и просматривается (с обрезанием каких%то ветвей)
некое дерево подзадач. Во многих задачах такое дерево поиска растет очень быст%
ро, часто экспоненциально, как функция некоторого параметра. Трудоемкость поиска растет соответственно. Часто только использование эвристик позволяет обрезать дерево поиска до такой степени, чтобы сделать вычисление сколь%ни%
будь реалистичным.
Обсуждение общих эвристических правил не входит в наши цели. Мы сосредо%
точимся в этой главе на общем принципе разбиения задач на подзадачи с приме%
нением рекурсии. Начнем с демонстрации соответствующей техники в простом примере, а именно в хорошо известной задаче о путешествии шахматного коня.
Пусть дана доска n
×
n с n
2
полями. Конь, который передвигается по шахмат%
ным правилам, ставится на доске в поле
, y0>
. Задача – обойти всю доску, если это возможно, то есть вычислить такой маршрут из n
2
–1
ходов, чтобы в каждое поле доски конь попал ровно один раз.
Очевидный способ упростить задачу обхода n
2
полей – рассмотреть подзадачу,
которая состоит в том, чтобы либо выполнить какой%либо очередной ход, либо обнаружить, что дальнейшие ходы невозможны. Эту идею можно выразить так:
PROCEDURE TryNextMove; (* *)
BEGIN
IF
THEN
;
WHILE

Глава 4
Динамические структуры
данных
4.1. Рекурсивные типы данных ..................................... 168 4.2. Указатели ......................... 170 4.3. Линейные списки .............. 175 4.4. Деревья ............................ 191 4.5. Сбалансированные деревья ................................... 210 4.6. Оптимальные деревья поиска ..................................... 220 4.7. Б<деревья (BУпражнения ............................. 250
Литература .............................. 254

Динамические структуры данных
168
4.1. Рекурсивные типы данных
В главе 1 массивы, записи и множества были введены в качестве фундаменталь%
ных структур данных. Мы назвали их фундаментальными, так как они являются строительными блоками, из которых формируются более сложные структуры,
а также потому, что на практике они встречаются чаще всего. Смысл определения типа данных, а затем определения переменных, имеющих этот тип, состоит в том,
чтобы раз и навсегда фиксировать диапазон значений этих переменных, а значит,
и способ их размещения в памяти. Поэтому такие переменные называют стати
ческими. Однако есть много задач, где нужны более сложные структуры данных.
Для таких задач характерно, что не только значения, но и структура переменных меняется во время вычисления. Поэтому их называют динамическими структура
ми. Естественно, компоненты таких структур – на определенном уровне разреше%
ния – являются статическими, то есть принадлежат одному из фундаментальных типов данных. Эта глава посвящена построению, анализу и работе с динамиче%
скими структурами данных.
Надо заметить, что существуют близкие аналогии между методами структури%
рования алгоритмов и данных. Эта аналогия, как и любая другая, не является пол%
ной, тем не менее сравнение методов структурирования программ и данных по%
учительно.
Элементарный неделимый оператор – присваивание значения некоторой пе%
ременной. Соответствующий член семейства структур данных – скалярный, не%
структурированный тип. Эта пара представляет собой неделимые строительные блоки для составных операторов и для типов данных. Простейшие структуры,
получаемые посредством перечисления, суть последовательность операторов и запись. И та, и другая состоят из конечного (обычно небольшого) числа явно пе%
речисленных компонент, которые все могут быть различными. Если все компо%
ненты идентичны, то их не обязательно выписывать по отдельности: в этом случае используют оператор for и массив, чтобы указать известное, конечное число по%
вторений. Выбор между двумя или более элементами выражается условным опе%
ратором и расширением записевых типов соответственно. И наконец, повторение с заранее неизвестным (и потенциально бесконечным) числом шагов выражается операторами while и repeat
. Соответствующая структура данных – последова%
тельность (файл) – это простейшее средство для построения типов с бесконечной мощностью.
Возникает вопрос: существует ли структура данных, которая аналогичным образом соответствовала бы оператору процедуры? Естественно, в этом отно%
шении самым интересным и новым свойством процедур является рекурсия.
Значения такого рекурсивного типа данных должны содержать одну или более компонент, принадлежащих этому же типу, подобно тому как процедура может содержать один или более вызовов самой себя. Как и процедуры, определения ти%
пов данных могли бы быть явно или косвенно рекурсивными.
Простой пример объекта, который весьма уместно представлять рекурсивно определенным типом, – арифметическое выражение, имеющееся в языках про%

169
граммирования. Рекурсия используется, чтобы отразить возможность вложений,
то есть использования подвыражений в скобках в качестве операндов выражений.
Поэтому дадим следующее неформальное определение выражения:
Выражение состоит из терма, за которым следует знак операции, за которым следует терм. (Два этих терма – операнды операции.) Терм – это либо перемен%
ная, представленная идентификатором, либо выражение, заключенное в скобки.
Тип данных, значениями которого представляются такие выражения, может быть легко описан, если использовать уже имеющиеся средства, добавив к ним рекурсию:
TYPE expression = RECORD op: INTEGER;
opd1, opd2: term
END
TYPE term =
RECORD
IF t: BOOLEAN THEN id: Name ELSE subex: expression END
END
Поэтому каждая переменная типа term состоит из двух компонент, а именно поля признака t
, а также, если t
истинно, поля id
, или в противном случае поля subex
. Например, рассмотрим следующие четыре выражения:
1.
x + y
2.
x – (y * z)
3.
(x + y) * (z – w)
4.
(x/(y + z)) * w
Эти выражения схематически показаны на рис. 4.1, где видна их «матрешечная»,
рекурсивная структура, а также показано размещение этих выражений в памяти.
Второй пример рекурсивной структуры данных – семейная родословная.
Пусть родословная определена именем индивида и двумя родословными его ро%
дителей. Это определение неизбежно приводит к бесконечной структуре. Реаль%
ные родословные ограничены, так как о достаточно далеких предках информация отсутствует. Снова предположим, что это можно учесть с помощью некоторой условной структуры (
ped от pedigree – родословная):
TYPE ped = RECORD
IF known: BOOLEAN THEN name: Name; father, mother: ped END
END
Заметим, что каждая переменная типа ped имеет по крайней мере одну компо%
ненту, а именно поле признака known
(известен). Если его значение равно
TRUE
,
то есть еще три поля; в противном случае эти поля отсутствуют. Пример конкрет%
ного значения показан ниже в виде выражения с вложениями, а также с помощью диаграммы, показывающей возможное размещение в памяти (см. рис. 4.2).
(T, Ted, (T, Fred, (T, Adam, (F), (F)), (F)), (T, Mary, (F), (T, Eva, (F), (F)))
Понятно, почему важны условия в таких определениях: это единственное средство ограничить рекурсивную структуру данных, поэтому они обязательно
Рекурсивные типы данных

Динамические структуры данных
170
Рис. 4.1. Схемы расположения в памяти рекурсивных записевых структур
Рис. 4.2. Пример рекурсивной структуры данных сопровождают каждое рекурсивное определе%
ние. Здесь особенно четко видна аналогия между структурированием программ и данных. Услов%
ный оператор (или оператор выбора) обяза%
тельно должен быть частью каждой рекурсивной процедуры, чтобы обеспечить завершение ее вы%
полнения. На практике динамические структу%
ры используют ссылки или указатели на свои элементы, а идея альтернативы (для завершения рекурсии) реализуется в понятии указателя, как объясняется в следующем разделе.
4.2. Указатели
Характерное свойство рекурсивных структур,
четко отличающее их от фундаментальных струк%
тур (массивов, записей, множеств), – это их спо%
собность менять свой размер. Поэтому невозмож%
но выделить фиксированный участок памяти для размещения рекурсивно определенной структу%
ры, и, как следствие, компилятор не может свя%
зать конкретные адреса с компонентами таких переменных. Метод, чаще всего применяемый для решения этой проблемы, состоит в динами

171
ческом распределении памяти (dynamic allocation of storage), то есть распределе%
нии памяти отдельным компонентам в тот момент, когда они возникают при вы%
полнения программы, а не во время трансляции. При этом компилятор отводит фиксированный объем памяти для хранения адреса динамически размещаемой компоненты вместо самой компоненты. Например, родословная, показанная на рис. 4.2, будет представлена отдельными – вполне возможно, несмежными – за%
писями, по одной на каждого индивида. Эти записи для отдельных людей связаны с помощью адресов, записанных в соответствующие поля father
(отец) и mother
(мать). Графически это лучше всего выразить с помощью стрелок или указателей
(рис. 4.3).
Рис. 4.3. Структура данных, связанная указателями
Важно подчеркнуть, что использование указателей для реализации рекурсив%
ных структур – это всего лишь технический прием. Программисту не обязательно знать об их существовании. Память может распределяться автоматически в тот момент, когда в первый раз используется ссылка на новую компоненту. Но если явно разрешается использование указателей, то можно построить и более общие структуры данных, чем те, которые можно описать с помощью рекурсивных опре%
делений. В частности, тогда можно определять потенциально бесконечные или циклические структуры (графы) и указывать, что некоторые структуры исполь%
зуются совместно. Поэтому в развитых языках программирования принято разре%
шать явные манипуляции не только с данными, но и со ссылками на них. Это тре%
бует проведения четкого различия на уровне обозначений между данными и ссылками на данные, а также необходимость иметь типы данных, значениями ко%
торых являются указатели (ссылки) на другие данные. Мы будем использовать следующую нотацию для этой цели:
TYPE T = POINTER TO T0
Такое определение типа означает, что значения типа
T
– это указатели на дан%
ные типа
T0
. Принципиально важно, что тип элементов, на которые ссылается
Указатели

Динамические структуры данных
172
указатель, очевиден из определения
T
. Мы говорим, что
T
связан с
T0
. Эта связь отличает указатели в языках высокого уровня от адресов в машинном языке и яв%
ляется весьма важным средством повышения безопасности в программировании посредством отражения семантики программы синтаксическими средствами.
Значения указательных типов порождаются при каждом динамическом разме%
щении элемента данных. Мы будет придерживаться правила, что такое событие всегда должно описываться явно, в противоположность механизму автоматичес%
кого размещения элемента данных при первой ссылке на него. С этой целью вве%
дем процедуру
NEW
. Если дана указательная переменная p
типа
T
, то оператор
NEW(p)
размещает где%то в памяти переменную типа
T0
, а указатель на эту новую переменную записывает в переменную p
(см. рис. 4.4). Сослаться в программе на само указательное значение теперь можно с помощью p
(то есть это значение ука%
зательной переменной p
). При этом переменная, на которую ссылается p
, обозна%
чается как p^
. Обычно используют ссылки на записи. Если у записи, на которую ссылается указатель p
, есть, например, поле x
, то оно обозначается как p^.x
. По%
скольку ясно, что полями обладает не указатель, а только запись p^
, то мы допус%
каем сокращенную нотацию p.x вместо p^.x
Рис. 4.4. Динамическое размещение переменной p^
Выше указывалось, что в каждом рекурсивном типе необходима компонента,
позволяющая различать возможные варианты, чтобы можно было обеспечить ко%
нечность рекурсивных структур. Пример семейной родословной показывает весь%
ма часто встречающуюся ситуацию, когда в одном из двух случаев другие компо%
ненты отсутствуют. Это выражается следующим схематическим определением:
TYPE T = RECORD
IF nonterminal: BOOLEAN THEN S(T) END
END
S(T)
обозначает последовательность определений полей, среди которых есть одно или более полей типа
T
, чем и обеспечивается рекурсивность. Все структуры типа, определенного по этой схеме, имеют древесное (или списковое) строение,
подобное показанному на рис. 4.3. Его особенность – наличие указателей на ком%
поненты данных, состоящие только из поля признака, то есть не несущие другой полезной информации. Метод реализации с явными укзателями подсказывает простой способ сэкономить память, разрешив включать информацию о поле при%

173
знака в само указательное значение. Обычно для этого расширяют диапазон значе%
ний всех указательных типов единственным значением, которое вообще не являет%
ся ссылкой ни на какой элемент. Обозначим это значение специальным символом
NIL
и постулируем, что все переменные указательных типов могут принимать зна%
чение
NIL
. Вследствие такого расширения диапазона указательных значений ко%
нечные структуры могут порождаться при отсутствии вариантов (условий) в их
(рекурсивных) определениях.
Ниже даются новые формулировки объявленных ранее явно рекурсивных ти%
пов данных с использованием указателей. Заметим, что здесь уже нет поля known
,
так как
p.known теперь выражается посредством p = NIL
. Переименование типа ped в
Person
(индивид) отражает изменение точки зрения, произошедшее благо%
даря введению явных указательных значений. Теперь вместо того, чтобы сначала рассматривать данную структуру целиком и уже потом исследовать ее подструк%
туры и компоненты, внимание сосредоточивается прежде всего на компонентах,
а их взаимная связь (представленная указателями) не фиксирована никаким яв%
ным определением.
TYPE term =
POINTER TO TermDescriptor;
TYPE exp =
POINTER TO ExpDescriptor;
TYPE ExpDescriptor =
RECORD op: INTEGER; opd1, opd2: term END;
TYPE TermDescriptor = RECORD id: ARRAY 32 OF CHAR END
TYPE Person =
POINTER TO RECORD
name: ARRAY 32 OF CHAR;
father, mother: Person
END
Замечание. Тип
Person соответствует указателям на записи безымянного типа
(
PersonDescriptor
).
Структура данных, представляющая родословную и показанная на рис. 4.2 и 4.3,
снова показана на рис. 4.5, где указатели на неизвестных лиц обозначены констан%
той
NIL
. Получающаяся экономия памяти очевидна.
В контексте рис. 4.5 предположим, что
Fred и
Mary
– брат и сестра, то есть у них общие отец и мать. Эту ситуацию легко выразить заменой двух значений
NIL
в соответствующих полях двух записей. Реализация, которая скрывает указатели
Рис. 4.5. Структура данных с указателями, имеющими значение
NIL
Указатели

Динамические структуры данных
174
или использует другие приемы работы с памятью, заставила бы программиста представить записи для родителей, то есть
Adam и
Eva
, дважды. Хотя для чтения данных не важно, одной или двумя записями представлены два отца (или две ма%
тери), разница становится существенной, когда разрешено частичное изменение данных. Трактовка указателей как явных элементов данных, а не как скрытых средств реализации, позволяет программисту четко указать, где нужно совмес%
тить используемые блоки памяти, а где – нет.
Другое следствие явных указателей – возможность определять и манипулиро%
вать циклическими структурами данных. Разумеется, такая дополнительная гиб%
кость не только предоставляет дополнительные возможности, но и требует от программиста повышенного внимания, поскольку работа с циклическими струк%
турами данных легко может привести к бесконечным процессам.
Эта тесная связь мощи и гибкости средств с опасностью их неправильного использования хорошо известна в программировании и заставляет вспомнить оператор
GOTO
. В самом деле, если продолжить аналогию между структурами программ и данных, то чисто рекурсивные структуры данных можно сопоста%
вить с процедурами, а введение указателей сравнимо с операторами
GOTO
. Ибо как оператор
GOTO
позволяет строить любые программные схемы (включая циклы), так и указатели позволяют строить любые структуры данных (включая кольцевые). [Однако в отличие от операторов
GOTO
, типизированные указатели не нарушают структурированности соответствующих записей – прим. перев.]
Параллели между структурами управления и структурами данных суммирова%
ны в табл. 4.1.
Таблица 4.1.
Таблица 4.1.
Таблица 4.1.
Таблица 4.1.
Таблица 4.1. Соответствия структур управления и структур данных
Схема построения
Схема построения
Схема построения
Схема построения
Схема построения
Оператор программы
Оператор программы
Оператор программы
Оператор программы
Оператор программы
Тип данных
Тип данных
Тип данных
Тип данных
Тип данных
Неделимый элемент
Присваивание
Скалярный тип
Перечисление
Операторная
Запись последовательность
Повторение (число
Оператор for
Массив повторений известно)
Выбор
Условный оператор
Объединение типов
(запись с вариантами)
Повторение
Оператор while или
Последовательностный тип repeat
Рекурсия
Процедура
Рекурсивный тип данных
Общий граф
Оператор перехода
Структура, связанная указателями
В главе 3 мы видели, что итерация является частным случаем рекурсии и что вы%
зов рекурсивной процедуры
P
, определенной в соответствии со следующей схемой,
PROCEDURE P;
BEGIN
IF B THEN P0; P END
END

175
где оператор
P0
не включает в себя
P
и может быть заменен на эквивалентный опе%
ратор цикла
WHILE B DO P0 END
Аналогии, представленные в табл. 4.1, подсказывают, что похожая связь долж%
на иметь место между рекурсивными типами данных и последовательностью.
В самом деле, рекурсивный тип, определенный в соответствии со схемой
TYPE T = RECORD
IF b: BOOLEAN THEN t0: T0; t: T END
END
где тип
T0
не имеет отношения к
T
, может быть заменен на эквивалентную после%
довательность элементов типа
T0
Остальная часть этой главы посвящена созданию и работе со структурами дан%
ных, компоненты которых связаны с помощью явных указателей. Особое внима%
ние уделяется конкретным простым схемам; из них можно понять, как работать с более сложными структурами. Такими простыми схемами являются линейный список (простейший случай) и деревья. Внимание, которое мы уделяем этим средствам структурирования данных, не означает, что на практике не встречают%
ся более сложные структуры. Следующий рассказ, опубликованный в цюрихской газете в июле 1922 г., доказывает, что странности могут встречаться даже в тех случаях, которые обычно служат образцами регулярных структур, таких как (генеа%
логические) деревья. Мужчина жалуется на свою жизнь следующим образом:
Я женился на вдове, у которой была взрослая дочь. Мой отец, который часто
нас навещал, влюбился в мою приемную дочь и женился на ней. Таким образом, мой
отец стал моим зятем, а моя приемная дочь стала моей мачехой. Через несколько
месяцев моя жена родила сына, который стал сводным братом моему отцу и моим
дядей. Жена моего отца, то есть моя приемная дочь, тоже родила сына, который
стал мне братом и одновременно внуком. Моя жена стала мне бабушкой, так как
она мать моей мачехи. Следовательно, я муж моей жены и в то же время ее прием
ный внук; другими словами, я сам себе дедушка.

1   ...   10   11   12   13   14   15   16   17   ...   22