- •Структуры данных и алгоритмы их обработки (Учебное пособие)
- •Москва 2007
- •1. Структуры данных и алгоритмы 6
- •1.2. Информация и ее представление
- •1.2.1. Природа информации
- •1.2.2. Хранение информации
- •1.2.3. Классификация структур данных
- •1.3. Операции над структурами данных
- •1.4. Порядок алгоритма
- •1.5. Структурность данных и технологии программирования
- •Контрольные вопросы
- •2. Простые структуры данных
- •2.1. Порядковые типы
- •2.2. Целочисленный тип
- •2.3. Символьный тип
- •2.4. Перечисляемый тип
- •2.5. Интервальный тип
- •2.6. Логический тип
- •2.7. Битовый тип
- •2.8. Вещественный тип
- •2.9. Указательный тип
- •Контрольные вопросы
- •3. Объектные типы данных
- •3.1. Объявление и реализация классов
- •Interface
- •Implementation
- •3.2. Директивы видимости
- •3.3. Свойства классов
- •3.4. Структурированная обработка ошибок
- •3.5. Применение объектов
- •Контрольные вопросы
- •4. Статические структуры данных
- •4.1. Векторы
- •4.2. Массивы
- •4.3. Множества
- •4.4. Записи
- •4.5. Таблицы
- •4.6. Операции над статическими структурами
- •4.6.1. Алгоритмы поиска
- •4.6.2. Алгоритмы сортировки
- •Самые медленные алгоритмы сортировки
- •Быстрые алгоритмы сортировки
- •Самые быстрые алгоритмы сортировки
- •Сортировка слиянием
- •Контрольные вопросы
- •5. Полустатические структуры данных
- •5.1. Стеки
- •5.1.1. Стеки в вычислительных системах
- •5.2. Очереди fifo
- •5.2.1. Очереди с приоритетами
- •5.2.2. Очереди в вычислительных системах
- •5.3. Деки
- •5.3.1. Деки в вычислительных системах
- •5.4. Строки
- •5.4.1. Операции над строками
- •5.4.2. Представление строк в памяти
- •3 A b d 8 p q r s t u V w
- •V w ptr nil
- •1 8 П р е д с т а в
- •2 7 ? Л е н и е ?
- •1 8 С т р о к и з
- •1 8 В е н ь я м и
- •1 8 С у п р а в л
- •1 8 Я е м о й д л
- •1 4 И н о й ? ? ? ? nil
- •6.2. Связные линейные списки
- •6.2.1. Машинное представление связных линейных списков
- •Inf next
- •Inf next
- •Inf nil
- •6.2.2. Реализация операций над связными линейными списками
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •6.2.3. Применение линейных списков
- •6.3. Нелинейные разветвленные списки
- •6.3.1. Основные понятия
- •6.3.2. Представление списковых структур в памяти
- •6.3.3. Операции обработки списков
- •6.4. Язык программирования lisp
- •6.5. Управление динамически выделяемой памятью
- •Контрольные вопросы
- •7. Нелинейные структуры данных
- •7.1. Графы и деревья
- •(B) (a) (b) (a)
- •V0 v1 v2 v5 v6 v3 v4 v7 v8 v9 v10 (v0) (v1) (v7) (v8) (v9) (v10) (v3) (v2) (v4) (v5) (v6)
- •7.3. Бинарные деревья
- •7.3.1. Представление бинарных деревьев
- •7.3.2. Прохождение бинарных деревьев
- •7.4. Алгоритмы на деревьях
- •7.4.1. Сортировка с прохождением бинарного дерева
- •7.4.2. Сортировка методом турнира с выбыванием
- •7.4.3. Применение бинарных деревьев для сжатия информации
- •7.4.4. Представление выражений с помощью деревьев
- •7.5. Представление сильноветвящихся деревьев
- •Контрольные вопросы
- •8. Методы ускорения доступа к данным
- •8.1. Хеширование данных
- •8.1.1. Функции хеширования
- •8.1.2. Оценка качества хеш-функции
- •8.1.3. Методы разрешения коллизий
- •8.1.4. Переполнение таблицы и рехеширование
- •8.2. Организация данных для поиска по вторичным ключам
- •8.2.1. Инвертированные индексы
- •8.2.2. Битовые карты
- •Контрольные вопросы
- •Листинги рабочих примеров
- •1. Создание и управление списковыми объектами
- •Interface
- •Implementation
- •Interface
- •Implementation
- •3. Моделирование работы стека
- •Interface
- •Implementation
- •Interface
- •Implementation
- •4. Создание и редактирование бинарных деревьев
- •5. Создание и редактирование сильноветвящихся деревьев
- •Задания для самостоятельной работы
- •Литература
- •144Кафедра Вычислительной Техники и Программирования Московского Государственного Открытого Университета
Контрольные вопросы
Приведите определение понятию граф. Разновидности, свойства и назначение графов.
Способы физического и логического представления графов.
Бинарные деревья. Представления и способы обхода.
Применения бинарных деревьев.
Сильноветвящиеся деревья. Представления и области применения.
8. Методы ускорения доступа к данным
8.1. Хеширование данных
В главе 4 были рассмотрены методы доступа к данным, используя алгоритмы поиска. Для ускорения доступа к данным в таблицах можно использовать предварительное упорядочивание таблицы в соответствии со значениями ключей (рис. 8.1). При этом могут быть использованы методы поиска в упорядоченных структурах данных, например, двоичный поиск, что существенно сокращает время поиска данных по значению ключа. Однако при добавлении новой записи требуется переупорядочить таблицу. Потери времени на повторное упорядочивание таблицы могут значительно превышать выигрыш от сокращения времени поиска.
Тем не менее, метод двоичного поиска относится к алгоритмам класса O(log(n)). Например, для установления факта наличия или отсутствия заданного элемента в наборе из 1000 элементов требуется около 10 сравнений, поскольку 210=1024. Двоичный поиск является наиболее эффективным из всех возможных методов, которые требуют использования функции сравнения. Все они используют ключ элемента для перемещения по структуре данных с применением метода, в основе которого лежит сравнение.
Другие подходы к поиску исключает саму процедуру сравнения. Каждый элемент связывается с уникальным индексом, который позволяет обнаружить элемент путем однонаправленного действия, просто извлекая элемент, расположенный в определенной позиции. Преобразование ключа элемента в значение индекса называется хешированием и выполняется с помощью функции хеширования. Массив, используемый для хранения элементов, с которыми используются значения индексов, называют хеш-таблицей.
Рис. 8.1. Хеш-таблица.
Выполнение поиска с использованием хеширования требует реализации двух отдельных алгоритмов. Первый шаг состоит в хешировании, в результате которого ключ элемента преобразуется в значение индекса. Идеальной хеш-функцией является такая функция h, которая для любых двух неодинаковых ключей дает неодинаковые адреса:
Подобрать такую функцию можно, если все возможные значения ключей заранее известны. Такая организация данных называется совершенным хешированием. При заранее неопределенном множестве значений ключей и ограниченной длины таблицы подбор совершенной функции затруднителен. На практике используют хеш-функции, которые не гарантируют выполнение условия. Отображение двух или более ключей на один и тот же индекс называют конфликтом или коллизией. Поэтому требуется второй шаг, определяющий способ разрешения коллизий в случае их возникновения.
Хеш-таблица представляет хороший пример достижения компромисса между быстродействием и занимаемым объемом памяти. При уникальном значении ключей элемента типа word требуется создать 65536 элементов, и при этом можно гарантировать нахождение элемента с заданным значением ключа в результате одной операции. Однако при хранении не более 100 элементов такой подход окажется расточительным, т.к. 99.85% памяти массива не будет использоваться. С другой стороны, можно выделить размер памяти под массив для фактического числа элементов, выполнить сортировку и двоичный поиск. Память будет сэкономлена, но работать такой алгоритм будет значительно медленнее.
Алгоритмы хеширования предлагают компромисс, при котором хеш-таблицы будут занимать больше места, чем требуется для хранения всех элементов, но поиск будет выполняться всего за несколько операций доступа.
С хеш-таблицами выполняют следующие операции: проверка наличия элемента в таблице и удаление элемента из таблицы. Также часто необходимо расширение таблицы для помещения в нее большего числа элементов, чем предполагалось изначально. Заметим, что функционирование хеш-таблицы не предполагает извлечение записей в порядке следования, т.к. физически соседние ключи таблицы указывают на логически далеко расположенные друг от друга элементы.