Целевая аудитория

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

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

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

Совместимость с разными версиями Visual Basic

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

=================xii

Некоторые новые понятия, такие как ссылки на объекты, классы и коллекции, которые были впервые введены в 4-й версии Visual Basic, облегчают понимание, разработку и отладку некоторых алгоритмов. Классы могут заключать некоторые алгоритмы в хорошо продуманных модулях, которые легко вставить в программу. Хотя для того, чтобы применять эти алгоритмы, необязательно разбираться в новых понятиях языка, эти новые возможности предоставляют слишком большие преимущества, чтобы ими можно было пренебречь.

Поэтому примеры алгоритмов в этом материале написаны для использования в 4-й и 5-й версиях Visual. Если вы откроете их в 5-й версии Visual Basic, среда разработки предложит вам сохранить их в формате 5-й версии, но никаких изменений в код вносить не придется. Все алгоритмы были протестированы в обеих версиях.

Эти программы демонстрируют использование алгоритмов без применения объектно-ориентированного подхода. Ссылки и коллекции облегчают программирование, но их применение может приводить к некоторому замедлению работы программ по сравнению со старыми версиями.

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

Языки программирования зачастую развиваются в сторону усложнения, но редко в противоположном направлении. Замечательным примером этого является наличие оператора 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. Эти методы используют объектно‑ориентированный подход для реализации нетипичного для традиционных алгоритмов поведения.

===================xv

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

Для работы с примерами вам потребуется компьютер, конфигурация которого удовлетворяет требованиям для работы программной среды Visual Basic. Эти требования выполняются почти для всех компьютеров, на которых может работать операционная система Windows.

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

Изменения во втором издании

Самое большое изменение в новой версии Visual Basic — это появление классов. Классы позволяют рассмотреть некоторые задачи с другой стороны, позволяя использовать более простой и естественный подход к пониманию и применению многих алгоритмов. Изменения в коде программ в этом изложении используют преимущества, предоставляемые классами. Их можно разбить на три категории:

1. Замена псевдоуказателей классами. Хотя все алгоритмы, которые были написаны для старых версий VB, все еще работают, многие из тех, что были написаны с применением псевдоуказателей (описанных во 2 главе), гораздо проще понять, используя классы.

2. Инкапсуляция. Классы позволяют заключить алгоритм в компактный модуль, который легко использовать в программе. Например, при помощи классов можно создать несколько связных списков и не писать при этом дополнительный код для управления каждым списком по отдельности.

3. Объектно‑ориентированные технологии. Использование классов также позволяет легче понять некоторые объектно‑ориентированные алгоритмы. В главе 13 описываются методы, которые сложно реализовать без использования классов.

Как пользоваться этим материалом

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

В 6 главе обсуждаются понятия, которые используются в 7, 8 и 12 главах, поэтому вам следует прочитать 6 главу до того, как браться за них. Остальные главы можно читать в любом порядке.

=============xvi

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

Последний план дает порядок для изучения всего материала целиком. Хотя 7 и 8 главы логически вытекают из 6 главы, они сложнее для изучения, чем следующие главы, поэтому они изучаются несколько позже.

Почему именно 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