Алгоритм поиска в отсортированном массиве за log2п сравнений описан в разделе 2.2, а код его разработан в разделе 4.2. В разделе 9.3 код был расширен для поиска первого вхождения элемента, а также оптимизирован. Приложения включают поиск записей в системе резервирования (раздел 2.2), строк с ошибками (раздел 2.2), анаграмм входного слова (задача 2.1), телефонных номеров (задача 2.6), положения точки между отрезками (задача 4.7), индекса записи в разреженном массиве (решение 10.2), случайных чисел (задача 13.3) и фраз (разделы 15.2 и 15.3). В задачах 2.9 и 9.9 обсуждаются компромиссы между двоичным и последовательным поиском.
• Хэширование. В задаче 1.10 используется хэширование телефонных номеров. В задаче 9.10 хэшируется набор целых чисел; в разделе 13.4 набор корзин используется для хэширования набора целых чисел, и наконец в разделе 13.8 хэшируются слова в словаре. В разделе 15.1 хэширование используется для подсчета слов в документе.
• Двоичные деревья поиска. В разделе 13.3 используется (несбалансированное) двоичное дерево поиска для представления списка случайных целых. Сбалансированные деревья обычно используются при реализации шаблона set из стандартной библиотеки шаблонов C++ STL, которым мы пользовались в разделах 13.1 и 15.1 и решении 1.1.
Опубликовал vovan666
April 17 2013 00:05:17 ·
0 Комментариев ·
3623 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
