 |
ГЛАВНАЯ | ПОИСК | ТОП | КАРТА САЙТА |
 |
 |
|
Стивенс Род >> Готовые алгоритмы на Visual Basic (страница 1)Готовые алгоритмы на Visual Basic(автор Стивенс Род)
Глава 1
Введение 8 Целевая аудитория 10 Что находится на компакт‑диске 13 Глава 1. Основные понятия 17 Что такое алгоритмы? 18 Анализ скорости выполнения алгоритмов 19 Пространство — время 19 Оценка с точностью до порядка 20 Поиск сложных частей алгоритма 22 Сложность рекурсивных алгоритмов 23 Многократная рекурсия 24 Косвенная рекурсия 25 Требования рекурсивных алгоритмов к объему памяти 25 Наихудший и усредненный случай 26 Часто встречающиеся функции оценки порядка сложности 27 Логарифмы 28 Реальные условия — насколько быстро? 29 Обращение к файлу подкачки 30 Псевдоуказатели, ссылки на объекты и коллекции 32 Резюме 34 Глава 2. Списки 35 Знакомство со списками 36 Простые списки 37 Коллекции 37 Список переменного размера 38 Класс SimpleList 41 Неупорядоченные списки 43 Связные списки 47 Добавление элементов к связному списку 50 Удаление элементов из связного списка 51 Уничтожение связного списка 51 Сигнальные метки 52 Инкапсуляция связных списков 53 Доступ к ячейкам 54 Разновидности связных списков 56 Циклические связные списки 56 Проблема циклических ссылок 57 Двусвязные списки 58 Потоки 61 Другие связные структуры 64 Псевдоуказатели 65 Резюме 68 Глава 3. Стеки и очереди 68 Стеки 69 Множественные стеки 71 Очереди 72 Циклические очереди 75 Очереди на основе связных списков 79 Применение коллекций в качестве очередей 80 Приоритетные очереди 80 Многопоточные очереди 83 Резюме 85 Глава 4. Массивы 86 Треугольные массивы 86 Диагональные элементы 89 Нерегулярные массивы 89 Прямая звезда 90 Нерегулярные связные списки 91 Разреженные массивы 92 Индексирование массива 94 Очень разреженные массивы 97 Резюме 98 Глава 5. Рекурсия 98 Что такое рекурсия? 99 Рекурсивное вычисление факториалов 100 Анализ времени выполнения программы 102 Рекурсивное вычисление наибольшего общего делителя 103 Анализ времени выполнения программы 104 Рекурсивное вычисление чисел Фибоначчи 105 Анализ времени выполнения программы 106 Рекурсивное построение кривых Гильберта 108 Анализ времени выполнения программы 110 Рекурсивное построение кривых Серпинского 112 Анализ времени выполнения программы 114 Опасности рекурсии 115 Бесконечная рекурсия 116 Потери памяти 117 Необоснованное применение рекурсии 118 Когда нужно использовать рекурсию 119 Хвостовая рекурсия 120 Нерекурсивное вычисление чисел Фибоначчи 123 Устранение рекурсии в общем случае 126 Нерекурсивное построение кривых Гильберта 130 Нерекурсивное построение кривых Серпинского 134 Резюме 137 Глава 6. Деревья 138 Определения 139 Представления деревьев 140 Полные узлы 140 Списки потомков 141 Представление нумерацией связей 143 Полные деревья 147 Обход дерева 148 Упорядоченные деревья 153 Добавление элементов 154 Удаление элементов 155 Обход упорядоченных деревьев 158 Деревья со ссылками 160 Работа с деревьями со ссылками 163 Квадродеревья 165 Изменение MAX_PER_NODE 171 Использование псевдоуказателей в квадродеревьях 171 Восьмеричные деревья 172 Резюме 172 Глава 7. Сбалансированные деревья 173 Сбалансированность дерева 173 АВЛ‑деревья 174 Удаление узла из АВЛ‑дерева 182 Б‑деревья 187 Производительность Б‑деревьев 188 Вставка элементов в Б‑дерево 189 Удаление элементов из Б‑дерева 190 Разновидности Б‑деревьев 192 Улучшение производительности Б‑деревьев 194 Балансировка для устранения разбиения блоков 194 Вопросы, связанные с обращением к диску 196 База данных на основе Б+дерева 199 Резюме 203 Глава 8. Деревья решений 203 Поиск в деревьях игры 204 Минимаксный поиск 205 Улучшение поиска в дереве игры 210 Поиск в других деревьях решений 212 Метод ветвей и границ 212 Эвристики 217 Другие сложные задачи 234 Задача о выполнимости 235 Задача о разбиении 236 Задача поиска Гамильтонова пути 237 Задача коммивояжера 238 Задача о пожарных депо 239 Краткая характеристика сложных задач 240 Резюме 241 Глава 9. Сортировка 241 Общие соображения 242 Таблицы указателей 242 Объединение и сжатие ключей 244 Примеры программ 247 Сортировка выбором 248 Рандомизация 250 Сортировка вставкой 251 Вставка в связных списках 252 Пузырьковая сортировка 254 Быстрая сортировка 258 Сортировка слиянием 263 Пирамидальная сортировка 265 Пирамиды 266 Приоритетные очереди 268 Алгоритм пирамидальной сортировки 271 Сортировка подсчетом 273 Блочная сортировка 275 Блочная сортировка с применением связного списка 276 Блочная сортировка на основе массива 278 Резюме 280 Глава 10. Поиск 281 Примеры программ 281 Поиск методом полного перебора 282 Поиск в упорядоченных списках 283 Поиск в связных списках 284 Двоичный поиск 286 Интерполяционный поиск 288 Строковые данные 293 Следящий поиск 294 Интерполяционный следящий поиск 295 Резюме 296 Глава 11. Хеширование 298 Связывание 300 Преимущества и недостатки связывания 301 Блоки 303 Хранение хеш‑таблиц на диске 306 Связывание блоков 310 Удаление элементов 312 Преимущества и недостатки применения блоков 313 Открытая адресация 314 Линейная проверка 314 Квадратичная проверка 321 Псевдослучайная проверка 324 Удаление элементов 327 Резюме 330 Глава 12. Сетевые алгоритмы 331 Определения 331 Представления сети 332 Оперирование узлами и связями 334 Обходы сети 335 Наименьшие остовные деревья 338 Кратчайший маршрут 341 Установка меток 344 Коррекция меток 348 Другие задачи поиска кратчайшего маршрута 352 Применения метода поиска кратчайшего маршрута 358 Максимальный поток 361 Приложения максимального потока 368 Резюме 370 Глава 13. Объектно‑ориентированные методы 371 Преимущества ООП 371 Инкапсуляция 372 Полиморфизм 374 Наследование и повторное использование 378 Парадигмы ООП 379 Управляющие объекты 380 Контролирующий объект 382 Итератор 383 Дружественный класс 384 Интерфейс 385 Фасад 386 Порождающий объект 386 Единственный объект 387 Преобразование в последовательную форму 388 Парадигма Модель/Вид/Контроллер. 390 Резюме 393 Приложение 1. Использование компакт‑диска 393 Что находится на компакт‑диске 393 Требования к аппаратному обеспечению 394 Установки исходного кода 394 Выполнение программ примеров 395 Информация и поддержка пользователей 395 Приложение 2. Список примеров программ 396 Введение Программирование под 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 Выбор наилучшего алгоритма определяется не особенностями версии языка программирования, а фундаментальными принципами программирования. Первое издание книги включало код для 3-й версии Visual Basic. Несколько лет спустя, эти алгоритмы все еще работают в 4-й и 5-й версиях этой программной среды. =================xii Некоторые новые понятия, такие как ссылки на объекты, классы и коллекции, которые были впервые введены в 4-й версии Visual Basic, облегчают понимание, разработку и отладку некоторых алгоритмов. Классы могут заключать некоторые алгоритмы в хорошо продуманных модулях, которые легко вставить в программу. Хотя для того, чтобы применять эти алгоритмы, необязательно разбираться в новых понятиях языка, эти новые возможности предоставляют слишком большие преимущества, чтобы ими можно было пренебречь. Поэтому примеры алгоритмов в этой книге написаны для использования в 4-й и 5-й версиях Visual Basic и находятся на компакт‑диске в формате 4-й версии. Если вы откроете их в 5-й версии Visual Basic, среда разработки предложит вам сохранить их в формате 5-й версии, но никаких изменений в код вносить не придется. Все алгоритмы были протестированы в обеих версиях. Также на компакт‑диске содержатся исходные тексты алгоритмов из первого издания книги для 3-й версии Visual Basic. Эти программы демонстрируют использование алгоритмов без применения объектно-ориентированного подхода. Ссылки и коллекции облегчают программирование, но их применение может приводить к некоторому замедлению работы программ по сравнению со старыми версиями. Тем не менее, игнорирование классов, объектов и коллекций привело бы к упущению многих действительно мощных свойств. Их использование позволяет достичь нового уровня модульности, разработки и повторного использования кода. Их, безусловно, необходимо иметь в виду, по крайней мере, на начальных этапах разработки. В дальнейшем, если возникнут проблемы с производительностью, вы сможете модифицировать код, используя более быстрые низкоуровневые методы. |
 |
 |