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

Страницы: 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, 32, 33