Читать курсовая по информатике, вычислительной технике, телекоммуникациям: "Хэш поиск" Страница 2

(Назад) (Cкачать работу)

2

nilnil

3

ash(as)=3

nilnil

4

akh(ak)=4

началоконец

…

…

m

nilnil

Алгоритмы построения и поиска хэш таблицы.

Построение:

Находим значение хэш функции и по этому значению входим в таблицу Если она пустая, то записываем в нее ключ Если она занятая, то сравниваем ключ с заданным ключом:

1. если ключи совпадают, то обрабатываем повторный ключ

2. иначе добавляем новый ключ в конец списка Поиск:

Находим значение хэш функции для искомого ключа и этому значению входим в таблицу Если ячейка пустая, то поиск заканчивается неудачейЕсли она не пустая, то выполняем сравнение ключей:

1. Если ключи совпадают, то поиск заканчивается за одно сравнение

2. Иначе организуем просмотр вспомогательного списка с положительным или отрицательным результатом. Для данного метода большое значение имеет равномерность распределения ключей по хеш-таблице, что гарантирует короткие вспомогательные списки и тем самым уменьшает число сравнений при поиске. Наихудшим является случай, когда для всех ключей хеш-функция дает одно и тоже значение, и все элементы выстраиваются в один длинный линейный список.

Другим фактором, влияющим на эффективность открытого хеширования, является размер хеш-таблицы по отношению к числу входных данных. Если эти величины равны, то теоретически можно обойтись без линейных списков, если между ключами нет конфликтов. На практике рекомендуют выбирать размер хеш-таблицы равным n/2.

3. Основные понятия объектной технологии

Объекты и классы.

Объект – это любая сущность, имеющая некоторые набор свойств и обладающее некоторым поведением.

Свойство объекта описывается как обычные поля данных. В этих полях хранятся значения соответствующих свойств.

Типы полей:

Простейшие примитивные типы.Структурированные типы. Объектные свойства представляющие из себя объекты той же самой или другой природы. (наличие объектных свойств является проявлением одного из способов взаимодействия объектов, а именно композицией объектов, которая используется в курсовой программе)

Набор свойств объекта создается при описании объекта и в дальнейшем изменяется. Поведение объекта описывается набором методов. Каждый метод представляет из себя программный код.

Объединение вместе обрабатываемых данных и программного кода их обработки называется признаком инкапсуляции.

Можно выделить следующие типичные методы объектов:

Конструкторы, деструкторы

Конструктор отвечает за создание нового объекта т. е за выделение ему памяти и практически всегда за начальную инициализацию этой памяти. Конструктор вызывается раньше всех остальных методов. Для создания одного и того же объекта можно предусмотреть несколько различных конструкторов, которые по-разному инициализируют свойства создаваемого объекта.

Деструктор отвечает за разрушение объекта т.е освобождение выделенной объекту памяти.

Методы, с помощью которых можно узнать текущее значение тех или иных свойств. Обычно для каждого свойства создается свой такой метод. Такие методы принято

Похожие работы