Языки программирования зачастую развиваются в сторону усложнения, но редко
в противоположном направлении. Замечательным примером этого является наличие
оператора goto в языке C. Это неудобный оператор,
потенциальный источник ошибок, который почти не используется большинством программистов
на C, но он по‑прежнему остается в синтаксисе языка с 1970 года. Он даже был
включен в C++ и позднее в Java, хотя создание нового языка было хорошим предлогом
избавиться от него.
Так и новые версии Visual Basic будут продолжать вводить новые свойства в
язык, но маловероятно, что из них будут исключены строительные блоки, использованные
при применении алгоритмов, описанных в книге. Независимо от того, что будет
добавлено в 6-й, 7-й или 8-й версии Visual Basic, классы, массивы и определяемые
пользователем типы данных останутся в языке. Большая часть, а может и все алгоритмы
из этой книги, будут выполняться без изменений в течение еще многих лет.
Обзор глав
В 1 главе рассматриваются понятия, которые вы должны понимать до того, как
приступить к анализу сложных алгоритмов. В ней изложены методы, которые потребуются
для теоретического анализа вычислительной сложности алгоритмов. Некоторые алгоритмы
с высокой теоретической производительностью на практике дают не очень хорошие
результаты, поэтому в этой главе также затрагиваются практические соображения,
например обращение к файлу подкачки и сравнивается использование коллекций и
массивов.
Во 2 главе показано, как образуются различные виды списков с использованием
массивов, объектов, и псевдоуказателей. Эти структуры данных можно с успехом
применять во многих программах, и они используются в следующих главах книги.
В 3 главе описаны два особых типа списков: стеки и очереди. Эти структуры
данных используются во многих алгоритмах, включая некоторые алгоритмы, описанные
в последующих главах. В конце главы приведена модель очереди на регистрацию
в аэропорту.
В 5 главе обсуждается мощный инструмент — рекурсия. Рекурсия может быть также
запутанной и приводить к проблемам. В 5 главе объясняется, в каких случаях следует
применять рекурсию и показывает, как можно от нее избавиться, если это необходимо.
В 6 главе используются многие из ранее описанных приемов, такие как рекурсия
и связные списки, для изучения более сложной темы — деревьев. Эта глава также
охватывает различные представления деревьев, такие как деревья с полными узлами
(fat node) и представление в виде нумерацией связей (forward star). В ней также
описаны некоторые важные алгоритмы работы с деревьями, таки как обход вершин
дерева.
В 7 главе затронута более сложная тема. Сбалансированные деревья обладают
особыми свойствами, которые позволяют им оставаться уравновешенными и эффективными.
Алгоритмы сбалансированных деревьев удивительно просто описываются, но их достаточно
трудно реализовать программно. В этой главе используется одна из наиболее мощных
структур подобного типа — Б+дерево (B+Tree) для создания сложной базы данных.
В 8 главе обсуждаются задачи, которые можно описать как поиск ответов в дереве
решений. Даже для небольших задач, эти деревья могут быть гигантскими, поэтому
необходимо осуществлять поиск в них максимально эффективно. В этой главе сравниваются
некоторые различные методы, которые позволяют выполнить такой поиск.
Глава 9 посвящена, пожалуй, наиболее изучаемой области теории алгоритмов
— сортировке. Алгоритмы сортировки интересны по нескольким причинам. Во‑первых,
сортировка — часто встречающаяся задача. Во‑вторых, различные алгоритмы сортировок
обладают своими сильными и слабыми сторонами, поэтому не существует одного алгоритма,
который показывал бы наилучшие результаты в любых ситуациях. И, наконец, алгоритмы
сортировки демонстрируют широкий спектр важных алгоритмических методов, таких
как рекурсия, пирамиды, а также использование генератора случайных чисел для
уменьшения вероятности выпадения наихудшего случая.
В главе 10 рассматривается близкая к сортировке тема. После выполнения сортировки
списка, программе может понадобиться найти элементы в нем. В этой главе сравнивается
несколько наиболее эффективных методов поиска элементов в сортированных списках.
=========xiv
В главе 11 обсуждаются методы сохранения и поиска элементов, работающие даже
быстрее, чем это возможно при использовании деревьев, сортировки или поиска.
В этой главе также описаны некоторые методы хэширования, включая использование
блоков и связных списков, и несколько вариантов открытой адресации.
В главе 12 описана другая категория алгоритмов — сетевые алгоритмы. Некоторые
из этих алгоритмов, такие как вычисление кратчайшего пути, непосредственно применимы
к физическим сетям. Эти алгоритмы также могут косвенно применяться для решения
других задач, которые на первый взгляд не кажутся связанными с сетями. Например,
алгоритмы поиска кратчайшего расстояния могут разбивать сеть на районы или определять
критичные задачи в расписании проекта.
В главе 13 объясняются методы, применение которых стало возможным благодаря
введению классов в 4‑й версии Visual Basic. Эти методы используют объектно‑ориентированный
подход для реализации нетипичного для традиционных алгоритмов поведения.
Приложение 1 описывает содержание компакт‑диска. В нем объясняется, как вы
можете загрузить программы примеров, и что делать, если возникнут проблемы с
компакт‑диском.
Приложение 2 кратко описывает программы примеров, которые содержатся на компакт‑диске.
Вы также можете обратиться к этому списку, чтобы узнать, какие программы демонстрируют
конкретные алгоритмические методы.
Что находится на компакт‑диске
Прилагаемый к книге компакт‑диск содержит исходный код на языке Visual Basic
для алгоритмов и программ примеров, описанных в книге. Этот код сохранен в формате
4‑й версии Visual Basic, чтобы быть доступным большему числу читателей книги.
Вы также можете открыть эти файлы в 4‑й или более поздней версии Visual Basic.
Алгоритмы тестировались в 4‑й и 5‑й версиях языка.
Описываемые в каждой главе программы примеров находятся в отдельных поддиректориях
в директории Src. Например, программы, демонстрирующие
алгоритмы, описанные в 3 главе, записаны в директории Src\Ch3. В приложении
2 приведен список всех описанных в книге программ.
Содержимое компакт‑диска также включает исходный код для программ из первого
издания книги. Эти программы совместимы с 3‑й версией Visual Basic, поэтому
они записаны в формате этой версии. Вы можете открыть их в 3‑й или последующих
версиях Visual Basic. Старые версии записаны в поддиректориях директории
OldSrc. Например, директория OldSrc\Ch3
содержит программы, которые относятся к 3 главе в этом издании книги.
Старые программы покрывают в основном те же темы, что и в настоящем издании,
но используют код для 3‑версии Visual Basic. Например, в них не используются
коллекции или классы. Это усложняет понимание некоторых алгоритмов, но многие
из этих программ показывают лучшую производительность.
Особенно широко коллекции и классы используются в обновленных версиях алгоритмов
работы с сетями и деревьями. Хотя такой подход облегчает понимание программ,
он также делает их более медленными. Старые программы используют представление
древовидной сети нумерацией связей (см. в 6 главе подробнее об этом представлении)
для достижения более высокой производительности.
===================xv
Аппаратные требования
Для работы с примерами вам потребуется компьютер, конфигурация которого удовлетворяет
требованиям для работы программной среды Visual Basic. Эти требования выполняются
почти для всех компьютеров, на которых может работать операционная система Windows.
Вам также потребуется наличие привода для чтения компакт‑дисков.
На компьютерах разной конфигурации алгоритмы выполняются с различной скоростью.
Компьютер с процессором Pentium Pro с тактовой частотой 2000 МГц и 64 Мбайт
оперативной памяти будет работать намного быстрее, чем машина с 386 процессором
и всего 4 Мбайт памяти. Вы быстро узнаете, на что способно ваше аппаратное обеспечение.
Изменения во втором издании
Самое большое изменение в новой версии Visual Basic — это появление классов.
Классы позволяют рассмотреть некоторые задачи с другой стороны, позволяя использовать
более простой и естественный подход к пониманию и применению многих алгоритмов.
Изменения в коде программ в этом издании книги используют преимущества, предоставляемые
классами. Их можно разбить на три категории:
1. Замена псевдоуказателей классами. Хотя все алгоритмы, которые были написаны
для первого издания этой книги, все еще работают, многие из тех, что были написаны
с применением псевдоуказателей (описанных во 2 главе), гораздо проще понять,
используя классы.
2. Инкапсуляция. Классы позволяют заключить алгоритм в компактный модуль,
который легко использовать в программе. Например, при помощи классов можно создать
несколько связных списков и не писать при этом дополнительный код для управления
каждым списком по отдельности.
3. Объектно‑ориентированные технологии. Использование классов также позволяет
легче понять некоторые объектно‑ориентированные алгоритмы. В главе 13 описываются
методы, которые сложно реализовать без использования классов.
Как пользоваться этой книгой
В главе 1 даются общие понятия, которые используются на протяжении всей книги,
поэтому вам следует начать чтение с этой главы. Вам стоит ознакомиться с этой
тематикой, даже если вы не хотите сразу же достичь глубокого понимания алгоритмов.
Во 2 и 3 главах описываются различные типы списков, которые используются
в программах из остальной части книги, поэтому вам следует прочесть их в следующую
очередь.
В 6 главе обсуждаются понятия, которые используются в 7, 8 и 12 главах, поэтому
вам следует прочитать 6 главу до того, как браться за них. Остальные главы можно
читать в любом порядке.
=============xvi
В табл. 1 показаны три возможных учебных плана, которыми вы можете руководствоваться
при изучении материала в зависимости от того, насколько широко вы хотите ознакомиться
с алгоритмами. Первый план включает в себя освоение основных методов и структур
данных, которые могут быть полезны при разработке вами собственных программ.
Второй кроме этого описывает также основные алгоритмы, такие как алгоритмы сортировки
и поиска, которые могут понадобиться при написании более сложных программ.
Последний план дает порядок для изучения всей книги целиком. Хотя 7 и 8 главы
логически вытекают из 6 главы, они сложнее для изучения, чем следующие главы,
поэтому они изучаются несколько позже. Главы 7, 12 и 13 возможно самые трудные
в книге, поэтому они изучаются в последнюю очередь. Конечно же, вы можете читать
книгу и последовательно с начала и до конца.
Почему именно Visual Basic?
Наиболее часто встречаются жалобы на медленное выполнение программ, написанных
на Visual Basic. Многие другие компиляторы, такие как Delphi, Visual C++ дают
более быстрый и гибкий код, и предоставляют программисту более мощные средства,
чем Visual Basic. Поэтому логично задать вопрос — «Почему я должен использовать
именно Visual Basic для написания сложных алгоритмов? Не лучше было бы использовать
Delphi или C++ или, по крайней мере, написать алгоритмы на одном из этих языков
и подключать их к программам на Visual Basic при помощи библиотек?» Написание
алгоритмов на Visual Basic имеет смысл по нескольким причинам.
Во‑первых, разработка приложения на Visual C++ гораздо сложнее и проблематичнее,
чем на Visual Basic. Некорректная реализация в программе всех деталей программирования
под Windows может привести к сбоям в вашем приложении, среде разработки, или
в самой операционной системе Windows.
Во‑вторых, разработка библиотеки на языке C++ для использования в программах
на Visual Basic включает в себя много потенциальных опасностей, характерных
и для приложений Windows, написанных на C++. Если библиотека будет неправильно
взаимодействовать с программой на Visual Basic, она также приведет к сбоям в
программе, а возможно и в среде разработки и системе.
В-третьих, многие алгоритмы достаточно эффективны и показывают неплохую производительность
даже при применении не очень быстрых компиляторов, таких, как Visual Basic.
Например, алгоритм сортировки подсчетом,
@Таблица 1. Планы занятий
===============xvii
описываемый в 9 главе, сортирует миллион целых чисел менее чем за 2 секунды
на компьютере с процессором Pentium с тактовой частотой 233 МГц. Используя библиотеку
C++, можно было бы сделать алгоритм немного быстрее, но скорости версии на Visual
Basic и так хватает для большинства приложений. Скомпилированные при помощи
5‑й версией Visual Basic исполняемые файлы сводят отставание по скорости к минимуму.
В конечном счете, разработка алгоритмов на любом языке программирования позволяет
больше узнать об алгоритмах вообще. По мере изучения алгоритмов, вы освоите
методы, которые сможете применять в других частях своих программ. После того,
как вы овладеете в совершенстве алгоритмами на Visual Basic, вам будет гораздо
легче реализовать их на Delphi или C++, если это будет необходимо.
=============xviii
Глава 1. Основные понятия
В этой главе содержатся общие понятия, которые нужно усвоить перед началом
серьезного изучения алгоритмов. Начинается она с вопроса «Что такое алгоритмы?».
Прежде чем углубиться в детали программирования алгоритмов, стоит потратить
немного времени, чтобы разобраться в том, что это такое.
Затем в этой главе дается введение в формальную теорию сложности алгоритмов
(complexity theory). При помощи этой теории можно оценить теоретическую вычислительную
сложность алгоритмов. Этот подход позволяет сравнивать различные алгоритмы и
предсказывать их производительность в разных условиях. В главе приводится несколько
примеров применения теории сложности к небольшим задачам.
Некоторые алгоритмы с высокой теоретической производительностью не слишком
хорошо работают на практике, поэтому в данной главе также обсуждаются некоторые
реальные предпосылки для создания программ. Слишком частое обращение к файлу
подкачки или плохое использование ссылок на объекты и коллекции может значительно
снизить производительность прекрасного в остальных отношениях приложения.
