Понедельник, Июль 5th, 2010

Структуры и алгоритмы обработки данных

9.Назовите разницу между этими тремя методами.
10.Какой метод сортировки является самым эффективным?
11.К какому из основных методов относится метод Шелла?

7. ПРЕОБРАЗОВАНИЕ КЛЮЧЕЙ (РАССТАНОВКА)

Метод расстановок (хеширования) направлен на быстрое решение задачи о местоположении элемента в структуре данных. В методе расстановок данные организованы как обычный массив. Поэтому Н — отображение, преобразующее ключи в индексы массива, отсюда и появилось название «преобразование ключей», обычно даваемое этому методу. Следует заметить, что нет никакой нужды обращаться к каким-либо процедурам динамического размещения, ведь массив — это один из основных, статических объектов. Метод преобразования ключей часто используется для таких задач, где можно с успехом воспользоваться и деревьями.
Основная трудность, связанная с преобразованием ключей, заключается в том, что множество возможных значений значительно шире множества допустимых адресов памяти (индексов массива). Возьмем в качестве примера имена, включающие до 16 букв и представляющие собой ключи, идентифицирующие отдельные индивиды из множества в тысячу персон. Следовательно, мы имеем дело с 2616 возможными ключами, которые нужно отобразить в 103 возможных индексов. Поэтому функция Н будет функцией класса «много значений в одно значение». Если дан некоторый ключ k, то первый шаг операции поиска — вычисление связанного с ним индекса h = H(k), а второй (совершенно необходимый) — проверка, действительно ли h идентифицирует в массиве (таблице) Т элемент с ключом k.

7.1. Выбор функции преобразования

Само собой разумеется, что любая хорошая функция преобразования должна как можно равномернее распределять ключи по всему диапазону значений индекса. Если это требование удовлетворяется, то других ограничений уже нет, и даже хорошо, если преобразование будет выглядеть как совершенно случайное. Такая особенность объясняет несколько ненаучное название этого метода — «перемалывание» (хеширование), т. е. дробление аргумента, превращение его в какое-то «месиво». Функция же Н будет называться «функцией расстановки». Ясно, что Н должно вычисляться достаточно эффективно, т. е. состоять из очень небольшого числа основных арифметических операций.
Представим себе, что есть функция преобразования ORD(k), обозначающая порядковый номер ключа k в множестве всех возможных ключей. Кроме того, будем считать, что индекс массива i лежит в диапазоне 0 … N — 1, где N — размер массива. В этом случае ясно, что нужно выбрать следующую функцию:

H(k) = ORD(k)  MOD N

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Категория: Учебники