- •Структуры и алгоритмы обработки данных Методическое пособие
- •Ктн е. В. Курапова, кф-мн е. П. Мачикина
- •Оглавление
- •ВвЕдение
- •Необходимые понятия и определения
- •Основные структуры данных
- •Задача сортировки массивов
- •Трудоемкость методов сортировки массивов
- •Задача сортировки последовательностей
- •Теорема о сложности сортировки
- •Задача поиска элементов с заданным ключом
- •Методы сортировки с квадратичной трудоемкостью
- •Метод прямого выбора
- •Алгоритм на псевдокоде
- •Пузырьковая сортировка
- •Алгоритм на псевдокоде
- •Шейкерная сортировка
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Метод Шелла
- •Метод прямого включения
- •Алгоритм на псевдокоде
- •Метод Шелла
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Быстрые методы сортировки массивов
- •Пирамидальная сортировка
- •Свойства пирамиды
- •Алгоритм на псевдокоде
- •Построение (1, 8)-пирамиды
- •Сортировка
- •Алгоритм на псевдокоде
- •Метод Хоара
- •Алгоритм на псевдокоде
- •Проблема глубины рекурсии.
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Работа с линейными списками
- •Указатели. Основные операции с указателями
- •Основные операции с линейными списками
- •Методы сортировки последовательностей
- •Метод прямого слияния
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Цифровая сортировка
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Двоичный поиск в упорядоченном массиве
- •Алгоритм двоичного поиска
- •Алгоритм на псевдокоде
- •Обозначим
- •Найден – логическая переменная, в которой будем отмечать факт успешного завершения поиска.
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Сортировка данных с произвольной структурой
- •Сравнение данных произвольной структуры
- •Сортировка по множеству ключей. Индексация
- •Алгоритм на псевдокоде (на примере пузырьковой сортировки)
- •Индексация через массив указателей
- •Варианты заданий
- •Двоичные деревья
- •Основные определения и понятия
- •Различные обходы двоичных деревьев
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Идеально сбалансированное дерево поиска
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Случайное дерево поиска
- •Определение случайного дерева поиска
- •Добавление вершины в дерево
- •Алгоритм на псевдокоде
- •Удаление вершины из дерева
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Сбалансированные по высоте деревья (авл-деревья)
- •Определение и свойства авл-дерева
- •Повороты при балансировке
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Удаление вершины из дерева
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Определение б-дерева порядка m
- •Поиск в б-дереве
- •Алгоритм на псевдокоде
- •Построение б-дерева
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Определение двоичного б-дерева
- •Добавление вершины в дерево
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Деревья оптимального поиска (доп)
- •Определение дерева оптимального поиска
- •Точный алгоритм построения доп
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Хэширование и поиск
- •Понятие хэш-функции
- •Алгоритм на псевдокоде
- •Метод прямого связывания
- •Метод открытой адресации
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Элементы теории кодирования информации
- •Необходимые понятия
- •Кодирование целых чисел
- •Алфавитное кодирование
- •Оптимальное алфавитное кодирование
- •Алгоритм на псевдокоде
- •Почти оптимальное алфавитное кодирование
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Рекомендуемая литература
- •Псевдокод для записи алгоритмов
- •Структуры и алгоритмы обработки данных
- •630102, Г. Новосибирск, ул. Кирова, 86.
Алгоритм на псевдокоде
Поиск и вставка элемента с ключом x
Пусть хэш-таблица является массивом A=(a0, a1, … , am-1), сначала заполненный нулями. Пусть x≠0.
h:=x mod m
d:=1
DO
IF (ah=x) элемент найден OD
IF (ah=0) ячейка пуста, ah:=x OD
IF (d≥m) переполнение таблицы OD
h:=h+d
IF (h≥m) h:=h-m FI
d:=d+2
OD
Заметим, что если нужен только поиск, то необходимо исключить операцию ah:=x.
Пример построения хэш-таблицы методом квадратичных проб (m=11) для строки ВЛАДИМИР ПУТИН. Номера символов данной строки приведены в таблице.
Таблица 5. Номера символов строки
В |
Л |
А |
Д |
И |
М |
И |
Р |
П |
У |
Т |
И |
Н |
3 |
12 |
1 |
5 |
9 |
13 |
9 |
17 |
16 |
20 |
19 |
9 |
14 |
Для каждого символа вычисляем его хэш-номер (или последовательность хэш-номеров, если потребуется) и в соответствии с вычисленным номером заносим символ в хэш-таблицу.
В: h0=3 mod 11=3
Л: h0=12 mod 11=1
А: h0=1 mod 11=1
h1=1+1=2
Д: h0=5
И: h0=9
М: h0=13 mod 11=2
h1=2+1=3
h2=3+3=6
Р: h0=17 mod 11=6
h1=6+1=7
П: h0=16 mod 11=5
h1=5+1=6
h2=6+3=9
h3=9+5=3
h4=3+7=10
У: h0=20 mod 11=9
h1=9+1=10
h2=10+3=13 mod 11=2
h3=2+5=7
h4=7+7=14 mod 11=3
h5=3+9=12 mod 11=1
Просмотр элементов хэш-таблицы на этом заканчивается несмотря на то, что в таблице еще имеются незаполненные ячейки, поскольку следующее значение d уже не будет строго меньше m=11. Таким образом, для данной строки не удается построить хэш-таблицу с m=11. Заполненная часть хэш-таблицы выглядит следующим образом
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
Л |
А |
В |
|
Д |
М |
Р |
|
И |
П |
Рисунок 63. Использование квадратичных проб
Варианты заданий
Реализовать построение хэш-таблицы методом прямого связывания для слов заданного текста. Экспериментально определить минимально необходимый объем хэш-таблицы.
Реализовать процедуру поиска с использованием хэш-таблицы (метод прямого связывания). Экспериментально определить среднее число сравнений при поиске.
Построить хэш-таблицу методом линейных проб для слов заданного текста. Экспериментально определить минимально необходимый объем хэш-таблицы число коллизий при построении.
Построить хэш-таблицу методом квадратичных проб для слов заданного текста. Экспериментально определить минимально необходимый объем хэш-таблицы число коллизий при построении.
Экспериментально сравнить объем хэш-таблицы и число коллизий для методов линейных и квадратичных проб.
Реализовать процедуру поиска с использованием хэш-таблицы (метод открытой адресации). Экспериментально определить среднее число коллизий при поиске.