VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
Введение 8
Целевая аудитория 10
Глава 1. Основные понятия 15
Что такое алгоритмы? 15
Анализ скорости выполнения алгоритмов 16
Пространство — время 17
Оценка с точностью до порядка 17
Поиск сложных частей алгоритма 19
Сложность рекурсивных алгоритмов 20
Многократная рекурсия 21
Косвенная рекурсия 22
Требования рекурсивных алгоритмов к объему памяти 22
Наихудший и усредненный случай 23
Часто встречающиеся функции оценки порядка сложности 24
Логарифмы 25
Реальные условия — насколько быстро? 25
Обращение к файлу подкачки 26
Псевдоуказатели, ссылки на объекты и коллекции 27
Резюме 29
Глава 2. Списки 30
Знакомство со списками 31
Простые списки 31
Коллекции 32
Список переменного размера 33
Класс SimpleList 36
Неупорядоченные списки 37
Связные списки 41
Добавление элементов к связному списку 43
Удаление элементов из связного списка 44
Уничтожение связного списка 44
Сигнальные метки 45
Инкапсуляция связных списков 46
Доступ к ячейкам 47
Разновидности связных списков 49
Циклические связные списки 49
Проблема циклических ссылок 50
Двусвязные списки 50
Потоки 53
Другие связные структуры 56
Псевдоуказатели 56
Резюме 59
Глава 3. Стеки и очереди 60
Стеки 60
Множественные стеки 62
Очереди 63
Циклические очереди 65
Очереди на основе связных списков 69
Применение коллекций в качестве очередей 70
Приоритетные очереди 70
Многопоточные очереди 72
Резюме 74
Глава 4. Массивы 75
Треугольные массивы 75
Диагональные элементы 77
Нерегулярные массивы 78
Прямая звезда 78
Нерегулярные связные списки 79
Разреженные массивы 80
Индексирование массива 82
Очень разреженные массивы 85
Резюме 86
Глава 5. Рекурсия 86
Что такое рекурсия? 87
Рекурсивное вычисление факториалов 88
Анализ времени выполнения программы 89
Рекурсивное вычисление наибольшего общего делителя 90
Анализ времени выполнения программы 91
Рекурсивное вычисление чисел Фибоначчи 92
Анализ времени выполнения программы 93
Рекурсивное построение кривых Гильберта 94
Анализ времени выполнения программы 96
Рекурсивное построение кривых Серпинского 98
Анализ времени выполнения программы 100
Опасности рекурсии 101
Бесконечная рекурсия 101
Потери памяти 102
Необоснованное применение рекурсии 103
Когда нужно использовать рекурсию 104
Хвостовая рекурсия 105
Нерекурсивное вычисление чисел Фибоначчи 107
Устранение рекурсии в общем случае 110
Нерекурсивное построение кривых Гильберта 114
Нерекурсивное построение кривых Серпинского 117
Резюме 121
Глава 6. Деревья 121
Определения 122
Представления деревьев 123
Полные узлы 123
Списки потомков 124
Представление нумерацией связей 126
Полные деревья 129
Обход дерева 130
Упорядоченные деревья 135
Добавление элементов 135
Удаление элементов 136
Обход упорядоченных деревьев 139
Деревья со ссылками 141
Работа с деревьями со ссылками 144
Квадродеревья 145
Изменение MAX_PER_NODE 151
Использование псевдоуказателей в квадродеревьях 151
Восьмеричные деревья 152
Резюме 152
Глава 7. Сбалансированные деревья 153
Сбалансированность дерева 153
АВЛ-деревья 154
Удаление узла из АВЛ-дерева 161
Б-деревья 166
Производительность Б-деревьев 167
Вставка элементов в Б-дерево 167
Удаление элементов из Б-дерева 168
Разновидности Б-деревьев 169
Улучшение производительности Б-деревьев 171
Балансировка для устранения разбиения блоков 171
Вопросы, связанные с обращением к диску 173
База данных на основе Б+дерева 176
Резюме 179
Глава 8. Деревья решений 179
Поиск в деревьях игры 180
Минимаксный поиск 181
Улучшение поиска в дереве игры 185
Поиск в других деревьях решений 187
Метод ветвей и границ 187
Эвристики 191
Другие сложные задачи 207
Задача о выполнимости 207
Задача о разбиении 208
Задача поиска Гамильтонова пути 209
Задача коммивояжера 210
Задача о пожарных депо 211
Краткая характеристика сложных задач 212
Резюме 212
Глава 9. Сортировка 213
Общие соображения 213
Таблицы указателей 213
Объединение и сжатие ключей 215
Примеры программ 217
Сортировка выбором 219
Рандомизация 220
Сортировка вставкой 221
Вставка в связных списках 222
Пузырьковая сортировка 224
Быстрая сортировка 227
Сортировка слиянием 232
Пирамидальная сортировка 234
Пирамиды 235
Приоритетные очереди 237
Алгоритм пирамидальной сортировки 240
Сортировка подсчетом 241
Блочная сортировка 242
Блочная сортировка с применением связного списка 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-й версии, но
никаких изменений в код вносить не придется. Все алгоритмы были
протестированы в обеих версиях.
Эти программы демонстрируют использование алгоритмов без применения
объектно-ориентированного подхода. Ссылки и коллекции облегчают
программирование, но их применение может приводить к некоторому замедлению
работы программ по сравнению со старыми версиями.
Тем не менее, игнорирование классов, объектов и коллекций привело бы к
упущению многих действительно мощных свойств. Их использование позволяет
достичь нового уровня модульности, разработки и повторного использования
кода. Их, безусловно, необходимо иметь в виду, по крайней мере, на
начальных этапах разработки. В дальнейшем, если возникнут проблемы с
производительностью, вы сможете модифицировать код, используя более быстрые
низкоуровневые методы.
Языки программирования зачастую развиваются в сторону усложнения, но редко
в противоположном направлении. Замечательным примером этого является
наличие оператора 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 посвящена, пожалуй, наиболее изучаемой области теории
алгоритмов — сортировке. Алгоритмы сортировки интересны по нескольким
причинам. Во-первых, сортировка — часто встречающаяся задача. Во-вторых,
различные алгоритмы сортировок обладают своими сильными и слабыми
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31
|