- 1
- 2
- 3
- . . .
- последняя »
Министерство образования и науки РФ
Академия управления «ТИСБИ»
Факультет информационных технологий Курсовая работа
по предмету «Объектно-ориентированное программирование»
тема: «Объектная реализация хэш-поиска» Выполнил: студент группы И-311
Хуснутдинов А.И.
Преподаватель:
Козин А.Н Казань 2006
Оглавление. 1. Постановка задачи……………………………………………………....3
3. Поиск с использованием Хэш-функций……………………………...3
2. Основные понятия объектной технологии ……….…………………5
5. Описание классов………………………………………………………9
4. Описание пользовательского интерфейса……………………….......11
6. Листинг и описание всех классов библиотеки на DP….…………….14
7. Список использованной литературы………………………………...25
Постановка задачи.
Цель работы: разработка набора взаимосвязанных классов для реализации Hash-поиска как специализированного контейнера. Разрешение конфликтов с помощью метода открытого хэширования (методом цепочек).
Создание удобного пользовательского интерфейса и получение навыков работы с взаимосвязанными классами.
Набор операций:
1. Добавление:
1.1.В начало списка;
1.2.В конец списка;
2. Удаление всего контейнера;
3. Поиск заданного элемента;
4. Полный проход по Hash таблице;
5. Сохранение таблицы во внешнем файле;
6. Загрузка таблицы из внешнего файла;
2.Поиск с использованием Хэш-функций. 2.1. Основные понятия. Метод хэш-поиска можно считать почти идеалом в среди поисковых методов. Он заключается в следующем. Некоторые элементы распределяются в массиве специальным образом. Для вычисления индекса размещения ячейки по входному ключу используется специальная функция, которая называется хэш-функцией.
Массив, заполненный элементами, определяемой хэш-функцией, называется хэш-таблицей.
Простая хэш-функция:
h(ai)=(ai mod m) + 1;
Хорошей является хэш-функция, которая удовлетворяет следующим условиям:
Функция должна быть очень простой с вычислительной точки зрения Функция должна распределять ключи в хэш-таблице как можно более равномерно.
Если два разных ключа претендуют на одну и ту же ячейку массива, то такая ситуация называется конфликтом ключей.
Важным практическим примером без конфликтной ситуации является построение таблицы ключевых слов в программах-трансляторах с языков программирования. Здесь набор ключевых слов является постоянным, изменяясь только при изменении версии транслятора, а с другой стороны, обработка транслятором входного текста на языке программирования требует многократного и очень быстрого распознавания в этом тексте ключевых слов языка.
Для решения проблемы с конфликтующими ключами были предложены несколько методов, которые можно сгруппировать на две основные группы:
Открытое хэширование Внутреннее хеширование
В данной курсовой работе мы посмотрим открытое хэширование. 2.2.Открытое хэширование. Сама идея открытого хэширования очень проста: связать все элементы с одним и тем же значением хэш-функции во вспомогательный линейный список.
индекс | ключ | указатели |
1 | aih(ai)=1 | началоконец |
- 1
- 2
- 3
- . . .
- последняя »
Похожие работы
Тема: Хэш поиск |
Предмет/Тип: Информатика, ВТ, телекоммуникации (Курсовая работа (т)) |
Тема: Хэш-функции в криптосистемах |
Предмет/Тип: Информационные технологии (Курсовая работа (т)) |
Тема: Программа "Поисковая система на основе хэш-таблиц" |
Предмет/Тип: Отсутствует (Курсовая работа (т)) |
Тема: Ассоциативный массив с возможностью хранения данных произвольных типов (хэш-массив) |
Предмет/Тип: Отсутствует (Практическое задание) |
Тема: Поиск фотооборудования |
Предмет/Тип: Информатика, ВТ, телекоммуникации (Диплом) |
Интересная статья: Быстрое написание курсовой работы