|
Реферат: 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 посвящена, пожалуй, наиболее изучаемой области теории
алгоритмов — сортировке. Алгоритмы сортировки интересны по нескольким
причинам. Во-первых, сортировка — часто встречающаяся задача. Во-вторых,
различные алгоритмы сортировок обладают своими сильными и слабыми
сторонами, поэтому не существует одного алгоритма, который показывал бы
наилучшие результаты в любых ситуациях. И, наконец, алгоритмы сортировки
демонстрируют широкий спектр важных алгоритмических методов, таких как
рекурсия, пирамиды, а также использование генератора случайных чисел для
уменьшения вероятности выпадения наихудшего случая.
В главе 10 рассматривается близкая к сортировке тема. После выполнения
сортировки списка, программе может понадобиться найти элементы в нем. В
этой главе сравнивается несколько наиболее эффективных методов поиска
элементов в сортированных списках.
=========xiv
В главе 11 обсуждаются методы сохранения и поиска элементов, работающие
даже быстрее, чем это возможно при использовании деревьев, сортировки или
поиска. В этой главе также описаны некоторые методы хэширования, включая
использование блоков и связных списков, и несколько вариантов открытой
адресации.
В главе 12 описана другая категория алгоритмов — сетевые алгоритмы.
Некоторые из этих алгоритмов, такие как вычисление кратчайшего пути,
непосредственно применимы к физическим сетям. Эти алгоритмы также могут
косвенно применяться для решения других задач, которые на первый взгляд не
кажутся связанными с сетями. Например, алгоритмы поиска кратчайшего
расстояния могут разбивать сеть на районы или определять критичные задачи в
расписании проекта.
В главе 13 объясняются методы, применение которых стало возможным благодаря
введению классов в 4-й версии Visual Basic. Эти методы используют объектно-
ориентированный подход для реализации нетипичного для традиционных
алгоритмов поведения.
===================xv
Аппаратные требования
Для работы с примерами вам потребуется компьютер, конфигурация которого
удовлетворяет требованиям для работы программной среды Visual Basic. Эти
требования выполняются почти для всех компьютеров, на которых может
работать операционная система Windows.
На компьютерах разной конфигурации алгоритмы выполняются с различной
скоростью. Компьютер с процессором Pentium Pro с тактовой частотой 2000 МГц
и 64 Мбайт оперативной памяти будет работать намного быстрее, чем машина с
386 процессором и всего 4 Мбайт памяти. Вы быстро узнаете, на что способно
ваше аппаратное обеспечение.
Изменения во втором издании
Самое большое изменение в новой версии Visual Basic — это появление
классов. Классы позволяют рассмотреть некоторые задачи с другой стороны,
позволяя использовать более простой и естественный подход к пониманию и
применению многих алгоритмов. Изменения в коде программ в этом изложении
используют преимущества, предоставляемые классами. Их можно разбить на три
категории:
1. Замена псевдоуказателей классами. Хотя все алгоритмы, которые были
написаны для старых версий VB, все еще работают, многие из тех, что были
написаны с применением псевдоуказателей (описанных во 2 главе), гораздо
проще понять, используя классы.
2. Инкапсуляция. Классы позволяют заключить алгоритм в компактный модуль,
который легко использовать в программе. Например, при помощи классов
можно создать несколько связных списков и не писать при этом
дополнительный код для управления каждым списком по отдельности.
3. Объектно-ориентированные технологии. Использование классов также
позволяет легче понять некоторые объектно-ориентированные алгоритмы. В
главе 13 описываются методы, которые сложно реализовать без использования
классов.
Как пользоваться этим материалом
В главе 1 даются общие понятия, которые используются на протяжении всего
изложения, поэтому вам следует начать чтение с этой главы. Вам стоит
ознакомиться с этой тематикой, даже если вы не хотите сразу же достичь
глубокого понимания алгоритмов.
В 6 главе обсуждаются понятия, которые используются в 7, 8 и 12 главах,
поэтому вам следует прочитать 6 главу до того, как браться за них.
Остальные главы можно читать в любом порядке.
=============xvi
В табл. 1 показаны три возможных учебных плана, которыми вы можете
руководствоваться при изучении материала в зависимости от того, насколько
широко вы хотите ознакомиться с алгоритмами. Первый план включает в себя
освоение основных методов и структур данных, которые могут быть полезны при
разработке вами собственных программ. Второй кроме этого описывает также
основные алгоритмы, такие как алгоритмы сортировки и поиска, которые могут
понадобиться при написании более сложных программ.
Последний план дает порядок для изучения всего материала целиком. Хотя 7
и 8 главы логически вытекают из 6 главы, они сложнее для изучения, чем
следующие главы, поэтому они изучаются несколько позже.
Почему именно Visual Basic?
Наиболее часто встречаются жалобы на медленное выполнение программ,
написанных на Visual Basic. Многие другие компиляторы, такие как Delphi,
Visual C++ дают более быстрый и гибкий код, и предоставляют программисту
более мощные средства, чем Visual Basic. Поэтому логично задать вопрос —
«Почему я должен использовать именно Visual Basic для написания сложных
алгоритмов? Не лучше было бы использовать Delphi или C++ или, по крайней
мере, написать алгоритмы на одном из этих языков и подключать их к
программам на Visual Basic при помощи библиотек?» Написание алгоритмов на
Visual Basic имеет смысл по нескольким причинам.
Во-первых, разработка приложения на Visual C++ гораздо сложнее и
проблематичнее, чем на Visual Basic. Некорректная реализация в программе
всех деталей программирования под Windows может привести к сбоям в вашем
приложении, среде разработки, или в самой операционной системе Windows.
Во-вторых, разработка библиотеки на языке C++ для использования в
программах на Visual Basic включает в себя много потенциальных опасностей,
характерных и для приложений Windows, написанных на C++. Если библиотека
будет неправильно взаимодействовать с программой на Visual Basic, она также
приведет к сбоям в программе, а возможно и в среде разработки и системе.
В-третьих, многие алгоритмы достаточно эффективны и показывают неплохую
производительность даже при применении не очень быстрых компиляторов,
таких, как Visual Basic. Например, алгоритм сортировки подсчетом,
@Таблица 1. Планы занятий
===============xvii
описываемый в 9 главе, сортирует миллион целых чисел менее чем за 2 секунды
на компьютере с процессором Pentium с тактовой частотой 233 МГц. Используя
библиотеку C++, можно было бы сделать алгоритм немного быстрее, но скорости
версии на Visual Basic и так хватает для большинства приложений.
Скомпилированные при помощи 5-й версией Visual Basic исполняемые файлы
сводят отставание по скорости к минимуму.
В конечном счете, разработка алгоритмов на любом языке программирования
позволяет больше узнать об алгоритмах вообще. По мере изучения алгоритмов,
вы освоите методы, которые сможете применять в других частях своих
программ. После того, как вы овладеете в совершенстве алгоритмами на Visual
Basic, вам будет гораздо легче реализовать их на Delphi или C++, если это
будет необходимо.
=============xviii
Глава 1. Основные понятия
В этой главе содержатся общие понятия, которые нужно усвоить перед началом
серьезного изучения алгоритмов. Начинается она с вопроса «Что такое
алгоритмы?». Прежде чем углубиться в детали программирования алгоритмов,
стоит потратить немного времени, чтобы разобраться в том, что это такое.
Затем в этой главе дается введение в формальную теорию сложности алгоритмов
(complexity theory). При помощи этой теории можно оценить теоретическую
вычислительную сложность алгоритмов. Этот подход позволяет сравнивать
различные алгоритмы и предсказывать их производительность в разных
условиях. В главе приводится несколько примеров применения теории сложности
к небольшим задачам.
Некоторые алгоритмы с высокой теоретической производительностью не слишком
хорошо работают на практике, поэтому в данной главе также обсуждаются
некоторые реальные предпосылки для создания программ. Слишком частое
обращение к файлу подкачки или плохое использование ссылок на объекты и
коллекции может значительно снизить производительность прекрасного в
остальных отношениях приложения.
После знакомства с основными понятиями, вы сможете применять их к
алгоритмам, изложенным в последующих главах, а также для анализа
собственных программ для оценки их производительности и сможете
предугадывать возможные проблемы до того, как они обернутся катастрофой.
Что такое алгоритмы?
Алгоритм – это последовательность инструкций для выполнения какого-либо
задания. Когда вы даете кому-то инструкции о том, как отремонтировать
газонокосилку, испечь торт, вы тем самым задаете алгоритм действий.
Конечно, подобные бытовые алгоритмы описываются неформально, например, так:
Проверьте, находится ли машина на стоянке.
Убедитесь, что машина поставлена на ручной тормоз.
Поверните ключ.
И т.д.
==========1
При этом по умолчанию предполагается, что человек, который будет
следовать этим инструкциям, сможет самостоятельно выполнить множество
мелких операций, например, отпереть и открыть дверь, сесть за руль,
пристегнуть ремень, найти ручной тормоз и так далее.
Если же составляется алгоритм для исполнения компьютером, вы не можете
полагаться на то, что компьютер поймет что-либо, если это не описано
заранее. Словарь компьютера (язык программирования) очень ограничен и все
инструкции для компьютера должны быть сформулированы на этом языке. Поэтому
для написания компьютерных алгоритмов используется формализованный стиль.
Интересно попробовать написать формализованный алгоритм для обычных
ежедневных задач. Например, алгоритм вождения машины мог бы выглядеть
примерно так:
Если дверь закрыта:
Вставить ключ в замок
Повернуть ключ
Если дверь остается закрытой, то:
Повернуть ключ в другую сторону
Повернуть ручку двери
И т.д.
Этот фрагмент «кода» отвечает только за открывание двери; при этом даже не
проверяется, какая дверь открывается. Если дверь заело или в машине
установлена противоугонная система, то алгоритм открывания двери может быть
достаточно сложным.
Формализацией алгоритмов занимаются уже тысячи лет. За 300 лет до н.э.
Евклид написал алгоритмы деления углов пополам, проверки равенства
треугольников и решения других геометрических задач. Он начал с небольшого
словаря аксиом, таких как «параллельные линии не пересекаются» и построил
на их основе алгоритмы для решения сложных задач.
Формализованные алгоритмы такого типа хорошо подходят для задач математики,
где должна быть доказана истинность какого-либо положения или возможность
выполнения каких-то действий, скорость же исполнения алгоритма не важна.
Для выполнения реальных задач, связанных с выполнением инструкций, например
задачи сортировки на компьютере записей о миллионе покупателей,
эффективность выполнения становится важной частью постановки задачи.
Анализ скорости выполнения алгоритмов
Есть несколько способов оценки сложности алгоритмов. Программисты обычно
сосредотачивают внимание на скорости алгоритма, но важны и другие
требования, например, к размеру памяти, свободному месту на диске или
другим ресурсам. От быстрого алгоритма может быть мало толку, если под него
требуется больше памяти, чем установлено на компьютере.
Пространство — время
Многие алгоритмы предоставляют выбор между скоростью выполнения и
используемыми программой ресурсами. Задача может выполняться
быстрее, используя больше памяти, или наоборот, медленнее, заняв меньший
объем памяти.
===========2
Хорошим примером в данном случае может служить алгоритм нахождения
кратчайшего пути. Задав карту улиц города в виде сети, можно написать
алгоритм, вычисляющий кратчайшее расстояние между любыми двумя точками в
этой сети. Вместо того чтобы каждый раз заново пересчитывать кратчайшее
расстояние между двумя заданными точками, можно заранее просчитать его для
всех пар точек и сохранить результаты в таблице. Тогда, чтобы найти
кратчайшее расстояние для двух заданных точек, достаточно будет просто
взять готовое значение из таблицы.
При этом мы получим результат практически мгновенно, но это потребует
большого объема памяти. Карта улиц для большого города, такого как Бостон
или Денвер, может содержать сотни тысяч точек. Для такой сети таблица
кратчайших расстояний содержала бы более 10 миллиардов записей. В этом
случае выбор между временем исполнения и объемом требуемой памяти очевиден:
поставив дополнительные 10 гигабайт оперативной памяти, можно заставить
программу выполняться гораздо быстрее.
Из этой связи вытекает идея пространственно-временной сложности алгоритмов.
При этом подходе сложность алгоритма оценивается в терминах времени и
пространства, и находится компромисс между ними.
В этом материале основное внимание уделяется временной сложности, но мы
также постарались обратить внимание и на особые требования к объему памяти
для некоторых алгоритмов. Например, сортировка слиянием (mergesort),
обсуждаемая в 9 главе, требует больше временной памяти. Другие алгоритмы,
например пирамидальная сортировка (heapsort), которая также обсуждается в 9
главе, требует обычного объема памяти.
Оценка с точностью до порядка
При сравнении различных алгоритмов важно понимать, как сложность алгоритма
соотносится со сложностью решаемой задачи. При расчетах по одному алгоритму
сортировка тысячи чисел может занять 1 секунду, а сортировка миллиона — 10
секунд, в то время как расчеты по другому алгоритму могут потребовать 2 и 5
секунд соответственно. В этом случае нельзя однозначно сказать, какая из
двух программ лучше — это будет зависеть от исходных данных.
Различие производительности алгоритмов на задачах разной вычислительной
сложности часто более важно, чем просто скорость алгоритма. В
вышеприведенном случае, первый алгоритм быстрее сортирует короткие списки,
а второй — длинные.
Производительность алгоритма можно оценить по порядку величины. Алгоритм
имеет сложность порядка O(f(N)) (произносится «О большое от F от N»), если
время выполнения алгоритма растет пропорционально функции f(N) с
увеличением размерности исходных данных N. Например, рассмотрим фрагмент
кода, сортирующий положительные числа:
For I = 1 To N
'Поиск наибольшего элемента в списке.
MaxValue = 0
For J = 1 to N
If Value(J) > MaxValue Then
MaxValue = Value(J)
MaxJ = J
End If
Next J
'Вывод наибольшего элемента на печать.
Print Format$(MaxJ) & ":" & Str$(MaxValue)
'Обнуление элемента для исключения его из дальнейшего поиска.
Value(MaxJ) = 0
Next I
===============3
В этом алгоритме переменная цикла I последовательно принимает значения от 1
до N. Для каждого приращения I переменная J в свою очередь также принимает
значения от 1 до N. Таким образом, в каждом внешнем цикле выполняется еще N
внутренних циклов. В итоге внутренний цикл выполняется N*N или N2 раз и,
следовательно, сложность алгоритма порядка O(N2).
При оценке порядка сложности алгоритмов используется только наиболее быстро
растущая часть уравнения алгоритма. Допустим, время выполнения алгоритма
пропорционально N3+N. Тогда сложность алгоритма будет равна O(N3).
Отбрасывание медленно растущих частей уравнения позволяет оценить поведение
алгоритма при увеличении размерности данных задачи N.
При больших N вклад второй части в уравнение N3+N становится все менее
заметным. При N=100, разность N3+N=1.000.100 и N3 равна всего 100, или
менее чем 0,01 процента. Но это верно только для больших N. При N=2,
разность между N3+N =10 и N3=8 равна 2, а это уже 20 процентов.
Постоянные множители в соотношении также игнорируются. Это позволяет легко
оценить изменения в вычислительной сложности задачи. Алгоритм, время
выполнения которого пропорционально 3*N2, будет иметь порядок O(N2). Если
увеличить N в 2 раза, то время выполнения задачи возрастет примерно в 22,
то есть в 4 раза.
Игнорирование постоянных множителей позволяет также упростить подсчет числа
шагов алгоритма. В предыдущем примере внутренний цикл выполняется N2 раз,
при этом внутри цикла выполняется несколько инструкций. Можно просто
подсчитать число инструкций If, можно подсчитать также инструкции,
выполняемые внутри цикла или, кроме того, еще и инструкции во внешнем
цикле, например операторы Print.
Вычислительная сложность алгоритма при этом будет пропорциональна N2, 3*N2
или 3*N2+N. Оценка сложности алгоритма по порядку величины даст одно и то
же значение O(N3) и отпадет необходимость в точном подсчете количества
операторов.
Поиск сложных частей алгоритма
Обычно наиболее сложным является выполнение циклов и вызовов процедур. В
предыдущем примере, весь алгоритм заключен в двух циклах.
============4
Если процедура вызывает другую процедуру, необходимо учитывать сложность
вызываемой процедуры. Если в ней выполняется фиксированное число
инструкций, например, осуществляется вывод на печать, то при оценке порядка
сложности ее можно не учитывать. С другой стороны, если в вызываемой
процедуре выполняется O(N) шагов, она может вносить значительный вклад в
сложность алгоритма. Если вызов процедуры осуществляется внутри цикла, этот
вклад может быть еще больше.
Приведем в качестве примера программу, содержащую медленную процедуру Slow
со сложностью порядка O(N3) и быструю процедуру Fast со сложностью порядка
O(N2). Сложность всей программы будет зависеть от соотношения между этими
двумя процедурами.
Если процедура Slow вызывается в каждом цикле процедуры Fast, порядки
сложности процедур перемножаются. В этом случае сложность алгоритма равна
произведению O(N2) и O(N3) или O(N3*N2)=O(N5). Приведем иллюстрирующий этот
случай фрагмент кода:
Sub Slow()
Dim I As Integer
Dim J As Integer
Dim K As Integer
For I = 1 To N
For J = 1 To N
For K = 1 To N
' Выполнить какие-либо действия.
Next K
Next J
Next I
End Sub
Sub Fast()
Dim I As Integer
Dim J As Integer
Dim K As Integer
For I = 1 To N
For J = 1 To N
Slow ' Вызов процедуры Slow.
Next J
Next I
End Sub
Sub MainProgram()
Fast
End Sub
С другой стороны, если процедуры независимо вызываются из основной
программы, их вычислительная сложность суммируется. В этом случае полная
сложность будет равна O(N3)+O(N2)=O(N3). Такую сложность, например, будет
иметь следующий фрагмент кода:
Sub Slow()
Dim I As Integer
Dim J As Integer
Dim K As Integer
For I = 1 To N
For J = 1 To N
For K = 1 To N
' Выполнить какие-либо действия.
Next K
Next J
Next I
End Sub
Sub Fast()
Dim I As Integer
Dim J As Integer
For I = 1 To N
For J = 1 To N
' Выполнить какие-либо действия.
Next J
Next I
End Sub
Sub MainProgram()
Slow
Fast
End Sub
==============5
Сложность рекурсивных алгоритмов
Рекурсивными процедурами (recursive procedure) называются процедуры,
вызывающие сами себя. Во многих рекурсивных алгоритмах именно степень
вложенности рекурсии определяет сложность алгоритма, при этом не всегда
легко оценить порядок сложности. Рекурсивная процедура может выглядеть
простой, но при этом вносить большой вклад в сложность программы,
многократно вызывая саму себя.
Следующий фрагмент кода содержит подпрограмму всего из двух операторов. Тем
не менее, для заданного N подпрограмма выполняется N раз, таким образом,
вычислительная сложность фрагмента порядка O(N).
Sub CountDown(N As Integer)
If N 20 Then
ArraySize = ArraySize –10
ReDim Preserve List(1 To ArraySize)
End If
End Sub
=============20
Для очень больших массивов это решение может также оказаться не самым
лучшим. Если вам нужен список, содержащий 1000 элементов, к которому обычно
добавляется по 100 элементов, то все еще слишком много времени будет
тратиться на изменение размера массива. Очевидной стратегией в этом случае
было бы увеличение приращения размера массива с 10 до 100 или более ячеек.
Тогда можно было бы добавлять по 100 элементов одновременно без частого
изменения размера списка.
Более гибким решением будет изменение приращения в зависимости от размера
массива. Для небольших списков это приращение было бы также небольшим. Хотя
изменения размера массива происходили бы чаще, они потребовали бы
относительно немного времени для небольших массивов. Для больших списков,
приращение размера будет больше, поэтому их размер будет изменяться реже.
Следующая программа пытается поддерживать примерно 10 процентов списка
свободным. Когда массив заполняется, его размер увеличивается на 10
процентов. Если свободное пространство составляет более 20 процентов от
размера массива, программа уменьшает его.
При увеличении размера массива, добавляется не меньше 10 элементов, даже
если 10 процентов от размера массива составляют меньшую величину. Это
уменьшает число необходимых изменений размера массива, если список очень
мал.
Const WANT_FREE_PERCENT = .1 ‘ 10% свободного места.
Const MIN_FREE = 10 ‘ Минимальное число пустых ячеек.
Global List() As String ‘ Массив элементов списка.
Global ArraySize As Integer ‘ Размер массива.
Global NumItems As Integer ‘ Число элементов в списке.
Global ShrinkWhen As Integer ‘ Уменьшить размер, если NumItems ArraySize Then ResizeList
List(NumItems) = value
End Sub
‘ Удалить последний элемент из списка.
‘ Если в массиве много пустых ячеек, уменьшить его размер.
Sub RemoveLast()
NumItems = NumItems – 1
If NumItems < ShrinkWhen Then ResizeList
End Sub
‘ Увеличить размер массива, чтобы 10% ячеек были свободны.
Sub ResizeList()
Dim want_free As Integer
want_free = WANT_FREE_PERCENT * NumItems
If want_free < MIN_FREE Then want_free = MIN_FREE
ArraySize = NumItems + want_free
ReDim Preserve List(1 To ArraySize)
‘ Уменьшить размер массива, если NumItems < ShrinkWhen.
ShrinkWhen = NumItems – want_free
End Sub
===============21
Класс SimpleList
Чтобы использовать этот простой подход, программе необходимо знать все
параметры списка, при этом нужно следить за размером массива, числом
используемых элементов, и т.д. Если необходимо создать больше одного
списка, потребуется множество копий переменных и код, управляющий разными
списками, будет дублироваться.
Классы Visual Basic могут сильно облегчить выполнение этой задачи. Класс
SimpleList инкапсулирует эту структуру списка, упрощая управление списками.
В этом классе присутствуют методы Add и Remove для использования в основной
программе. В нем также есть процедуры извлечения свойств NumItems и
ArraySize, с помощью которых программа может определить число элементов в
списке и объем занимаемой им памяти.
Процедура ResizeList объявлена как частная внутри класса SimpleList. Это
скрывает изменение размера списка от основной программы, поскольку этот код
должен использоваться только внутри класса.
Используя класс SimpleList, легко создать в приложении несколько списков.
Для того чтобы создать новый объект для каждого списка, просто используется
оператор New. Каждый из объектов имеет свои переменные, поэтому каждый из
них может управлять отдельным списком:
Dim List1 As New SimpleList
Dim List2 As New SimpleList
Когда объект SimpleList увеличивает массив, он выводит окно сообщения,
показывающее размер массива, количество неиспользуемых элементов в нем, и
значение переменной ShrinkWhen. Когда число использованных ячеек в массиве
становится меньше, чем значение ShrinkWhen, программа уменьшает размер
массива. Заметим, что когда массив практически пуст, переменная ShrinkWhen
иногда становится равной нулю или отрицательной. В этом случае размер
массива не будет уменьшаться, даже если вы удалите все элементы из списка.
=============22
Программа SimList добавляет к массиву еще 50 процентов пустых ячеек, если
необходимо увеличить его размер, и всегда оставляет при этом не менее 1
пустой ячейки. Эти значения был выбраны для удобства работы с программой. В
реальном приложении, процент свободной памяти должен быть меньше, а число
свободных ячеек больше. Более разумным в таком случае было бы выбрать
значения порядка 10 процентов от текущего размера списка и минимум 10
свободных ячеек.
Неупорядоченные списки
В некоторых приложениях может понадобиться удалять элементы из середины
списка, добавляя при этом элементы в конец списка. В этом случае порядок
расположения элементов может быть не важен, но при этом может быть
необходимо удалять определенные элементы из списка. Списки такого типа
называются неупорядоченными списками (unordered lists). Они также иногда
называются «множеством элементов».
Неупорядоченный список должен поддерживать следующие операции:
1. добавление элемента к списку;
2. удаление элемента из списка;
3. определение наличия элемента в списке;
4. выполнение каких-либо операций (например, вывода на дисплей или принтер)
для всех элементов списка.
Простую структуру, представленную в предыдущем параграфе, можно легко
изменить для того, чтобы обрабатывать такие списки. Когда удаляется элемент
из середины списка, остальные элементы сдвигаются на одну позицию, заполняя
образовавшийся промежуток. Это показано на рис. 2.1, на котором второй
элемент удаляется из списка, и третий, четвертый, и пятый элементы
сдвигаются влево, заполняя свободный участок.
Удаление из массива элемента при таком подходе может занять достаточно
много времени, особенно если удаляется элемент в начале списка. Чтобы
удалить первый элемент из массива с 1000 элементов, потребуется сдвинуть
влево на одну позицию 999 элементов. Гораздо быстрее удалять элементы можно
при помощи простой схемы чистки памяти (garbage collection).
Вместо удаления элементов из списка, пометьте их как неиспользуемые. Если
элементы списка — данные простых типов, например целые, можно помечать
элементы, используя определенное, так называемое «мусорное» значение
(garbage value).
@Рисунок 2.1 Удаление элемента из середины массива
===========23
Для целых чисел можно использовать для этого значение -32.767. Для
переменной типа Variant можно использовать значение NULL. Это значение
присваивается каждому неиспользуемому элементу. Следующий фрагмент кода
демонстрирует удаление элемента из подобного целочисленного списка:
Const GARBAGE_VALUE = -32767
‘ Пометить элемент как неиспользуемый.
Sub RemoveFromList(position As Long)
List(position) = GARBAGE_VALUE
End Sub
Если элементы списка — это структуры, определенные оператором Type, вы
можете добавить к такой структуре новое поле IsGarbage. Когда элемент
удаляется из списка, значение поля IsGarbage устанавливается в True.
Type MyData
Name As Sring ‘ Данные.
IsGarbage As Integer ‘ Этот элемент не используется?
End Type
‘ Пометить элемент, как не использующийся.
Sub RemoveFromList (position As Long)
List(position).IsGarbage = True
End Sub
Для простоты далее в этом разделе предполагается, что элементы данных
являются данными универсального типа и их можно помечать значением NULL.
Теперь можно изменить другие процедуры, которые используют список, чтобы
они пропускали помеченные элементы. Например, так можно модифицировать
процедуру, которая печатает список:
‘ Печать элементов списка.
Sub PrintItems()
Dim I As Long
For I = 1 To ArraySize
If Not IsNull(List(I)) Then ‘ Если элемент не помечен
Print Str$(List(I)) ‘ напечатать его.
End If
Next I
End Sub
После использования в течение некоторого времени схемы пометки «мусора»,
список может оказаться полностью им заполнен. В конце концов, подпрограммы
вроде этой процедуры больше времени будут тратить на пропуск ненужных
элементов, чем на обработку настоящих данных.
=============24
Для того, чтобы избежать этого, можно периодически запускать процедуру
очистки памяти (garbage collection routine). Эта процедура перемещает все
непомеченные записи в начало массива. После этого можно добавить их к
свободным элементам в конце массива. Когда потребуется добавить к массиву
дополнительные элементы, их также можно будет использовать без изменения
размера массива.
После добавления помеченных элементов к другим свободным ячейкам массива,
полный объем свободного пространства может стать достаточно большим, и в
этом случае можно уменьшить размер массива, освобождая память:
Private Sub CollectGarbage()
Dim i As Long
Dim good As Long
good = 1 ‘ Первый используемый элемент.
For i = 1 To m_NumItems
‘ Если он не помечен, переместить его на новое место.
If Not IsNull(m_List(i)) Then
m_List(good) = m_list(i)
good = good + 1
End If
Next i
‘ Последний используемый элемент.
m_NumItems(good) = good - 1
‘ Необходимо ли уменьшать размер списка?
If m_NumItems < m_ShrinkWhen Then ResizeList
End Sub
При выполнении чистки памяти, используемые элементы перемещаются ближе к
началу списка, заполняя пространство, которое занимали помеченные элементы.
Значит, положение элементов в списке может измениться во время этой
операции. Если другие часть программы обращаются к элементам списка по их
положению в нем, необходимо модифицировать процедуру чистки памяти, с тем,
чтобы она также обновляла ссылки на положение элементов в списке. В общем
случае это может оказаться достаточно сложным, приводя к проблемам при
сопровождении программ.
Можно выбирать разные моменты для запуска процедуры чистки памяти. Один из
них — когда массив достигает определенного размера, например, когда список
содержит 30000 элементов.
Этому методу присущи определенные недостатки. Во-первых, он использует
большой объем памяти. Если вы часто добавляете или удаляете элементы,
«мусор» будет занимать довольно большую часть массива. При таком
неэкономном расходовании памяти, программа может тратить время на свопинг,
хотя список мог бы целиком помещаться в памяти при более частом
переупорядочивании.
===========25
Во-вторых, если список начинает заполняться ненужными данными, процедуры,
которые его используют, могут стать чрезвычайно неэффективными. Если в
массиве из 30.000 элементов 25.000 не используются, подпрограмма типа
описанной выше PrintItems, может выполняться ужасно медленно.
И, наконец, чистка памяти для очень большого массива может потребовать
значительного времени, в особенности, если при обходе элементов массива
программе приходится обращаться к страницам, выгруженным на диск. Это может
приводить к «подвисанию» вашей программы на несколько секунд во время
чистки памяти.
Чтобы решить эту проблему, можно создать новую переменную GarbageCount, в
которой будет находиться число ненужных элементов в списке. Когда
значительная часть памяти, занимаемой списком, содержит ненужные элементы,
вы может начать процедуру «сборки мусора».
Dim GarbageCount As Long ‘ Число ненужных элементов.
Dim MaxGarbage As Long ‘ Это значение определяется в ResizeList.
‘ Пометить элемент как ненужный.
‘ Если «мусора» слишком много, начать чистку памяти.
Public Sub Remove(position As Long)
m_List(position) = Null
m_GarbageCount = m_GarbageCount + 1
‘ Если «мусора» слишком много, начать чистку памяти.
If m_GarbageCount > m_MaxGarbage Then CollectGarbage
End Sub
Программа Garbage демонстрирует этот метод чистки памяти. Она пишет рядом с
неиспользуемыми элементами списка слово «unused», а рядом с помеченными как
ненужные — слово «garbage». Программа использует класс GarbageList примерно
так же, как программа SimList использовала класс SimpleList, но при этом
она еще осуществляет «сборку мусора».
Чтобы добавить элемент к списку, введите его значение и нажмите на кнопку
Add (Добавить). Для удаления элемента выделите его, а затем нажмите на
кнопку Remove (Удалить). Если список содержит слишком много «мусора»,
программа начнет выполнять чистку памяти.
При каждом изменении размера списка объекта GarbageList, программа выводит
окно сообщения, в котором приводится число используемых и свободных
элементов в списке, а также значения переменных MaxGarbage и ShrinkWhen.
Если удалить достаточное количество элементов, так что больше, чем
MaxGarbage элементов будут помечены как ненужные, программа начнет
выполнять чистку памяти. После ее окончания, программа уменьшает размер
массива, если он содержит меньше, чем ShrinkWhen занятых элементов.
Если размер массива должен быть увеличен, программа Garbage добавляет к
массиву еще 50 процентов пустых ячеек, и всегда оставляет хотя бы одну
пустую ячейку при любом изменении размера массива. Эти значения были
выбраны для упрощения работы пользователя со списком. В реальной программе
процент свободной памяти должен быть меньше, а число свободных ячеек —
больше. Оптимальными выглядят значения порядка 10 процентов и 10 свободных
ячеек.
==========26
Связные списки
Другая стратегия используется при управлении связанными списками. Связанный
список хранит элементы в структурах данных или объектах, которые называются
ячейками (cells). Каждая ячейка содержит указатель на следующую ячейку в
списке. Так как единственный тип указателей, которые поддерживает Visual
Basic — это ссылки на объекты, то ячейки в связном списке должны быть
объектами.
В классе, задающем ячейку, должна быть определена переменная NextCell,
которая указывает на следующую ячейку в списке. В нем также должны быть
определены переменные, содержащие данные, с которыми будет работать
программа. Эти переменные могут быть объявлены как открытые (public) внутри
класса, или класс может содержать процедуры для чтения и записи значений
этих переменных. Например, в связном списке с записями о сотрудниках, в
этих полях могут находиться имя сотрудника, номер социального страхования,
название должности, и т.д. Определения для класса EmpCell могут выглядеть
примерно так:
Public EmpName As String
Public SSN As String
Public JobTitle As String
Public NextCell As EmpCell
Программа создает новые ячейки при помощи оператора New, задает их значения
и соединяет их, используя переменную NextCell.
Программа всегда должна сохранять ссылку на вершину списка. Для того, чтобы
определить, где заканчивается список, программа должна установить значение
NextCell для последнего элемента списка равным Nothing (ничего). Например,
следующий фрагмент кода создает список, представляющий трех сотрудников:
Dim top_cell As EmpCell
Dim cell1 As EmpCell
Dim cell2 As EmpCell
Dim cell3 As EmpCell
‘ Создание ячеек.
Set cell1 = New EmpCell
cell1.EmpName = "Стивенс”
cell1.SSN = "123-45-6789"
cell1.JobTitle = "Автор"
Set cell2 = New EmpCell
cell2.EmpName = "Кэтс”
cell2.SSN = "123-45-6789"
cell2.JobTitle = "Юрист"
Set cell3 = New EmpCell
cell3.EmpName = "Туле”
cell3.SSN = "123-45-6789"
cell3.JobTitle = "Менеджер"
‘ Соединить ячейки, образуя связный список.
Set cell1.NextCell = cell2
Set cell2.NextCell = cell3
Set cell3.NextCell = Nothing
‘ Сохранить ссылку на вершину списка.
Set top_cell = cell1
===============27
На рис. 2.2 показано схематическое представление этого связного списка.
Прямоугольники представляют ячейки, а стрелки — ссылки на объекты.
Маленький перечеркнутый прямоугольник представляет значение Nothing,
которое обозначает конец списка. Имейте в виду, что top_cell, cell1 и
cell2 – это не настоящие объекты, а только ссылки, которые указывают на
них.
Следующий код использует связный список, построенный при помощи предыдущего
примера для печати имен сотрудников из списка. Переменная ptr используется
в качестве указателя на элементы списка. Она первоначально указывает на
вершину списка. В коде используется цикл Do для перемещения ptr по списку
до тех пор, пока указатель не дойдет до конца списка. Во время каждого
цикла, процедура печатает поле EmpName ячейки, на которую указывает ptr.
Затем она увеличивает ptr, указывая на следующую ячейку в списке. В конце
концов, ptr достигает конца списка и получает значение Nothing, и цикл Do
останавливается.
Dim ptr As EmpCell
Set ptr = top_cell ‘ Начать с вершины списка.
Do While Not (ptr Is Nothing)
‘ Вывести поле EmpName этой ячейки.
Debug.Print ptr.Empname
‘ Перейти к следующей ячейке в списке.
Set ptr = ptr.NextCell
Loop
После выполнения кода вы получите следующий результат:
Стивенс
Кэтс
Туле
@Рис. 2.2. Связный список
=======28
Использование указателя на другой объект называется косвенной адресацией
(indirection), поскольку вы используете указатель для косвенного
манипулирования данными. Косвенная адресация может быть очень запутанной.
Даже для простого расположения элементов, такого, как связный список,
иногда трудно запомнить, на какой объект указывает каждая ссылка. В более
сложных структурах данных, указатель может ссылаться на объект, содержащий
другой указатель. Если есть несколько указателей и несколько уровней
косвенной адресации, вы легко можете запутаться в них
Для того, чтобы облегчить понимание, в изложении используются иллюстрации,
такие как рис. 2.2,(для сетевой версии исключены, т.к. они многократно
увеличивают размер загружаемого файла) чтобы помочь вам наглядно
представить ситуацию там, где это возможно. Многие из алгоритмов, которые
используют указатели, можно легко проиллюстрировать подобными рисунками.
Добавление элементов к связному списку
Простой связный список, показанный на рис. 2.2, обладает несколькими
важными свойствами. Во-первых, можно очень легко добавить новую ячейку в
начало списка. Установим указатель новой ячейки NextCell на текущую вершину
списка. Затем установим указатель top_cell на новую ячейку. Рис. 2.3
соответствует этой операции. Код на языке Visual Basic для этой операции
очень прост:
Set new_cell.NextCell = top_cell
Set top_cell = new_cell
@Рис. 2.3. Добавление элемента в начало связного списка
Сравните размер этого кода и кода, который пришлось бы написать для
добавления нового элемента в начало списка, основанного на массиве, в
котором потребовалось бы переместить все элементы массива на одну позицию,
чтобы освободить место для нового элемента. Эта операция со сложностью
порядка O(N) может потребовать много времени, если список достаточно
длинный. Используя связный список, моно добавить новый элемент в начало
списка всего за пару шагов.
======29
Так же легко добавить новый элемент и в середину связного списка.
Предположим, вы хотите вставить новый элемент после ячейки, на которую
указывает переменная after_me. Установим значение NextCell новой ячейки
равным after_me.NextCell. Теперь установим указатель after_me.NextCell на
новую ячейку. Эта операция показана на рис. 2.4. Код на Visual Basic снова
очень прост:
Set new_cell.NextCell = after_me.NextCell
Set after_me.NextCell = new_cell
Удаление элементов из связного списка
Удалить элемент из вершины связного списка так же просто, как и добавить
его. Просто установите указатель top_cell на следующую ячейку в списке.
Рис. 2.5 соответствует этой операции. Исходный код для этой операции еще
проще, чем код для добавления элемента.
Set top_cell = top_cell.NextCell
Когда указатель top_cell перемещается на второй элемент в списке, в
программе больше не останется переменных, указывающих на первый объект. В
этом случае, счетчик ссылок на этот объект станет равен нулю, и система
автоматически уничтожит его.
Так же просто удалить элемент из середины списка. Предположим, вы хотите
удалить элемент, стоящий после ячейки after_me. Просто установите указатель
NextCell этой ячейки на следующую ячейку. Эта операция показана на рис.
2.6. Код на Visual Basic прост и понятен:
after_me.NextCell = after_me.NextCell.NextCell
@Рис. 2.4. Добавление элемента в середину связного списка
=======30
@Рис. 2.5. Удаление элемента из начала связного списка
Снова сравним этот код с кодом, который понадобился бы для выполнения той
же операции, при использовании списка на основе массива. Можно быстро
пометить удаленный элемент как неиспользуемый, но это оставляет в списке
ненужные значения. Процедуры, обрабатывающие список, должны это учитывать,
и соответственно быть более сложными. Присутствие чрезмерного количества
«мусора» также замедляет работу процедуры, и, в конце концов, придется
проводить чистку памяти.
При удалении элемента из связного списка, в нем не остается пустых
промежутков. Процедуры, которые обрабатывают список, все так же обходят
список с начала до конца, и не нуждаются в модификации.
Уничтожение связного списка
Можно предположить, что для уничтожения связного списка необходимо обойти
весь список, устанавливая значение NextCell для всех ячеек равным Nothing.
На самом деле процесс гораздо проще: только top_cell принимает значение
Nothing.
Когда программа устанавливает значение top_cell равным Nothing, счетчик
ссылок для первой ячейки становится равным нулю, и Visual Basic уничтожает
эту ячейку.
Во время уничтожения ячейки, система определяет, что в поле NextCell этой
ячейки содержится ссылка на другую ячейку. Поскольку первый объект
уничтожается, то число ссылок на второй объект уменьшается. При этом
счетчик ссылок на второй объект списка становится равным нулю, поэтому
система уничтожает и его.
Во время уничтожения второго объекта, система уменьшает число ссылок на
третий объект, и так далее до тех пор, пока все объекты в списке не будут
уничтожены. Когда в программе уже не будет ссылок на объекты списка, можно
уничтожить и весь список при помощи единственного оператора Set
top_cell = Nothing.
@Рис. 2.6. Удаление элемента из середины связного списка
========31
Сигнальные метки
Для добавления или удаления элементов из начала или середины списка
используются различные процедуры. Можно свести оба этих случая к одному и
избавиться от избыточного кода, если ввести специальную сигнальную метку
(sentinel) в самом начале списка. Сигнальную метку нельзя удалить. Она не
содержит данных и используется только для обозначения начала списка.
Теперь вместо того, чтобы обрабатывать особый случай добавления элемента в
начало списка, можно помещать элемент после метки. Таким же образом, вместо
особого случая удаления первого элемента из списка, просто удаляется
элемент, следующий за меткой.
Использование сигнальных меток пока не вносит особых различий. Сигнальные
метки играют важную роль в гораздо более сложных алгоритмах. Они позволяют
обрабатывать особые случаи, такие как начало списка, как обычные. При этом
требуется написать и отладить меньше кода, и алгоритмы становятся более
согласованными и более простыми для понимания.
В табл. 2.1 сравнивается сложность выполнения некоторых типичных операций с
использованием списков на основе массивов со «сборкой мусора» или связных
списков.
Списки на основе массивов имеют одно преимущество: они используют меньше
памяти. Для связных списков необходимо добавить поле NextCell к каждому
элементу данных. Каждая ссылка на объект занимает четыре дополнительных
байта памяти. Для очень больших массивов это может потребовать больших
затрат памяти.
Программа LnkList1 демонстрирует простой связный список с сигнальной
меткой. Введите значение в текстовое поле ввода, и нажмите на элемент в
списке или на метку. Затем нажмите на кнопку Add After (Добавить после), и
программа добавит новый элемент после указанного. Для удаления элемента из
списка, нажмите на элемент и затем на кнопку Remove After (Удалить после).
@Таблица 2.1. Сравнение списков на основе массивов и связных списков
=========32
Инкапсуляция связных списков
Программа LnkList1 управляет списком явно. Например, следующий код
показывает, как программа удаляет элемент из списка. Когда подпрограмма
начинает работу, глобальная переменная SelectedIndex дает положение
элемента, предшествующего удаляемому элементу в списке. Переменная Sentinel
содержит ссылку на сигнальную метку списка.
Private Sub CmdRemoveAfter_Click()
Dim ptr As ListCell
Dim position As Integer
If SelectedIndex < 0 Then Exit Sub
‘ Найти элемент.
Set ptr = Sentinel
position = SelectedIndex
Do While position > 0
position = position - 1
Set ptr = ptr.nextCell
Loop
‘ Удалить следуюший элемент.
Set ptr.NextCell = ptr.NextCell.NextCell
NumItems = NumItems - 1
SelectItem Select | |
