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

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

Минимаксный поиск 181

Улучшение поиска в дереве игры 185

Поиск в других деревьях решений 187

Метод ветвей и границ 187

Эвристики 192

Другие сложные задачи 208

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

Задача о разбиении 209

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

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

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

Краткая характеристика сложных задач 212

Резюме 213

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

Общие соображения 214

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

Объединение и сжатие ключей 216

Примеры программ 218

Сортировка выбором 219

Рандомизация 221

Сортировка вставкой 222

Вставка в связных списках 223

Пузырьковая сортировка 224

Быстрая сортировка 228

Сортировка слиянием 233

Пирамидальная сортировка 235

Пирамиды 235

Приоритетные очереди 238

Алгоритм пирамидальной сортировки 240

Сортировка подсчетом 242

Блочная сортировка 243

Блочная сортировка с применением связного списка 244

Блочная сортировка на основе массива 246

Резюме 248

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

Примеры программ 249

Поиск методом полного перебора 250

Поиск в упорядоченных списках 251

Поиск в связных списках 252

Двоичный поиск 254

Интерполяционный поиск 255

Строковые данные 260

Следящий поиск 260

Интерполяционный следящий поиск 262

Резюме 263

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

Связывание 266

Преимущества и недостатки связывания 267

Блоки 269

Хранение хеш‑таблиц на диске 271

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

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

Преимущества и недостатки применения блоков 277

Открытая адресация 278

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

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

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

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

Резюме 292

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

Определения 293

Представления сети 294

Оперирование узлами и связями 295

Обходы сети 296

Наименьшие остовные деревья 299

Кратчайший маршрут 302

Установка меток 304

Коррекция меток 308

Другие задачи поиска кратчайшего маршрута 312

Применения метода поиска кратчайшего маршрута 316

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

Приложения максимального потока 325

Резюме 327

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

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

Инкапсуляция 328

Полиморфизм 331

Наследование и повторное использование 334

Парадигмы ООП 335

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

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

Итератор 338

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

Интерфейс 340

Фасад 341

Порождающий объект 341

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

Преобразование в последовательную форму 342

Парадигма Модель/Вид/Контроллер. 345

Резюме 346

Требования к аппаратному обеспечению 347

Выполнение программ примеров 347

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