Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
TOC o «1-3» Введение… PAGEREF_Toc3148911 h 8
Целевая аудитория… PAGEREF_Toc3148912 h 10
Глава 1. Основные понятия… PAGEREF_Toc3148913 h 15
Что такое алгоритмы?… PAGEREF_Toc3148914 h 15
Анализ скорости выполнения алгоритмов… PAGEREF_Toc3148915 h 16
Пространство — время… PAGEREF_Toc3148916 h 17
Оценка с точностью до порядка… PAGEREF_Toc3148917 h 17
Поиск сложных частей алгоритма… PAGEREF_Toc3148918 h 19
Сложность рекурсивных алгоритмов… PAGEREF_Toc3148919 h 20
Многократная рекурсия… PAGEREF_Toc3148920 h 21
Косвенная рекурсия… PAGEREF_Toc3148921 h 22
Требования рекурсивных алгоритмов к объему памяти… PAGEREF_Toc3148922 h 22
Наихудший и усредненный случай… PAGEREF_Toc3148923 h 23
Часто встречающиеся функции оценки порядка сложности… PAGEREF_Toc3148924 h 24
Логарифмы… PAGEREF_Toc3148925 h 25
Реальные условия — насколько быстро?… PAGEREF_Toc3148926 h 25
Обращение к файлу подкачки… PAGEREF_Toc3148927 h 26
Псевдоуказатели, ссылки на объекты и коллекции… PAGEREF_Toc3148928 h 27
Резюме… PAGEREF_Toc3148929 h 29
Глава 2. Списки… PAGEREF_Toc3148930 h 30
Знакомство со списками… PAGEREF_Toc3148931 h 31
Простые списки… PAGEREF_Toc3148932 h 31
Коллекции… PAGEREF_Toc3148933 h 32
Список переменного размера… PAGEREF_Toc3148934 h 33
Класс SimpleList… PAGEREF_Toc3148935 h 36
Неупорядоченные списки… PAGEREF_Toc3148936 h 37
Связные списки… PAGEREF_Toc3148937 h 41
Добавление элементов к связному списку… PAGEREF_Toc3148938 h 43
Удаление элементов из связного списка… PAGEREF_Toc3148939 h 44
Уничтожение связного списка… PAGEREF_Toc3148940 h 44
Сигнальные метки… PAGEREF_Toc3148941 h 45
Инкапсуляция связных списков… PAGEREF_Toc3148942 h 46
Доступ к ячейкам… PAGEREF_Toc3148943 h 47
Разновидности связных списков… PAGEREF_Toc3148944 h 49
Циклические связные списки… PAGEREF_Toc3148945 h 49
Проблема циклических ссылок… PAGEREF_Toc3148946 h 50
Двусвязные списки… PAGEREF_Toc3148947 h 50
Потоки… PAGEREF_Toc3148948 h 53
Другие связные структуры… PAGEREF_Toc3148949 h 56
Псевдоуказатели… PAGEREF_Toc3148950 h 56
Резюме… PAGEREF_Toc3148951 h 59
Глава 3. Стеки и очереди… PAGEREF_Toc3148952 h 60
Стеки… PAGEREF_Toc3148953 h 60
Множественные стеки… PAGEREF_Toc3148954 h 62
Очереди… PAGEREF_Toc3148955 h 63
Циклические очереди… PAGEREF_Toc3148956 h 65
Очереди на основе связных списков… PAGEREF_Toc3148957 h 69
Применение коллекций в качестве очередей… PAGEREF_Toc3148958 h 70
Приоритетные очереди… PAGEREF_Toc3148959 h 70
Многопоточные очереди… PAGEREF_Toc3148960 h 72
Резюме… PAGEREF_Toc3148961 h 74
Глава 4. Массивы… PAGEREF_Toc3148962 h 75
Треугольные массивы… PAGEREF_Toc3148963 h 75
Диагональные элементы… PAGEREF_Toc3148964 h 77
Нерегулярные массивы… PAGEREF_Toc3148965 h 78
Прямая звезда… PAGEREF_Toc3148966 h 78
Нерегулярные связные списки… PAGEREF_Toc3148967 h 79
Разреженные массивы… PAGEREF_Toc3148968 h 80
Индексирование массива… PAGEREF_Toc3148969 h 82
Очень разреженные массивы… PAGEREF_Toc3148970 h 85
Резюме… PAGEREF_Toc3148971 h 86
Глава 5. Рекурсия… PAGEREF_Toc3148972 h 86
Что такое рекурсия?… PAGEREF_Toc3148973 h 87
Рекурсивное вычисление факториалов… PAGEREF_Toc3148974 h 88
Анализ времени выполнения программы… PAGEREF_Toc3148975 h 89
Рекурсивное вычисление наибольшего общего делителя… PAGEREF_Toc3148976 h 90
Анализ времени выполнения программы… PAGEREF_Toc3148977 h 91
Рекурсивное вычисление чисел Фибоначчи… PAGEREF_Toc3148978 h 92
Анализ времени выполнения программы… PAGEREF_Toc3148979 h 93
Рекурсивное построение кривых Гильберта… PAGEREF_Toc3148980 h 94
Анализ времени выполнения программы… PAGEREF_Toc3148981 h 96
Рекурсивное построение кривых Серпинского… PAGEREF_Toc3148982 h 98
Анализ времени выполнения программы… PAGEREF_Toc3148983 h 100
Опасности рекурсии… PAGEREF_Toc3148984 h 101
Бесконечная рекурсия… PAGEREF_Toc3148985 h 101
Потери памяти… PAGEREF_Toc3148986 h 102
Необоснованное применение рекурсии… PAGEREF_Toc3148987 h 103
Когда нужно использовать рекурсию… PAGEREF_Toc3148988 h 104
Хвостовая рекурсия… PAGEREF_Toc3148989 h 105
Нерекурсивное вычисление чисел Фибоначчи… PAGEREF_Toc3148990 h 107
Устранение рекурсии в общем случае… PAGEREF_Toc3148991 h 110
Нерекурсивное построение кривых Гильберта… PAGEREF_Toc3148992 h 114
Нерекурсивное построение кривых Серпинского… PAGEREF_Toc3148993 h 117
Резюме… PAGEREF_Toc3148994 h 121
Глава 6. Деревья… PAGEREF_Toc3148995 h 121
Определения… PAGEREF_Toc3148996 h 122
Представления деревьев… PAGEREF_Toc3148997 h 123
Полные узлы… PAGEREF_Toc3148998 h 123
Списки потомков… PAGEREF_Toc3148999 h 124
Представление нумерацией связей… PAGEREF_Toc3149000 h 126
Полные деревья… PAGEREF_Toc3149001 h 129
Обход дерева… PAGEREF_Toc3149002 h 130
Упорядоченные деревья… PAGEREF_Toc3149003 h 135
Добавление элементов… PAGEREF_Toc3149004 h 135
Удаление элементов… PAGEREF_Toc3149005 h 136
Обход упорядоченных деревьев… PAGEREF_Toc3149006 h 139
Деревья со ссылками… PAGEREF_Toc3149007 h 141
Работа с деревьями со ссылками… PAGEREF_Toc3149008 h 144
Квадродеревья… PAGEREF_Toc3149009 h 145
Изменение MAX_PER_NODE… PAGEREF_Toc3149010 h 151
Использование псевдоуказателей в квадродеревьях… PAGEREF_Toc3149011 h 151
Восьмеричные деревья… PAGEREF_Toc3149012 h 152
Резюме… PAGEREF_Toc3149013 h 152
Глава 7. Сбалансированные деревья… PAGEREF_Toc3149014 h 153
Сбалансированность дерева… PAGEREF_Toc3149015 h 153
АВЛ‑деревья… PAGEREF_Toc3149016 h 154
Удаление узла из АВЛ‑дерева… PAGEREF_Toc3149017 h 161
Б‑деревья… PAGEREF_Toc3149018 h 166
Производительность Б‑деревьев… PAGEREF_Toc3149019 h 167
Вставка элементов в Б‑дерево… PAGEREF_Toc3149020 h 167
Удаление элементов из Б‑дерева… PAGEREF_Toc3149021 h 168
Разновидности Б‑деревьев… PAGEREF_Toc3149022 h 169
Улучшение производительности Б‑деревьев… PAGEREF_Toc3149023 h 171
Балансировка для устранения разбиения блоков… PAGEREF_Toc3149024 h 171
Вопросы, связанные с обращением к диску… PAGEREF_Toc3149025 h 173
База данных на основе Б+дерева… PAGEREF_Toc3149026 h 176
Резюме… PAGEREF_Toc3149027 h 179
Глава 8. Деревья решений… PAGEREF_Toc3149028 h 179
Поиск в деревьях игры… PAGEREF_Toc3149029 h 180
Минимаксный поиск… PAGEREF_Toc3149030 h 181
Улучшение поиска в дереве игры… PAGEREF_Toc3149031 h 185
Поиск в других деревьях решений… PAGEREF_Toc3149032 h 187
Метод ветвей и границ… PAGEREF_Toc3149033 h 187
Эвристики… PAGEREF_Toc3149034 h 191
Другие сложные задачи… PAGEREF_Toc3149035 h 207
Задача о выполнимости… PAGEREF_Toc3149036 h 207
Задача о разбиении… PAGEREF_Toc3149037 h 208
Задача поиска Гамильтонова пути… PAGEREF_Toc3149038 h 209
Задача коммивояжера… PAGEREF_Toc3149039 h 210
Задача о пожарных депо… PAGEREF_Toc3149040 h 211
Краткая характеристика сложных задач… PAGEREF_Toc3149041 h 212
Резюме… PAGEREF_Toc3149042 h 212
Глава 9. Сортировка… PAGEREF_Toc3149043 h 213
Общие соображения… PAGEREF_Toc3149044 h 213
Таблицы указателей… PAGEREF_Toc3149045 h 213
Объединение и сжатие ключей… PAGEREF_Toc3149046 h 215
Примеры программ… PAGEREF_Toc3149047 h 217
Сортировка выбором… PAGEREF_Toc3149048 h 219
Рандомизация… PAGEREF_Toc3149049 h 220
Сортировка вставкой… PAGEREF_Toc3149050 h 221
Вставка в связных списках… PAGEREF_Toc3149051 h 222
Пузырьковая сортировка… PAGEREF_Toc3149052 h 224
Быстрая сортировка… PAGEREF_Toc3149053 h 227
Сортировка слиянием… PAGEREF_Toc3149054 h 232
Пирамидальная сортировка… PAGEREF_Toc3149055 h 234
Пирамиды… PAGEREF_Toc3149056 h 235
Приоритетные очереди… PAGEREF_Toc3149057 h 237
Алгоритм пирамидальной сортировки… PAGEREF_Toc3149058 h 240
Сортировка подсчетом… PAGEREF_Toc3149059 h 241
Блочная сортировка… PAGEREF_Toc3149060 h 242
Блочная сортировка с применением связного списка… PAGEREF_Toc3149061 h 243
Блочная сортировка на основе массива… PAGEREF_Toc3149062 h 245
Резюме… PAGEREF_Toc3149063 h 248
Глава 10. Поиск… PAGEREF_Toc3149064 h 248
Примеры программ… PAGEREF_Toc3149065 h 249
Поиск методом полного перебора… PAGEREF_Toc3149066 h 249
Поиск в упорядоченных списках… PAGEREF_Toc3149067 h 250
Поиск в связных списках… PAGEREF_Toc3149068 h 251
Двоичный поиск… PAGEREF_Toc3149069 h 253
Интерполяционный поиск… PAGEREF_Toc3149070 h 255
Строковые данные… PAGEREF_Toc3149071 h 259
Следящий поиск… PAGEREF_Toc3149072 h 260
Интерполяционный следящий поиск… PAGEREF_Toc3149073 h 261
Резюме… PAGEREF_Toc3149074 h 262
Глава 11. Хеширование… PAGEREF_Toc3149075 h 263
Связывание… PAGEREF_Toc3149076 h 265
Преимущества и недостатки связывания… PAGEREF_Toc3149077 h 266
Блоки… PAGEREF_Toc3149078 h 268
Хранение хеш‑таблиц на диске… PAGEREF_Toc3149079 h 270
Связывание блоков… PAGEREF_Toc3149080 h 274
Удаление элементов… PAGEREF_Toc3149081 h 275
Преимущества и недостатки применения блоков… PAGEREF_Toc3149082 h 277
Открытая адресация… PAGEREF_Toc3149083 h 277
Линейная проверка… PAGEREF_Toc3149084 h 278
Квадратичная проверка… PAGEREF_Toc3149085 h 284
Псевдослучайная проверка… PAGEREF_Toc3149086 h 286
Удаление элементов… PAGEREF_Toc3149087 h 289
Резюме… PAGEREF_Toc3149088 h 291
Глава 12. Сетевые алгоритмы… PAGEREF_Toc3149089 h 292
Определения… PAGEREF_Toc3149090 h 292
Представления сети… PAGEREF_Toc3149091 h 293
Оперирование узлами и связями… PAGEREF_Toc3149092 h 295
Обходы сети… PAGEREF_Toc3149093 h 296
Наименьшие остовные деревья… PAGEREF_Toc3149094 h 298
Кратчайший маршрут… PAGEREF_Toc3149095 h 302
Установка меток… PAGEREF_Toc3149096 h 304
Коррекция меток… PAGEREF_Toc3149097 h 308
Другие задачи поиска кратчайшего маршрута… PAGEREF_Toc3149098 h 311
Применения метода поиска кратчайшего маршрута… PAGEREF_Toc3149099 h 316
Максимальный поток… PAGEREF_Toc3149100 h 319
Приложения максимального потока… PAGEREF_Toc3149101 h 325
Резюме… PAGEREF_Toc3149102 h 327
Глава 13. Объектно‑ориентированные методы… PAGEREF_Toc3149103 h 327
Преимущества ООП… PAGEREF_Toc3149104 h 328
Инкапсуляция… PAGEREF_Toc3149105 h 328
Полиморфизм… PAGEREF_Toc3149106 h 330
Наследование и повторное использование… PAGEREF_Toc3149107 h 333
Парадигмы ООП… PAGEREF_Toc3149108 h 335
Управляющие объекты… PAGEREF_Toc3149109 h 335
Контролирующий объект… PAGEREF_Toc3149110 h 336
Итератор… PAGEREF_Toc3149111 h 337
Дружественный класс… PAGEREF_Toc3149112 h 338
Интерфейс… PAGEREF_Toc3149113 h 340
Фасад… PAGEREF_Toc3149114 h 340
Порождающий объект… PAGEREF_Toc3149115 h 340
Единственный объект… PAGEREF_Toc3149116 h 341
Преобразование в последовательную форму… PAGEREF_Toc3149117 h 341
Парадигма Модель/Вид/Контроллер.… PAGEREF_Toc3149118 h 344
Резюме… PAGEREF_Toc3149119 h 346
Требования к аппаратному обеспечению… PAGEREF_Toc3149120 h 346
Выполнение программ примеров… PAGEREF_Toc3149121 h 346
programmer@newmail.ru
Далее следует «текст», который любой уважающий себя программист должен прочесть хотябы один раз. (Это наше субъективноемнение)
<span Times New Roman",«serif»; text-transform:uppercase">ВведениеПрограммирование под Windows всегда было нелегкой задачей. Интерфейс прикладногопрограммирования (ApplicationProgrammingInterface) Windows предоставляет в распоряжение программиста набор мощных,но не всегда безопасных инструментов для разработки приложений. Можно сравнитьего с бульдозером, при помощи которого удается добиться поразительныхрезультатов, но без соответствующих навыков и осторожности, скорее всего, делозакончится только разрушениями и убытками.
Эта картина изменилась с появлением VisualBasic. Используя визуальныйинтерфейс, VisualBasicпозволяет быстро и легко разрабатывать законченные приложения. При помощи VisualBasicможноразрабатывать и тестировать сложные приложения без прямого использованияфункций API. Избавляя программиста от проблем с API, VisualBasic позволяетсконцентрироваться на деталях приложения.
Хотя VisualBasicи облегчает разработку пользовательского интерфейса, задача написания кода дляреакции на входные воздействия, обработки их, и представления результатовложится на плечи программиста. Здесь начинается применение алгоритмов.
Алгоритмы представляют собой формальные инструкции длявыполнения сложных задач на компьютере. Например, алгоритм сортировки можетопределять, как найти конкретную запись в базе из 10 миллионов записей. Взависимости от класса используемых алгоритмов искомые данные могут быть найденыза секунды, часы или вообще не найдены.
В этом материале обсуждаются алгоритмы на VisualBasic и содержится большоечисло мощных алгоритмов, полностью написанных на этом языке. В ней такжеанализируются методы обращения со структурами данных, такими, как списки,стеки, очереди и деревья, и алгоритмы для выполнения типичных задач, таких каксортировка, поиск и хэширование.
Для того чтобы успешно применять эти алгоритмы, недостаточноих просто скопировать в свою программу. Необходимо кроме этого понимать, какразличные алгоритмы ведут себя в разных ситуациях, что в конечном итоге и будетопределять выбор наиболее подходящего алгоритма.
В этом материале поведение алгоритмов в типичном и наихудшемслучаях описано доступным языком. Это позволит понять, чего вы вправе ожидатьот того или иного алгоритма и распознать, в каких условиях встречаетсянаихудший случай, и в соответствии с этим переписать или поменять алгоритм.Даже самый лучший алгоритм не поможет в решении задачи, если применять егонеправильно.
=============xi
Все алгоритмы также представлены в виде исходных текстов на VisualBasic, которые вы можетеиспользовать в своих программах без каких‑либо изменений. Онидемонстрируют использование алгоритмов в программах, а также важные характерныеособенности работы самих алгоритмов.
<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»">Что дают вам эти знания
После ознакомления с данным материалом и примерами выполучите:
1.<span Times New Roman"">
Понятие об алгоритмах. После прочтенияданного материала и выполнения примеров программ, вы сможете применять сложныеалгоритмы в своих проектах на VisualBasicи критически оценивать другие алгоритмы, написанные вами или кем‑либоеще.2.<span Times New Roman"">
Большую подборку исходных текстов,которые вы сможете легко добавить к вашим программам. Используя код,содержащийся в примерах, вы сможете легко добавлять мощные алгоритмы к вашимприложениям.3.<span Times New Roman"">
Готовые примеры программ дадут вамвозможность протестировать алгоритмы. Вы можете использовать эти примеры имодифицировать их для углубленного изучения алгоритмов и понимания их работы,или использовать их как основу для разработки собственных приложений.ЦелеваяаудиторияВ этом материале обсуждаются углубленные вопросыпрограммирования на VisualBasic.Они не предназначена для обучения программированию на этом языке. Если выхорошо разбираетесь в основах программирования на VisualBasic, вы сможетесконцентрировать внимание на алгоритмах вместо того, чтобы застревать надеталях языка.
В этом материале изложены важные концепции программирования,которые могут быть с успехом применены для решения новых задач. Приведенныеалгоритмы используют мощные программные методы, такие как рекурсия, разбиениена части, динамическое распределение памяти и сетевые структуры данных, которыевы можете применять для решения своих конкретных задач.
Даже если вы еще не овладели в полной мере программированиемна VisualBasic,вы сможете скомпилировать примеры программ и сравнить производительностьразличных алгоритмов. Более того, вы сможете выбрать удовлетворяющие вашимтребованиям алгоритмы и добавить их к вашим проектам на VisualBasic.
<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»">Совместимость с разными версиями
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">Visual<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">Basic<span Arial",«sans-serif»; mso-bidi-font-family:«Times Ne