Структуры и методы обработки данных, практикум в среде Delphi, Зубов В.С., Шевченко И.В., 2004

Структуры и методы обработки данных, Практикум в среде Delphi, Зубов В.С., Шевченко И.В., 2004.

   В книге рассматриваются широко используемые структуры данных и фундаментальные алгоритмы сортировки данных, информационного поиска, упорядочивания динамических данных, решения графовых задач и генерации комбинаторных объектов. Алгоритмы прошли тщательный отбор и апробацию.
Для учащихся вузов и в помощь пользователям компьютеров при построении структур данных и выборе алгоритмов.




Динамические строки — реальные структуры данных.
В отличие от абстрактных реальные структуры «живут»: данные добавляются, изменяются, исключаются. Это влечет динамику размеров.

Типична ситуация, когда одна проблема требует решения другой, которая никак не решается без решения третьей и т.д. В этом ряду проблема, не вызвавшая новых проблем (по-видимому, относительно простая), решается нами первой, хотя оформилась последней, а исходная проблема решается в последнюю очередь. Такая дисциплина обслуживания обозначается LIFO («последним пришел, первым ушел») и часто используется в программах. Ей соответствует реальная линейная структура, называемая стек.

Помещение в стек нового элемента, его чтение (для обработки), удаление происходят в одном конце, называемом верхушкой. Другой конец (дно) неактивен. Если мы удалим элемент, в верхушке оказывается следующий (сравните с действием патронного магазина в стрелковом оружии).

ОГЛАВЛЕНИЕ.
От авторов.
Предисловие.
1. СТРУКТУРЫ ДАННЫХ.
1.1. Абстрактные структуры. Реальное и идеальное.
1.2. Реализация протомассивов. Массивы.
1.3. Реализация битового протомассива. Массив множеств.
1.4. Связывание данных. Преимущества структур с индексированием.
1.5. Динамические строки — реальные структуры данных.
1.6. Кольцевые структуры данных.
1.7. Упорядоченное бинарное дерево. Обход дерева.
1.8. Неупорядоченное бинарное дерево.
1.9. Недвоичные деревья. Проекции регулярных деревьев.
1.10. Многомерные связанные структуры.
1.11. Однородные сетевые структуры.
1.12. Примеры реальных структур данных. Отношения.
1.13. Систематизация структур данных.
2. КРИТЕРИИ ОЦЕНКИ АЛГОРИТМОВ. ОБЩИЕ МЕТОДЫ.
2.1. Асимптотические характеристики.
2.2. Роль метода в снижении трудоемкости решения задачи.
2.3. Рекурсия в алгоритмах.
2.4. Динамическое программирование. Задача о критическом пути.
2.5. Пространственная и временная локальность.
2.6. Характеристики вычислительной сложности алгоритмов.
2.7. Частные характеристики качества алгоритмов.
2.8. Увеличение быстродействия программ.
3. УПОРЯДОЧЕНИЕ И СОРТИРОВКА ДАННЫХ В ПАМЯТИ.
3.1. Методы упорядочения. Сортировка.
3.2. Простые отобразительные алгоритмы сортировки.
3.3. Сортировки с отдельным полем отображения. Алгоритм Фалька.
3.4. Универсальные реализации отобразительной сортировки.
3.5. Алгоритм Шелла и алгоритм СортДеревом.
3.6. Быстрая сортировка (алгоритм QuickSort).
3.7. Сортировка прямым слиянием. Алгоритм Боуза—Нельсона.
3.8. Списковые алгоритмы. Естественное слияние.
3.9. Сравнение алгоритмов сортировки массивов.
3.10. Память, кэш и трудоемкость сортировки.
3.11. Пример конструирования. Компактная сортировка слиянием.
3.12. Систематизация алгоритмов сортировки.
4. ПРИМЕНЕНИЯ СОРТИРОВКИ. ВНЕШНЯЯ СОРТИРОВКА.
4.1. Нахождение пересечений и объединений наборов данных.
4.2. Сортировка строк. Комбинированные алгоритмы.
4.3. Нахождение множества экстремальных элементов. Порядковые статистики.
4.4. Лексикографическая сортировка.
4.5. Обработка результатов лексикографической сортировки.
4.6. Сопоставительная специальная сортировка.
4.7. Пример отобразительной специальной сортировки.
4.8. Внешняя сортировка на дисках. Пример алгоритма.
4.9. Компактная внешняя сортировка разделением.
4.10. Сортировка данных без упорядочения?.
5. ПОИСК ДАННЫХ В МАССИВАХ И БИНАРНЫХ ДЕРЕВЬЯХ.
5.1. Разновидности информационного поиска.
5.2. Поиск перебором и многовариантный бинарный поиск в массиве.
5.3. Универсальная схема бинарного поиска в массиве.
5.4. Построение и поддержание бинарного дерева.
5.5. Многовариантный бинарный поиск в дереве.
5.6. Построение сбалансированного дерева — ABЛ-дерева.
5.7. Исключение узлов в АВЛ-дереве.
5.8. АВЛ-дерево в роли динамического вектора.
5.9. Цифровой поиск. Система луч.
5.10. Сравнение алгоритмов бинарного и цифрового поиска.
6. ПОИСК В НЕДВОИЧНЫХ ДЕРЕВЬЯХ - В-ДЕРЕВЬЯХ.
6.1. В-деревья. Принципы организации.
6.2. Поиск в В+-дереве по совпадению и по близости.
6.3. Обход В+-дерева слева. Поиск по интервалу.
6.4. Перестройки В+-дерева при его росте.
6.5. Поиск со вставкой в В+-дерево.
6.6. Инициализация, поддержание и сохранение В+-дерева.
6.7. Удаление информационных записей и ключей из В+-дерева.
6.8. Сравнение АВЛ- и В+-дерева, построенных в памяти.
6.9. Построение В+-дерева на диске.
6.10. Анализ реализации В+-дерева на диске.
7. ОТОБРАЗИТЕЛЬНЫЙ МЕТОД ПОИСКА. ХЕШИРОВАНИЕ.
7.1. Сочетание доступа к данным и поиска данных.
7.2. Хеш-функции. Недостатки хеширования.
7.3. Обработка коллизий. Внешние структуры.
7.4. Обработка коллизий в хеш-таблице с внутренними цепями.
7.5. Обработка коллизий в хеш-таблице с открытой адресацией.
7.6. Хеширование в случае строк-ключей.
7.7. Характеристика методов хеширования в памяти.
7.8. Хеширование на диске.
7.9. Композиции с улучшенной локальностью хеширования.
7.10. Сравнение хеширования и поиска в динамических деревьях.
8. СИСТЕМЫ ПРЕДСТАВЛЕНИЯ И ИССЛЕДОВАНИЯ ГРАФОВ.
8.1. Исходные понятия и термины.
8.2. Матричные представления графов.
8.3. Представления графов для пользователя приложений.
8.4. Нематричные представления графов.
8.5. Поиск в глубину как система исследования графа.
8.6. Структуры, используемые при поиске в глубину.
8.7. Нахождение фундаментального множества циклов.
8.8. Выявление в графе мостов и точек сочленений.
8.9. Перебор цепей (путей) поиском в глубину.
8.10. Ординарный поиск в ширину как система исследования графа.
8.11. Нахождение медианы и кратчайших цепей (путей) поиском в ширину.
8.12. Топологическое упорядочение узлов орграфа.
8.13. Система Дейкстры. Кратчайшие пути во взвешенном графе.
8.14. Нахождение эйлеровой цепи.
9. ПРИКЛАДНЫЕ ГРАФОВЫЕ ЗАДАЧИ.
9.1. Нахождение кратчайшего каркаса графа.
9.2. Использование кратчайшего каркаса в задаче коммивояжера.
9.3. Нахождение всевозможных кратчайших цепей в графе.
9.4. Кратчайшие пути в орграфе без циклов.
9.5. Максимальный поток и минимальный разрез сети.
9.6. Поиск в ширину и глубину в задаче о максимальном потоке.
9.7. Нахождение максимального потока по методу Диница.
9.8. Наибольшее паросочетание в двудольном графе.
9.9. Выделение в графе блоков.
9.10. Решение задач о клике методом ветвей и границ.
9.11. Экспериментальная оценка метода Брона—Кербоша. Клиранги.
9.12. Пример практической задачи с нахождением циклов в графе.
10. ГЕНЕРАЦИЯ И ПРИМЕНЕНИЕ КОМБИНАТОРНЫХ ОБЪЕКТОВ.
10.1. Перестановки. Генераторы перестановок.
10.2. Сочетания. Генераторы сочетаний.
10.3. Быстродействующий генератор перестановок.
10.4. Генерация произвольных подмножеств. Мультимножества.
10.5. Генерация всех разбиений множества.
10.6. Генерация псевдослучайных чисел.
10.7. Генерация не ориентированных графов.
10.8. Генерация ориентированных графов.
10.9. Генерация сетей.
Ответы к заданиям.
Приложения.
Литература.
Предметный указатель.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Структуры и методы обработки данных, практикум в среде Delphi, Зубов В.С., Шевченко И.В., 2004 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.




Теги: учебник по информатике :: информатика :: компьютеры :: Зубов :: Шевченко