Род Стивенс

Delphi
Готовые алгоритмы

Readytorun
Delphi®

Algorithms

Rod Stephens

JOHN WILEY & SONS, INC.

New York • Chichester • Weinheim • Brisbane • Singapore • Toronto

WILEY COMPUTER PUBLISHING

Delphi

Готовые

алгоритмы

Род Стивенс

Серия «Для программистов»

Москва

УДК 004.438Delphi
ББК 32.973.26018.1

С80

Стивенс Р.

С80
Delphi. Готовые алгоритмы: Пер. с англ. – М.: ДМК Пресс. – 384 с.: ил.
(Серия «Для программистов»).

ISBN 5940741061

Программирование всегда было достаточно сложной задачей. Эта кни

га поможет вам легко преодолеть возникающие трудности с помощью биб
лиотеки мощных алгоритмов, полностью реализованных в исходном коде
Delphi. Вы узнаете, как выбрать способ, наиболее подходящий для реше
ния конкретной задачи, и как добиться максимальной производительнос
ти вашего приложения. Рассматриваются типичные и наихудшие случаи
реализации алгоритмов, что позволит вам вовремя распознать возможные
трудности и при необходимости переписать или заменить часть программы.
Подробно описываются важнейшие элементы алгоритмов хранения и обра
ботки данных (списки, стеки, очереди, деревья, сортировка, поиск, хеши
рование и т.д.). Приводятся не только традиционные решения, но и мето
ды, основанные на последних достижениях объектноориентированного
программирования.

Книга предназначена для начинающих программистов на Delphi, но

благодаря четкой структуризации материала и богатой библиотеке готовых
алгоритмов будет также интересна и специалистам.

ББК 32.973.26018.1

All Rights Reserved. Authorized translation from the English language edition published by

John Wiley & Sons, Inc.

Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы

то ни было форме и какими бы то ни было средствами без письменного разрешения владель
цев авторских прав.

Материал, изложенный в данной книге, многократно проверен. Но, поскольку вероятность

технических ошибок все равно существует, издательство не может гарантировать абсолютную
точность и правильность приводимых сведений. В связи с этим издательство не несет ответ
ственности за возможные ошибки, связанные с использованием книги.

ISBN 0471254002 (англ.)
      © By Rod Stephens. Published by John Wiley

ISBN 5940741061 (рус.)
     © Перевод на русский язык, оформление.

& Sons, Inc.

          ДМК Пресс

Содержание

Введение ......................................................................................... 12

Глава 1. Основные понятия ................................................ 18

Что такое алгоритмы ................................................................ 18
Анализ скорости выполнения алгоритмов .......................... 19

Память или время ........................................................................ 19

Оценка с точностью до порядка ................................................... 20

Определение сложности ............................................................. 21

Сложность рекурсивных алгоритмов ........................................... 23
Средний и наихудший случай ................................................. 25
Общие функции оценки сложности ...................................... 26

Логарифмы ................................................................................. 27
Скорость работы алгоритма в реальных условиях ........... 27

Обращение к файлу подкачки ...................................................... 28
Резюме ........................................................................................ 30

Глава 2. Списки ........................................................................... 31

Основные понятия о списках .................................................. 31
Простые списки ......................................................................... 32

Изменение размеров массивов .................................................. 32

Список переменного размера .................................................... 35

Класс SimpleList .......................................................................... 39
Неупорядоченные списки ....................................................... 40
Связанные списки ..................................................................... 45

Добавление элементов ............................................................... 47

Удаление элементов ................................................................... 48

Delphi. Готовые алгоритмы

Метки .......................................................................................... 49

Доступ к ячейкам ......................................................................... 50
Разновидности связанных списков ...................................... 52
Циклические связанные списки ................................................... 52
Двусвязные списки ...................................................................... 53
Списки с потоками ...................................................................... 55
Другие связанные структуры ................................................. 58
Резюме ........................................................................................ 60

Глава 3. Стеки и очереди ..................................................... 61

Стеки ............................................................................................ 61
Стеки на связанных списках ........................................................ 63
Очереди ....................................................................................... 65
Циклические очереди .................................................................. 66
Очереди на основе связанных списков ........................................ 70

Очереди с приоритетом .............................................................. 71
Многопоточные очереди ............................................................. 73
Резюме ........................................................................................ 75

Глава 4. Массивы ...................................................................... 77

Треугольные массивы .............................................................. 77
Диагональные элементы ............................................................. 78
Нерегулярные массивы ........................................................... 79
Линейное представление с указателем ....................................... 80
Нерегулярные связанные списки ................................................. 81
Динамические массивы Delphi ..................................................... 82
Разреженные массивы ............................................................. 83
Индексирование массива ............................................................ 84
Сильно разреженные массивы .............................................. 87
Резюме ........................................................................................ 89

Глава 5. Рекурсия ...................................................................... 90

Что такое рекурсия ................................................................... 90
Рекурсивное вычисление факториалов .............................. 91

Анализ сложности ....................................................................... 92

Содержание

Рекурсивное вычиcление
наибольшего общего делителя ............................................. 93

Анализ сложности ....................................................................... 94
Рекурсивное вычисление чисел Фибоначчи ...................... 95

Анализ сложности ....................................................................... 96
Рекурсивное построение кривых Гильберта ...................... 97

Анализ сложности ....................................................................... 99
Рекурсивное построение кривых Серпинского ............... 102

Анализ сложности ..................................................................... 104
Недостатки рекурсии ............................................................. 105

Бесконечная рекурсия ............................................................... 106

Потери памяти .......................................................................... 107

Необоснованное применение рекурсии .................................... 107

Когда нужно использовать рекурсию ........................................ 108
Удаление хвостовой рекурсии ............................................. 109
Нерекурсивное вычисление чисел Фибоначчи ................ 111
Устранение рекурсии в общем случае ............................... 113
Нерекурсивное создание кривых Гильберта ................... 118
Нерекурсивное построение кривых Серпинского .......... 121
Резюме ...................................................................................... 125

Глава 6. Деревья ...................................................................... 126

Определения ............................................................................ 126
Представления деревьев ...................................................... 127

Полные узлы ............................................................................. 128

Списки дочерних узлов ............................................................. 129

Представление нумерацией связей .......................................... 130

Полные деревья ........................................................................ 134
Обход дерева ........................................................................... 135
Упорядоченные деревья ........................................................ 140

Добавление элементов ............................................................. 141

Удаление элементов ................................................................. 142

Обход упорядоченных деревьев ................................................ 146

Delphi. Готовые алгоритмы

Деревья со ссылками ............................................................. 147

Особенности работы ................................................................. 150
Qдеревья ................................................................................. 151

Изменение значения MAX_QTREE_NODES ................................ 157

Восьмеричные деревья ............................................................. 157
Резюме ...................................................................................... 158

Глава 7. Сбалансированные деревья ........................ 159

Балансировка ........................................................................... 159
AVLдеревья .............................................................................. 160

Добавление узлов к AVLдереву ................................................ 160

Удаление узлов из AVLдерева .................................................. 169
Бдеревья .................................................................................. 174

Производительность Бдерева ................................................. 175

Удаление элементов из Бдерева .............................................. 176

Добавление элементов в Бдерево ........................................... 176

Разновидности Бдерева .......................................................... 178

Усовершенствование Бдеревьев ............................................. 180

Вопросы доступа к диску ........................................................... 181

База данных на основе Б+дерева .............................................. 184
Резюме ...................................................................................... 187

Глава 8. Деревья решений ................................................ 188

Поиск в игровых деревьях ..................................................... 188

Минимаксный перебор ............................................................. 190

Оптимизация поиска в деревьях решений ................................. 193
Поиск нестандартных решений ........................................... 194

Ветви и границы ........................................................................ 195

Эвристика ................................................................................. 200
Сложные задачи ...................................................................... 216

Задача о выполнимости ............................................................ 217

Задача о разбиении .................................................................. 217

Задача поиска Гамильтонова пути ............................................. 218

Задача коммивояжера .............................................................. 219

Содержание

Задача о пожарных депо ........................................................... 220

Краткая характеристика сложных задач .................................... 220
Резюме ...................................................................................... 221

Глава 9. Сортировка .............................................................. 222

Общие принципы ..................................................................... 222

Таблицы указателей .................................................................. 222

Объединение и сжатие ключей .................................................. 223
Пример программы ................................................................ 226
Сортировка выбором ............................................................. 226
Перемешивание ...................................................................... 227
Сортировка вставкой ............................................................. 228

Вставка в связанных списках ..................................................... 229
Пузырьковая сортировка ....................................................... 231
Быстрая сортировка ............................................................... 234
Сортировка слиянием ............................................................ 239
Пирамидальная сортировка ................................................. 241

Пирамиды ................................................................................. 241

Очереди с приоритетом ............................................................ 245

Алгоритм пирамидальной сортировки ...................................... 248
Сортировка подсчетом .......................................................... 250
Блочная сортировка ............................................................... 251

Блочная сортировка с использованием связанных списков ...... 252
Резюме ...................................................................................... 255

Глава 10. Поиск ......................................................................... 257

Примеры программ ................................................................ 257
Полный перебор ...................................................................... 258

Перебор сортированных списков .............................................. 259

Перебор связанных списков ...................................................... 259
Двоичный поиск ....................................................................... 261
Интерполяционный поиск ..................................................... 263

Delphi. Готовые алгоритмы

Строковые данные .................................................................. 267
Следящий поиск ...................................................................... 268

Двоичное отслеживание и поиск ............................................... 268

Интерполяционный следящий поиск ......................................... 269
Резюме ...................................................................................... 270

Глава 11. Хеширование ....................................................... 272

Связывание ............................................................................... 273

Преимущества и недостатки связывания .................................. 275
Блоки .......................................................................................... 277

Хранение хештаблиц на диске ................................................. 280

Связывание блоков ................................................................... 283

Удаление элементов ................................................................. 285

Преимущества и недостатки использования блоков ................. 286
Открытая адресация ............................................................... 286

Линейная проверка ................................................................... 287

Квадратичная проверка ............................................................. 294

Псевдослучайная проверка ....................................................... 297

Удаление элементов ................................................................. 299
Резюме ...................................................................................... 301

Глава 12. Сетевые алгоритмы ........................................ 304

Определения ............................................................................ 304
Представления сетей ............................................................. 305

Управление узлами и связями ................................................... 307
Обход сети ................................................................................ 308
Наименьший каркас дерева ................................................. 311
Кратчайший путь ..................................................................... 316

Расстановка меток .................................................................... 318

Коррекция меток ....................................................................... 323

Варианты поиска кратчайшего пути .......................................... 326

Применение алгоритмов поиска кратчайшего пути ................... 331

Содержание

Максимальный поток .............................................................. 335

Сферы применения ................................................................... 342
Резюме ...................................................................................... 345

Глава 13. Объектноориентированные
методы ............................................................................................ 346

Преимущества ООП ................................................................ 346

Инкапсуляция ............................................................................ 346

Полиморфизм ........................................................................... 349

Многократное использование и наследование ......................... 349
Парадигмы ООП ...................................................................... 351

Управляющие объекты .............................................................. 351

Контролирующий объект ........................................................... 353

Итератор ................................................................................... 354

Дружественный класс ............................................................... 356

Интерфейс ................................................................................ 356

Фасад ....................................................................................... 357

Фабрика .................................................................................... 357

Единственный объект ................................................................ 359

Сериализация ........................................................................... 361

Парадигма Модель/Вид/Контроллер ........................................ 364
Резюме ...................................................................................... 367

Приложение 1. Архив примеров ................................... 368

Cодержание архива с примерами ....................................... 368
Аппаратные требования ........................................................ 368
Запуск примеров программ ................................................. 368
Информация и поддержка пользователей ....................... 369

Приложение 2. Список примеров программ ........ 370

Предметный указатель ........................................................ 373

Введение

Программирование под Windows всегда было достаточно сложной задачей. Интер
фейс прикладного программирования (Application Programming Interface – API)
Windows предоставляет в ваше распоряжение набор мощных, но не всегда без
опасных инструментов для разработки приложений. Эти инструменты в некото
ром смысле можно сравнить с огромной и тяжелой машиной, при помощи которой
удается добиться поразительных результатов, но если водитель неосторожен или
не владеет соответствующими навыками, дело, скорее всего, закончится только
разрушениями и убытками.
С появлением Delphi ситуация изменилась. С помощью интерфейса для быст
рой разработки приложений (Rapid Application development – RAD) Delphi позво
ляет быстро и легко выполнять подобную работу. Используя Delphi, можно созда
вать и тестировать приложения со сложным пользовательским интерфейсом без
прямого использования функций API. Освобождая программиста от проблем, свя
занных с применением API, Delphi позволяет сконцентрироваться непосредствен
но на приложении.
Несмотря на то, что Delphi упрощает создание пользовательского интерфейса,
писать остальную часть приложения – код для обработки действий пользователя
и отображения результатов – предоставляется программисту. И здесь потребуют
ся алгоритмы.
Алгоритмы – это формальные команды, необходимые для выполнения на ком
пьютере сложных задач. Например, с помощью алгоритма поиска можно найти
конкретную информацию в базе данных, состоящей из 10 млн записей. В зависимо
сти от качества используемых алгоритмов искомые данные могут быть обнаруже
ны за секунды, часы или вообще не найдены.
В этой книге не только подробно рассказывается об алгоритмах, написанных
на Delphi, но и приводится много готовых мощных алгоритмов. Здесь также ана
лизируются методы управления структурами данных, такими как списки, стеки,
очереди и деревья; описываются алгоритмы для выполнения типичных задач –
сортировки, поиска и хеширования.
Для того чтобы успешно использовать алгоритмы, недостаточно просто ско
пировать код в свою программу и запустить ее на выполнение. Необходимо знать,
как различные алгоритмы ведут себя в разных ситуациях. В конечном итоге имен
но эта информация определяет выбор наиболее подходящего варианта.
Книга написана на достаточно простом языке. Здесь рассматривается поведе
ние алгоритмов как в типичных, так наихудших случаях. Это позволит понять, чего
вы вправе ожидать от определенного алгоритма, вовремя распознать возможные

трудности и при необходимости переписать или удалить алгоритм. Даже самый луч
ший алгоритм не поможет в решении задачи, если использовать его неправильно.
Все алгоритмы представлены в виде исходных текстов на Delphi, которые вы мо
жете включать в свои программы без какихлибо изменений. Тексты кода и приме
ры приложений находятся на сайте издательства «ДМК Пресс» www.dmkpress.ru.
Они демонстрируют характерные особенности работы алгоритмов и их использо
вание в различных программах.

Назначение книги

Данная книга содержит следующий материал:

 полное введение в теорию алгоритмов. После прочтения книги и выполне
ния приведенных примеров вы сможете использовать сложные алгоритмы
в своих проектах и критически оценивать новые алгоритмы, написанные
вами или кемто еще;

 большую подборку исходных текстов. С помощью текстов программ, имею
щихся на сайте издательства «ДМК Пресс», вы сможете быстро добавить го
товые алгоритмы в свои приложения;

 готовые примеры программ позволят вам проверить алгоритмы. Работая с эти
ми примерами, изменяя и совершенствуя их, вы лучше изучите принцип ра
боты алгоритмов. Кроме того, вы можете использовать их как основу для
создания собственных приложений.

Читательская аудитория

Книга посвящена профессиональному программированию в Delphi. Она не
предназначена для обучения. Хорошее знание основ Delphi позволит вам сконцен
трировать внимание на алгоритмах вместо того, чтобы погружаться в детали само
го языка.
Здесь изложены важные принципы программирования, которые могут с успе
хом применяться для решения многих практических задач. Представленные алго
ритмы используют мощные программные методы, такие как рекурсия, разбиение
на части, динамическое распределение памяти, а также сетевые структуры данных,
что поможет вам создавать гибкие и сложные приложения.
Даже если вы еще не овладели Delphi, вы сможете выполнить примеры про
грамм и сравнить производительность различных алгоритмов. Более того, любой
из приведенных алгоритмов будет нетрудно добавить к вашим проектам.

Совместимость версий Delphi

Выбор наилучшего алгоритма зависит от основных принципов программиро
вания, а не от особенностей конкретной версии языка. Тексты программ в этой кни
ге были проверены с помощью Delphi 3, 4 и 5, но благодаря универсальности свойств
языка они должны успешно работать и в более поздних версиях Delphi.

Совместимость версий Delphi

Введение

Языки программирования, как правило, развиваются в сторону усложнения
и очень редко в противоположном направлении. Яркий тому пример – оператор
goto в языке С. Этот неудобный оператор является потенциальным источником
ошибок, он почти не используется большинством программистов на С, но сохранил
ся в синтаксисе языка еще с 70х годов. Оператор даже был встроен в C++ и позднее
в Java, хотя создание нового языка было хорошим предлогом избавиться от ненуж
ного наследия.
Аналогично в старших версиях Delphi наверняка появятся новые свойства, но
вряд ли исчезнут стандартные блоки, необходимые для реализации алгоритмов,
описанных в этой книге. Независимо от того, что добавлено в 4й, 5й, и будет до
бавлено в 6й версии Delphi, классы, массивы, и определяемые пользователем
типы данных останутся в языке. Большая часть, а может быть, и все алгоритмы из
этой книги не будут изменяться еще в течение многих лет. Если вам понадобится
обновить алгоритмы, то их можно будет найти на сайте www.vbhelper. com/da.htm.

Содержание глав

В главе 1 рассматриваются те основы, которые вам необходимо изучить, преж
де чем приступать к анализу сложных алгоритмов. Здесь описываются методы
анализа вычислительной сложности алгоритмов. Некоторые алгоритмы, теорети
чески обеспечивающие высокую производительность, в реальности дают не очень
хорошие результаты. Поэтому в этой главе обсуждаются и практические вопросы,
например, рассматривается обращение к файлу подкачки.
В главе 2 рассказывается, как можно сформировать различные виды списков
с помощью массивов и указателей. Эти структуры данных применяются во мно
гих программах, что продемонстрировано в следующих главах книги. В главе 2
также показано, как обобщить методы, использованные для построения связан
ных списков, для создания других, более сложных структуры данных, например,
деревьев и сетей.
В главе 3 рассматриваются два специализированных вида списков – стеки
и очереди, использующиеся во многих алгоритмах (некоторые их них описывают
ся в последующих главах). В качестве практического примера приведена модель,
сравнивающая производительность двух типов очередей, которые могли бы ис
пользоваться в регистрационных пунктах аэропортов.
Глава 4 посвящена специальным типам массивов. Треугольные, неправильные
и разреженные массивы позволяют использовать удобные представления данных
для экономии памяти.
В главе 5 рассматривается мощный, но довольно сложный инструмент – ре
курсия. Здесь рассказывается, в каких случаях можно использовать рекурсию и как
ее можно при необходимости удалить.
В главе 6 многие из представленных выше алгоритмов, такие как рекурсия
и связанные списки, используются для изучения более сложного вопроса – дере
вьев. Рассматриваются различные представления деревьев – с помощью полных
узлов и нумерации связей. Здесь содержатся также некоторые важные алгоритмы,
например, обход узлов дерева.

В главе 7 затронута более широкая тема. Сбалансированные деревья обла
дают некоторыми свойствами, которые позволяют им оставаться уравновешен
ными и эффективными. Алгоритмы сбалансированных деревьев просто описать,
но довольно трудно реализовать в программе. В этой главе для построения слож
ной базы данных используется одна из наиболее мощных структур – Б+ дерево.
В главе 8 рассматриваются алгоритмы, которые предназначены для поиска
ответа в дереве решений. Даже при решении маленьких задач эти деревья могут
быть поистине огромными, поэтому становится насущным вопрос эффективного
поиска нужных элементов. В этой главе сравнивается несколько различных мето
дов подобного поиска.
Глава 9 посвящена наиболее сложному разделу теории алгоритмов. Алгорит
мы сортировки интересны по нескольким причинам. Вопервых, сортировка – это
общая задача программирования. Вовторых, различные алгоритмы сортировки
имеют свои достоинства и недостатки, и нет единого универсального алгоритма,
который бы работал одинаково в любых ситуациях. И наконец, в алгоритмах сор
тировки используется множество разнообразных методов, таких как рекурсия,
бинарные деревья, применение генератора случайных чисел, что уменьшает веро
ятность выпадения наихудшего случая.
Глава 10 посвящена вопросам сортировки. Как только список отсортирован, про
грамме может потребоваться найти в нем какойлибо элемент. В этой главе сравни
ваются наиболее эффективные методы поиска элементов в сортированных списках.
В главе 11 приводятся более быстрые, чем использование деревьев, способы
сортировки и поиска, методы сохранения и размещения элементов. Здесь описы
вается несколько методов хеширования, включая использование блоков и связан
ных списков, а также некоторые типы открытой адресации.
В главе 12 обсуждается другая категория алгоритмов – сетевая. Некоторые из
подобных алгоритмов, например, вычисление кратчайшего пути, непосредственно
применяются в физических сетях. Они могут косвенно использоваться для реше
ния других проблем, которые на первый взгляд кажутся не относящимися к сетям.
Например, алгоритм поиска кратчайшего пути может делить сеть на районы или
находить критические точки в сетевом графике.
Глава 13 посвящена объектноориентированным алгоритмам. В них использу
ются объектноориентированные способы реализации нетипичного для традици
онных алгоритмов поведения.
В приложении 1 описывается содержание архива примеров, который находит
ся на сайте издательства «ДМК Пресс» www.dmkpress.ru.
В приложении 2 содержатся все программы примеров, имеющихся в архиве.
Для того чтобы найти, какая из программ демонстрирует конкретные алгоритми
ческие методы, достаточно обратиться к этому списку.

Архив примеров

Архив примеров, который вы можете загрузить с сайта издательства «ДМК
Пресс» www.dmkpress.ru, содержит исходный код в Delphi 3 для алгоритмов и при
меров программ, описанных в книге.

Архив примеров

Введение

Описанные в каждой главе примеры программ содержатся в отдельных под
каталогах. Например, программы, демонстрирующие алгоритмы, которые рас
сматриваются в главе 3, сохранены в каталоге \Ch3\. В приложении 2 перечисля
ются все приведенные в книге программы.

Аппаратные требования

Для освоения примеров необходим компьютер, конфигурация которого удов
летворяет требованиям работы с Delphi, то есть почти каждый компьютер, рабо
тающий с любой версией Windows.
На компьютерах с различной конфигурацией алгоритмы выполняются с неоди
наковой скоростью. Компьютер с процессором Pentium Pro с частотой 200 МГц
и объемом оперативной памяти 64 Мб, безусловно, будет работать быстрее, чем
компьютер на базе процессора Intel 386 и объемом памяти 4 Мб. Вы быстро опре
делите предел возможностей ваших аппаратных средств.

Как пользоваться этой книгой

В главе 1 дается базовый материал, поэтому необходимо начать именно с этой
главы. Даже если вам уже известны все тонкости теории алгоритмов, все равно не
обходимо прочесть эту главу.
Следующими нужно изучить главы 2 и 3, поскольку в них рассматриваются
различные виды списков, используемых программами в следующих главах книги.
В главе 6 обсуждаются понятия, которые используются затем в главах 7, 8, и 12.
Перед тем как заняться изучением этих глав, вы должны ознакомиться с главой 6.
Остальные главы можно читать в произвольном порядке.
В табл. 1 приведены три примерных плана работы с материалом. Вы можете
выбрать один из них, руководствуясь тем, насколько глубоко вы хотите изучить
алгоритмы. Первый план предполагает освоение основных методов и структур
данных, которые вы можете успешно использовать в собственных программах.
Второй план помимо этого включает в себя работу с фундаментальными алгорит
мами, такими как алгоритмы сортировки и поиска, которые могут вам понадобить
ся для разработки более сложных программ.
Последний план определяет порядок изучения всей книги. Несмотря на то, что
главы 7 и 8 по логике должны следовать за главой 6, она гораздо сложнее, чем бо
лее поздние главы, поэтому их рекомендуется прочесть позже. Главы 7, 12 и 13
наиболее трудные в книге, поэтому к ним лучше обратиться в последнюю очередь.
Конечно, вы можете читать книгу и последовательно – от самой первой страницы
до последней.

Таблица 1. Планы работы

Изучаемый материал
Главы

Основные методы
1
2
3
4

Базовые алгоритмы
1
2
3
4
5
6
9
10
13

Углубленное изучение
1
2
3
4
5
6
9
10
11
8
12
7
13

Обозначения, используемые в книге

В книге используются следующие шрифтовые выделения:

 курсивом помечены смысловые выделения в тексте;

 полужирным шрифтом выделяются названия элементов интерфейса: пунк
тов меню, пиктограмм и т.п.;

 моноширинным шрифтом выделены листинги (программный код).

Обозначения, используемые в книге