Блочная сортировка с применением связного списка................... 243
Блочная сортировка на основе массива......................................... 245
Резюме................................................................................................. 248
Глава 10. Поиск................................................................................... 248
Примеры программ........................................................................... 249
Поиск методом полного перебора................................................... 249
Поиск в упорядоченных списках.................................................... 250
Поиск в связных списках................................................................ 251
Двоичный поиск................................................................................ 253
Интерполяционный поиск............................................................... 255
Строковые данные............................................................................ 259
Следящий поиск................................................................................ 260
Интерполяционный следящий поиск............................................. 261
Резюме................................................................................................. 262
Глава 11. Хеширование...................................................................... 263
Связывание........................................................................................ 265
Преимущества и недостатки связывания....................................... 266
Блоки.................................................................................................. 268
Хранение хеш‑таблиц на диске...................................................... 270
Связывание блоков.......................................................................... 274
Удаление элементов........................................................................ 275
Преимущества и недостатки применения блоков......................... 277
Открытая адресация......................................................................... 277
Линейная проверка.......................................................................... 278
Квадратичная проверка................................................................... 284
Псевдослучайная проверка............................................................. 286
Удаление элементов........................................................................ 289
Резюме................................................................................................. 291
Глава 12. Сетевые алгоритмы............................................................ 292
Определения...................................................................................... 292
Представления сети.......................................................................... 293
Оперирование узлами и связями.................................................... 295
Обходы сети....................................................................................... 296
Наименьшие остовные деревья...................................................... 298
Кратчайший маршрут...................................................................... 302
Установка меток.............................................................................. 304
Коррекция меток............................................................................. 308
Другие задачи поиска кратчайшего маршрута.............................. 311
Применения метода поиска кратчайшего маршрута.................... 316
Максимальный поток...................................................................... 319
Приложения максимального потока.............................................. 325
Резюме................................................................................................. 327
Глава 13. Объектно‑ориентированные методы................................. 327
Преимущества ООП......................................................................... 328
Инкапсуляция.................................................................................. 328
Полиморфизм.................................................................................. 330
Наследование и повторное использование.................................... 333
Парадигмы ООП............................................................................... 335
Управляющие объекты................................................................... 335
Контролирующий объект............................................................... 336
Итератор.......................................................................................... 337
Дружественный класс..................................................................... 338
Интерфейс....................................................................................... 340
Фасад............................................................................................... 340
Порождающий объект..................................................................... 340
Единственный объект...................................................................... 341
Преобразование в последовательную форму................................ 341
Парадигма Модель/Вид/Контроллер............................................. 344
Резюме................................................................................................. 346
Требования к аппаратному обеспечению...................................... 346
Выполнение программ примеров.................................................... 346
programmer@newmail.ru
Далее следует «текст», который любой уважающий себя программист должен прочесть хотя бы один раз. (Это наше субъективное мнение)
Программирование под Windows всегда было нелегкой задачей. Интерфейс прикладного программирования (Application Programming Interface) Windows предоставляет в распоряжение программиста набор мощных, но не всегда безопасных инструментов для разработки приложений. Можно сравнить его с бульдозером, при помощи которого удается добиться поразительных результатов, но без соответствующих навыков и осторожности, скорее всего, дело закончится только разрушениями и убытками.
Эта картина изменилась с появлением Visual Basic. Используя визуальный интерфейс, Visual Basic позволяет быстро и легко разрабатывать законченные приложения. При помощи Visual Basic можно разрабатывать и тестировать сложные приложения без прямого использования функций API. Избавляя программиста от проблем с API, Visual Basic позволяет сконцентрироваться на деталях приложения.
Хотя Visual Basic и облегчает разработку пользовательского интерфейса, задача написания кода для реакции на входные воздействия, обработки их, и представления результатов ложится на плечи программиста. Здесь начинается применение алгоритмов.
Алгоритмы представляют собой формальные инструкции для выполнения сложных задач на компьютере. Например, алгоритм сортировки может определять, как найти конкретную запись в базе из 10 миллионов записей. В зависимости от класса используемых алгоритмов искомые данные могут быть найдены за секунды, часы или вообще не найдены.
В этом материале обсуждаются алгоритмы на Visual Basic и содержится большое число мощных алгоритмов, полностью написанных на этом языке. В ней также анализируются методы обращения со структурами данных, такими, как списки, стеки, очереди и деревья, и алгоритмы для выполнения типичных задач, таких как сортировка, поиск и хэширование.
Для того чтобы успешно применять эти алгоритмы, недостаточно их просто скопировать в свою программу. Необходимо кроме этого понимать, как различные алгоритмы ведут себя в разных ситуациях, что в конечном итоге и будет определять выбор наиболее подходящего алгоритма.
В этом материале поведение алгоритмов в типичном и наихудшем случаях описано доступным языком. Это позволит понять, чего вы вправе ожидать от того или иного алгоритма и распознать, в каких условиях встречается наихудший случай, и в соответствии с этим переписать или поменять алгоритм. Даже самый лучший алгоритм не поможет в решении задачи, если применять его неправильно.
=============xi
Все алгоритмы также представлены в виде исходных текстов на Visual Basic, которые вы можете использовать в своих программах без каких‑либо изменений. Они демонстрируют использование алгоритмов в программах, а также важные характерные особенности работы самих алгоритмов.
Что дают вам эти знания
После ознакомления с данным материалом и примерами вы получите:
1. Понятие об алгоритмах. После прочтения данного материала и выполнения примеров программ, вы сможете применять сложные алгоритмы в своих проектах на Visual Basic и критически оценивать другие алгоритмы, написанные вами или кем‑либо еще.
2. Большую подборку исходных текстов, которые вы сможете легко добавить к вашим программам. Используя код, содержащийся в примерах, вы сможете легко добавлять мощные алгоритмы к вашим приложениям.
3. Готовые примеры программ дадут вам возможность протестировать алгоритмы. Вы можете использовать эти примеры и модифицировать их для углубленного изучения алгоритмов и понимания их работы, или использовать их как основу для разработки собственных приложений.
В этом материале обсуждаются углубленные вопросы программирования на Visual Basic. Они не предназначена для обучения программированию на этом языке. Если вы хорошо разбираетесь в основах программирования на Visual Basic, вы сможете сконцентрировать внимание на алгоритмах вместо того, чтобы застревать на деталях языка.
В этом материале изложены важные концепции программирования, которые могут быть с успехом применены для решения новых задач. Приведенные алгоритмы используют мощные программные методы, такие как рекурсия, разбиение на части, динамическое распределение памяти и сетевые структуры данных, которые вы можете применять для решения своих конкретных задач.
Даже если вы еще не овладели в полной мере программированием на Visual Basic, вы сможете скомпилировать примеры программ и сравнить производительность различных алгоритмов. Более того, вы сможете выбрать удовлетворяющие вашим требованиям алгоритмы и добавить их к вашим проектам на Visual Basic.
Совместимость с разными версиями Visual Basic
Выбор наилучшего алгоритма определяется не особенностями версии языка программирования, а фундаментальными принципами программирования.
=================xii
Некоторые новые понятия, такие как ссылки на объекты, классы и коллекции, которые были впервые введены в 4-й версии Visual Basic, облегчают понимание, разработку и отладку некоторых алгоритмов. Классы могут заключать некоторые алгоритмы в хорошо продуманных модулях, которые легко вставить в программу. Хотя для того, чтобы применять эти алгоритмы, необязательно разбираться в новых понятиях языка, эти новые возможности предоставляют слишком большие преимущества, чтобы ими можно было пренебречь.
Поэтому примеры алгоритмов в этом материале написаны для использования в 4-й и 5-й версиях Visual. Если вы откроете их в 5-й версии Visual Basic, среда разработки предложит вам сохранить их в формате 5-й версии, но никаких изменений в код вносить не придется. Все алгоритмы были протестированы в обеих версиях.
Эти программы демонстрируют использование алгоритмов без применения объектно-ориентированного подхода. Ссылки и коллекции облегчают программирование, но их применение может приводить к некоторому замедлению работы программ по сравнению со старыми версиями.