1.3. Схема алгоритма слияния набросана в задаче 14.4.4.
Решение 11.6 содержит псевдокод сортировки выбором и сортировки Шелла (selection sort, Shell sort).
• Время выполнения нескольких алгоритмов сортировки оиисано в решении 1.3.
• Специальные функции. Эти функции позволяют писать короткие и эффективные программы для некоторых типов входных данных.
• Поразрядная сортировка. Сортировка битовых строк из задачи 11.5, придуманная Макилроем, может быть обобщена для сортировки строк на других алфавитах (байтах, например).
• Сортировка с битовым массивом. Сортировка из раздела 1.4 использует тот факт, что числа берутся из небольшого диапазона, без повторений и дополнительных данных. Детали реализации и возможные расширения описаны в задачах 1.2, 1.3, 1.5 и 1.6.
• Прочие сортировки. Многопроходная сортировка в разделе 1.3 считывает входной файл много раз, экономя память за счет быстроты выполнения. В главах 12 и 13 порождаются упорядоченные наборы случайных чисел.
Поиск
• Постановка задачи. Функция поиска определяет, является ли заданный ей на входе элемент членом данного множества, и иногда выдает связанную с ним информацию.
• Приложения. Программа-справочник телефонных номеров Леска в задаче 2.6 ищет имя в базе данных, возвращая соответствующий ему телефонный номер. Шахматная программа Томпсона из раздела 10.8 искала текущее расположение фигур в базе данных, вычисляя оптимальный ход. Программа проверки правописания Макилроя из раздела 13.8 осуществляет поиск в словаре. Другие приложения поиска описаны в соответствующих функциях.
• Функции общего назначения. Приведенные ниже алгоритмы предназначены для поиска в произвольном ^-элементном множестве.
• Последовательный поиск. Простые и оптимизированные версии последовательного поиска для массивов приводятся в разделе 9.2. Последовательный поиск для массивов и связанных списков описан в разделе 13.2. Этот алгоритм используется для расстановки переносов (задача 3.5), сглаживания географических данных (раздел 9.2), представления разреженных матриц (раздел 10.2), порождения случайных наборов (раздел 13.2), сортировки сжатого словаря (раздел 13.8), упаковки корзин (задача 14.5) и поиска одинаковых фраз в тексте (раздел 15.3). Введение к главе 3 и задача 3.1 описывают два глупых варианта реализации последовательного поиска.
Опубликовал vovan666
April 17 2013 00:05:15 ·
0 Комментариев ·
3445 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
